Conference rusure::math

Article 6967 of sci.math
Path: ryn.esg.dec.com!shlump.nac.dec.com!decuac!haven!ncifcrf!toms
From: toms@ncifcrf.gov (Tom Schneider)
Newsgroups: sci.math
Subject: Re: Problem
Message-ID: <1340@fcs280s.ncifcrf.gov>
Date: 18 Sep 89 23:04:44 GMT
References: <14360@bloom-beacon.MIT.EDU>
Reply-To: toms@fcs260c2.UUCP (Tom Schneider)
Organization: National Cancer Institute, Frederick
Lines: 19

	[extract deleted]

Seems to me you'd want to land on the peak, which has the greatest probability
of being where the cookie is.  After that you've got a problem!  Ideally, you'd
walk a bit left down the slope, but not too far because now it's more likely
that the cookie is on the other side!  So you walk over to the other side until
you are below where you were on the first side... then repeat.  That's not so
good because you keep wasting time walking over the peak again.  If I had a
twin brother Skippy, I'd send him the other way, and then when one of us found
the cookie, we shout or radio to the other and we'd get back together on the
peak to share it.  Now the question is, do I trust Skippy not to eat the whole
cookie?  Tom


Article 6974 of sci.math
Path: ryn.esg.dec.com!shlump.nac.dec.com!decwrl!ucbvax!tut.cis.ohio-state.edu!gem.mps.ohio-state.edu!ginosko!uunet!jarthur!bevans
From: bevans@jarthur.Claremont.EDU (Brian Evans)
Newsgroups: sci.math
Subject: Re: Problem
Message-ID: <2010@jarthur.Claremont.EDU>
Date: 19 Sep 89 08:07:01 GMT
References: <14360@bloom-beacon.MIT.EDU> <1340@fcs280s.ncifcrf.gov>
Reply-To: bevans@jarthur.UUCP (Brian Evans)
Organization: Society for the Preservation of E. coli
Lines: 14


Problem of cookie on gaussian distribution:  How to best find the cookie?

Simple!  Get Cookie Monster to tell you where to land on the line.
That, obviously, is where the cookie is.  Now then, you may not be
able to eat cookie, but Cookie Monster know where cookie is.......

In tummy.  ;-)

-- 
Brian Evans			    "It has been scientifically proven
bevans@hmcvax.bitnet		     that scientists cause cancer in
bevans@jarthur.claremont.edu         laboratory rats."
or !uunet!jarthur!bevans

I've been struggling with this for awhile and haven't gotten anywhere, but 
it seems plausible to me that you don't want to start in the center, since
half the time, as soon as you switch directions, you see that you would
have been better off to have started the same distance on the other side of
the peak... I think the best method is to start at a distance off the peak
that is some simple function of s= the standard deviation, perhaps s
itself, and switch when the absolute value of the distance from the middle
is like 2*s, 3(or 4)*s, etc. The point is to make the first pass wide
enough so the probability of finding the cookie is at least 1/2 before you
switch directions and have to start wasting motion. 

Lynn 

    Is this material for a contest?  Entrants would write a routine that,
    upon every call, would return a pair of real numbers (from, to).
    The calling program would generate cookie locations and call the
    "entry" routine repeatedly until the correct interval was returned
    (and, of course, verify that the interval is adjacent to the last
    interval).
    
    Any interest?

>    The calling program would generate cookie locations and call the
>    "entry" routine repeatedly until the correct interval was returned
>    (and, of course, verify that the interval is adjacent to the last
>    interval).

I think that's not quite the same problem ... it doesn't take into account 
the cost function associated with a change in direction, which is 
proportional to the size of the subinterval already covered in previous 
steps. Or maybe I'm misunderstanding someone?

Lynn 

    A change in direction nominally costs 0, but that's not what you meant.
    Assume mean 0 and standard deviation 1, and a variant of the Yarbrough
    algorithm in .3.  Your code would return:
    
    (-1, -1)	first time a point, indicating a start at -1 (1 sd off mean)
    (-1, +2)	march 1 sd right to 0, 1 sd right to +1, thence to +2
    (+2, -3)	move "back over" area already found, then 1 sd further to -3
    (-3, +4)	" " " ", then 1 sd further to +4
    
    etc.  You would pay 3 for move 2, 5 for move 3, 7 for move 4, etc.
    
    Since you can only designate intervals adjacent to your latest endpoint,
    you would naturally have to re-cover the subintervals crossed in earlier
    searches, assuming you eventually wanted to search the entire real line.
    The intervals above are equivalent to:
    
    (-1, -1)	Starting point
    (-1,  0)	Move right 1
    ( 0, +1)	Move right 1
    (+1, +2)	Move right 1
    (+2, +1)	Move left 1 (re-covering earlier territory)
    (+1,  0)		" " " "
    (0,  -1)		" " " "
    
    etc.  You would not be allowed to go from (+1, +2) to (-1, -2) since
    those two intervals are not adjacent.  (Actually I should be using
    [a,b] rather than (a,b) since we're dealing with closed intervals).
    
      John

	Well, what's the answer?

	It seems to me that you need to solve an infinite number of
equations in order to determine the route that you should take, but maybe
someone can see through the calculus more clearly than I can.

	One thing that does drop out, however, is the starting point.   If
you say wlog that the first step is going to be in a *positive* direction,
then the starting point I think is the solution to the transcendental 
equation:

		t*p(t) = -1/2

where p is the pdf for a normal distribution with mean 0, variance 1.
So, you *don't* start at the origin, confirming what intuition would 
suggest.

Regards,
Andrew.

    I hypothesize that there is no solution, although I have not had time
    yet to prove it.  Specifically, I strongly suspect the following:

    Suppose you have a solution which you suppose to be optimal.  That
    solution may be expressed as (or reduced to, after eliminating non-
    deterministic elements which cannot change the expected search time)
    a starting point and a sequence of increasing lengths to be searched
    over in alternating directions.  Then I suspect that if the starting
    point is on the origin or a finite distance from it, and if each of
    the search lengths is a finite, non-zero amount larger than the
    previous, then I can take your proposed a solution and create one
    with a smaller expected search time.

				    Topher

I tried working this problem, but for a triangular probability distribution
(p(x) = 1+x for -1<=x<=0, p(x) = 1-x for 0<=x<=1).  Solveable, but unpleasant, 

>    Suppose you have a solution which you suppose to be optimal.  That
>    solution may be expressed as (or reduced to, after eliminating non-
>    deterministic elements which cannot change the expected search time)
>    a starting point and a sequence of increasing lengths to be searched
>    over in alternating directions.  Then I suspect that if the starting
>    point is on the origin or a finite distance from it, and if each of
>    the search lengths is a finite, non-zero amount larger than the
>    previous, then I can take your proposed a solution and create one
>    with a smaller expected search time.

Assuming this is true, then you can create a strictly monotonic decreasing
sequence of positive search times, each associated with some search strategy.

It clearly converges to the glb of the sequence.  Assume p is the limit.
Since the  This point is clearly not associated with any legal strategy,
because if it were then it would violate the conjecture that for every
legal strategy there is one with shorter search time.  

Why can't p be acheived with a legal search strategy?  Is it because it would 
require infinitely many search intervals?  That doesn't seem to be what you
are describing.

Avery

	There seems to be an awful lot of verbiage in this topic, and not much
concrete mathematics.   The way I view the problem, we have p(x) be the normal
pdg with mean 0 and variance 1.   We will "land" at point l_0, then go right
to r_0, then left to l_1 < l_0 then right to r_1 > r_0, then left to l_2, etc.
let f(x,x') denote int(x to x')p(x)dx.

	Then I figure that the expected distance until the cookie is found is
given by the following expression *if* it converges:

E =	2*p(l_0) - l_0 - sum(j = 1 to %) [2*(1-f(l_j,r_(j-1)))*l_j]
		       + sum(j = 0 to %) [2*(1-f(l_j,r_j))*r_j]

	Does anyone disagree so far?

	Now, the klutzy way forward is to see if we can differentiate this
expression with respect to all the l_j & r_j, and see if we have a chance to
get a minima.   (I made a slip in my previous posting at this point.)   After
finding some minima, we can then explore the convergence of the series, for
those values!   It seems like a backward way of doing things, but I bet it's
valid.

	Note that dp(x)/dx = -x*p(x), df(x,x')/dx = -p(x), df(x,x')/dx' = p(x')

So, diffing wrt l_0, we get:

	-1 + 2*p(l_0)*[r_0-l_0]

Diffing with respect to l_j, for j > 0:

	-2*(1-f(l_j,r_(j-1)) + 2*p(l_j)*[r_j-l_j]

Diffing with respect to r_j, for j >= 0:

	2*(1-f(l_j,r_j)) - 2*p(r_j)*[r_j-l_(j+1)] 

	Does everyone agree so far.

Postponing for a moment the question of solving these equations, let's ask
(assuming they can all be simultaneously satisfied, if they represent a
global minimum.   Let's take the second differential of each of the three
expressions above:

(out of time, I'll be back.)

Regards,
Andrew.

>Postponing for a moment the question of solving these equations, let's ask
>(assuming they can all be simultaneously satisfied, if they represent a
>global minimum.   Let's take the second differential of each of the three
>expressions above:

For l_0:
	-2*p(l_0)*(l_0*[r_0-l_0] + 1)
+ve iff:
	l_0 < -1/[r_0-l_0] (which is certainly < 0).   reasonable

For l_j, j > 0
	-2*p(l_j)*(l_j*[r_j-l_j] + 2)
+ve iff:
	l_j < -2/[r_j-l_j] (which is certainly < 0).   reasonable

For r_j j >= 0
	2*p(r_j)*(r_j*[r_j-l(j+1)] -2)
+ve iff:
	r_j > 2/[r_j-l(j+1)] (which is certainly > 0).   reasonable

	What this seems to be saying is: you need to have the l_j negative,
and the r_j positive.   As long as l_j < l_(j-1) and r_j > r_(j-1), then
the validity of *all* these inequalities would follow from just:
	r_0 > l_0 -1/l_0
	l_1 < r_0 - 2/r_0
	r_1 > l_1 -2/l_1


	Now returning to the 1st differentials, these are all zero, and we
probably have a minimum, when:

	2*p(l_0)*[r_0-l_0] = 1

for j > 0:
	f(l_j,r_(j-1)) + p(l_j)*[r_j-l_j] = 1

for j >= 0:
	f(l_j,r_j) + p(r_j)*[r_j-l_(j+1)] = 1

	This gives us omega transcendental equations, each in 3 variables,
except for one in 2 variables.   How can we solve any of them, even 
numerically?   There are various techniques for shepherding the variables for 
this kind of problem, eg: Lagrangians, but I can't think of any other relation 
which has to hold for the variables.

	However, if we're willing to guess l_0 for the moment, then we can
express each of the other variables, one by one, as an explicit function
(if you count the error function as explicit) of the previously defined
variables.   One could compute E progressively, and stop when E seemed to
have converged.   It would then be possible to try sensitivity analysis
to determine which is the best l_0.   I am not confident that one could neatly
manipulate an analytic expression for E as a function of l_0.

*******************************************************************************
*
* ANALYTIC SOLUTION TO THE PROBLEM, IN TERMS OF l_0:
*
* r_0 = l_0 + 1/[2*p(l_0)]
*
* for j > 0:
*	l_j = r_(j-1) - (1-f(l_(j-1),r_(j-1)))/p(r_(j-1))
*
* for j > 0:
*	r_j = l_j + (1-f(l_j,r_(j-1)))/p(l_j)
*
* where let's remember that:
*	p(x) is the value of the zero-mean unit-variance normal pdf at x.
*	f(x,x') = int(x to x')p(x)dx	(the error function)
*
*	When numerical values for r_0, l_1, r_1 have been computed for any l_0,
* there should be a check done against the three sufficient 2nd differential 
* equations developed above:
*	r_0 > l_0 -1/l_0
*	l_1 < r_0 - 2/r_0
*	r_1 > l_1 -2/l_1
*	If these all pass, then the solution for this value of l_0 is
* guaranteed to be a minimum, with respect to all the other variables.
*
*******************************************************************************

	It might be possible that all the complexities vanish when the
values are resubstituted into the original equation, but somehow I doubt it:

E =	2*p(l_0) - l_0 - 2*sum(j = 1 to %) [(1-f(l_j,r_(j-1)))*l_j]
		       + 2*sum(j = 0 to %) [(1-f(l_j,r_j))*r_j]

	However, the probably happy behaviour of the 2nd derivatives does 
suggest to me that we have a local minimum here, and it's a question of trying 
various l_0 to find which gives the lowest E.

Regards,
Andrew.

	On reflection, I am unhappy that I remember correctly how to
manage optimization of a function of an infinite number of variables.
If someone with better recall or inate sense can recall to me how we
can do it, I would be grateful.   Remember, we are trying to minimize:

E =	2*p(l_0) - l_0 - 2*sum(j = 1 to %) [(1-f(l_j,r_(j-1)))*l_j]
		       + 2*sum(j = 0 to %) [(1-f(l_j,r_j))*r_j]

as a function of l_j,r_j j=0,...,%, and we have the inequalities:

	... < l_j < l(j-1) < ... < l_0 < r_0 < ... < r_(j_1) < r_j < ...

p(x) = [1/sqrt(2*pi)] * exp(-x^2/2)
f(x,x') = int(x to x') p(x) dx

regards,
Andrew.

    Renewed activity on this topic inspired me to finish up something that
    I had started before: a justification for my belief that there is no
    optimal strategy.  Note that this is not meant as a formal proof.

    First: some notation.

	p(x) = the value of the probability density function for the
	       Z distribution (standard normal -- mean of 0, standard
	       deviation of 1) at point x.

	P(x) = The value of the lower cumulative probability function for
	       the Z distribution at point x.  I.e., the probability that
	       a random sample from the Z distribution will be less than
	       x.

	Q(x) = The value of the upper cumulative probability function for
	       the Z distribution at point x.  I.e., the probability that
	       a random sample from the Z distribution will be greater than
	       or equal to x.

	x1:x2 = The region (interval) from x1 to x2.

	P(R) for R a region = the probability that a random sample from the
	       from the Z distribution will lie within region R.  If R =
	       x1:x2, then P(R) = P(x1:x2) = P(x2) - P(x1) = Q(x1) - Q(x2).

    The continuous nature of the problem makes it a little bit tricky to
    deal with so I introduce a family of related problems.  Each member of
    the family is characterized by a parameter "s" (a positive real number).

    The Discrete Cookie-Finding Problem of step-size s (DCFP[s]) is the
    same as the original problem (the Continuous Cookie-Finding Problem or
    CCFP) except:

	1) The searcher may only start an integral number of multiples of
	   s from 0 (this isn't actually particularly important).

	2) The searcher searches by taking a step of width s and
	   determining whether the cookie is anywhere within the region
	   stepped over.  This takes time 1/s.

    The CCFP is the limit of the DCFPs as s goes to 0.

    OK.  Now imagine that I am the searcher, sometime into my, so far
    unsuccessful, search.  I have just taken a step (of size s, of course)
    "over" some previously unsearched territory.  Adjacent to me is an
    already searched region stretching from "a" to "b", a<b.  If b-a=s,
    I have just landed and searched my first segment.  Without loss of
    generality I may assume that I am standing at "b".

    I now have two choices.  I can search the next unsearched segment in
    the positive direction (call it S+), or I can search the next
    unsearched segment in the negative direction (call it S-).  The
    time-cost for S+ is 1/s.  The time-cost for S- is b-a+(1/s).

    Note first of all that the history of how I got to my current position
    -- my search path up to now -- is irrelevant to the question of my
    optimal next move.

    What is the basis of my choice?

    Searching S+ costs 1/s, and is clearly a win if the cookie is within
    it.  This has a probability of:

		    P(S+)/(1-P(a:b)) = P(b:b+s)/(1-P(a:b))

    There is further potential cost and gain to be considered since if the
    cookie is not found on the step, we will have (1) decreased our
    evaluation of the probability that the cookie is in the positive
    direction, (2) increased the same for the negative direction, (3)
    decreased the cost of further search in the positive direction and (4)
    increased the same for the negative direction.

    Searching S- costs b-a+(1/s), and is a win if the cookie is within
    *it*.  This has a probability of:

		    P(S-)/(1-P(a:b)) = P(a-s:a)/(1-P(a:b)).

    With similar further potential costs and gains.

    These further potential costs and gains are what make the problem
    complex, since their evaluation depends on the strategy from each "new"
    position.

    I can take a short-cut in some cases, however, by constructing as "S+
    desirability score", D+.  If this score is large enough (without
    worrying about what constitutes "large enough") then it is to my
    advantage to search S+ next.  If it isn't, then I will have to use
    further analysis to make my decision.

    Here are the relevant considerations for constructing D+.

	1) The greater the probability of finding the cookie in S+ the
	   greater the benefit, all else being equal, of searching S+
	   next.

	2) The greater the width of the searched region (b-a), the
	   greater the disadvantage of searching S- next, all else being
	   equal, and therefore, the greater the advantage of searching
	   S+ next.

        3) The greater the probability of finding the cookie after crossing
           over the already searched region, before we cross back over to
           search the positive side again, the greater the advantage of
           searching S- next and therefore the greater the disadvantage of
           searching S+ next.  We don't know what that probability is
           (since it depends on undetermined optimal strategy), but we know
           that it is less than the probability that the cookie is anywhere
           to the left of a, i.e.,

		    P(a)/(1-P(a:b))

	   Since we want to be sure that the advantage is to S+ we will use
	   this upper bound.

    That gives us:

			        P(S+)
			       -------(b-a)
				  N              P(S+)(b-a)
                   D+(S+,a) = --------------  = ------------
				   P(a)             P(a)
				  ------
				    N

    Assume that my b is in the positive tail (as eventually, it must be).
    Further assume for the moment that I check my D+(S+,a), as given by the
    above formula, and find it at least large enough to take S+ without
    further analysis.  The search fails, and so I have a new positive step
    to check, S++ = b+s:b+2s, with S- unchanged.  So:

		                 P(S++)(b-a+s)
		    D+(S++,a) = ---------------
			             P(a)

    The difference between D+(S++) and D+(S+) is

				     P(S++)(b-a) + P(S++)s - P(S+)(b-a)
	    D+(S++,a) - D+(S+,a) = ------------------------------------
						    P(a)

				     (P(S++) - P(S+))(b-a) + P(S++)s
			          = ---------------------------------
					          P(a)

    We now take the limit as s goes to zero.  Note that P(S+) equals
    P(b+s) - P(b).  As s goes to zero this equals P'(b), or p(b).
    Similarly P(S++) equals (at the limit) p(b+s).  Therefore, the "P(S++) -
    P(S+)" becomes "p(b+s) - p(b)", which, as s goes to zero is the
    deriviative of p at b which happens to be b*p(b).  P(S++) becomes, as
    I said before, p(b+s), which in turn becomes p(b) (i.e., converges), so
    P(S++)s goes to zero.

    So as s goes to 0, the above difference becomes: p(b)*b*(b-a)/P(a). All
    of these terms are positive, and so, we can conclude that for a small
    enough step size (most importantly the "infinitesimal" step size of the
    original CCSP), once we have found a strong enough D+ it will continue
    to be strong enough and we will never get the "green light" to go back
    and continue with the negative tail.

    (to be continued)....

					    Topher

    OK, let's summarize where we are.

    We have a function D+ over states of the problem search space.  This
    function represents an estimate of the preponderance of reasons for
    continuing the search in the current direction over reversing the
    direction of search, crossing over the already searched region and
    continuing in the negative direction.

    It is plausible (but unproven -- this is the major point in need of
    real proof) that there is a threshold value, d, such that D+ > d is
    sufficient justification to conclude that the optimal search strategy
    continues in the same direction.

    I have shown that D+ as a function of the current search position
    increases monotonically throughout the positive tail.  This does not
    mean, of course, that D+ will eventually exceed the threshold d,
    since it may increase asymptotically to a value below d.  I will
    show in a while that that is not the case: if there is a finite d,
    a complete search will eventually result in a state where D+ will
    exceed it.

    But first, I would like to cut to the heart of the matter and discuss
    possible interpretations of the non-decreasing nature of D+.  There
    are two plausible interpretations:

	1) All search strategies diverge.  Although a particular search
	   strategy may have a very high probability of succeeding in
	   some reasonable time, there will always be enough probability
	   of having to cross back and forth over an ever-widening, already
	   searched region that the expected search time will be infinite.

	   While this alternative is possible, I don't think it is very
	   likely.  The tails die off exponentially while the searched
	   region widens linearly.  Although I have not shown that there
	   are search strategies with finite time (nor have I spent much
	   time trying) I think that they are probably numerous.

	2) Search strategies converge.  A search strategy will zig back
	   and forth and eventually (in finite expected time) find the
	   cookie.  However, for any "good" strategy a very slightly better
	   one can be constructed by lengthening one of the further out
	   zigs.  That is, one can find a place, probably well into the
	   search, where the strategy keeps going in the same direction for
	   some finite distance, and where any lengthening of that
	   distance will slightly decrease the expected search time.

	   I.e., there is no optimal solution.

    That leaves us needing to show that D+ will eventually exceed any
    finite d.  I will assume that we are talking about some zig-zagging
    strategy which will reach every point a finite distance from the origin
    in a finite amount of time.

    The previous explicit definition for D+ was for DCFP[s] and was:

			       P(S+)(b-a)
                   D+(S+,a) = ------------
				  P(a)

    with S+ representing the region b:b+s.  Using the fact that the limit
    of S+ as s goes to 0 is p(b) for CCFP we have:

			     p(b)(b-a)
		  D+(a,b) = -----------
				P(a)

    Eventually during our search we will by necessity reach a point where
    we will have searched the origin.  After that a will be negative and
    b will be positive.  We will assume that we have passed that point, and
    that will allow us to change our notation slightly.  Instead of dealing
    with a, the lower boundary of the searched distance we will deal with
    A = -a, the distance from the origin to the lower boundary.  We get:

			     p(b)(b+A)
		  D+(A,b) = -----------
				Q(A)

    Furthermore, we will assume that we have reached a point (as we must
    eventually) with the following characteristics: b>1, A>1, and b+A>=d.

    We make use of the following inequality:

				p(x)
			Q(x) < ------
				 x

    for positive x (for large x the right side is an excellent estimator
    for Q).

    Therefore,

			     p(b)(b+A)A
		  D+(A,b) > ------------
				p(A)

    Since (b+A)>=d, and A>1, if p(b)/p(A)>=1 then D+(A,b)>d.  (This will
    occur if b<=A.)  Assume we are "looking" at D+(A,b) just as we are
    about to turn around and go the other way according to our strategy.

    If all our conditions are met and p(b)/p(A)>=1 then D+(A,b) will be
    greater than d and we are done.  If not, we will turn around and cross
    the searched area.  Now we look at the D+ (which will be "reversed")
    just as we hit a.  We get:

			     p(A)(b+A)b
		  D+(A,b) > ------------
				 p(b)

    Since p(b)/p(A) was less than 1, p(A)/p(b) must be greater than 1, by
    assumption b>1, and so D+(A,b) > d.  QED.

					Topher

    People working on this problem may find the following result helpful:

    For a standard normal distribution, the expected time to find a cookie
    searching linearly through the region from a to b, with a<b, given that
    the cookie IS in that region equals (using the notation explained in
    .14):

		     p(a) - p(b)
		    ------------- - a
			P(a:b)

    Searching from b to a is:

		         p(a) - p(b)
		    b - -------------
			    P(a:b)

						Topher

>	2) The searcher searches by taking a step of width s and
>	   determining whether the cookie is anywhere within the region
>	   stepped over.  This takes time 1/s.

	Eh?   Why time 1/s?   Surely just s?

>   The CCFP is the limit of the DCFPs as s goes to 0.

	And it takes an infinite time to search an infinitessimal interval
like this.   No wonder you don't think that you can expect to find the
cookie in a finite time!

Regards,
Andrew.

RE: .17 (Andrew)

>>	   stepped over.  This takes time 1/s.
>
>	Eh?   Why time 1/s?   Surely just s?

    Ah-ha, you *did* understand -- I screwed up.  Something left over from a
    different notation.  Replace all the "1/s"es with s.  Its too long to
    post a corrected version, but I'll be glad to send one to anyone who
    wants one via mail.

    I hereby warrant that the previously posted material is almost
    certainly not at all free of dumb errors -- hopefully none are
    substantive or significant to the point.  An additional gold star to
    anyone finding such errors (the first is for reading all that junk).

			Topher