Results 1 to 5 of 5

Math Help - meeting problem: stay or to go

  1. #1
    Newbie
    Joined
    Jul 2011
    Posts
    1

    meeting problem: to stay or to go

    I am a physist, but this life problem has been bothering me for a long time. Sorry if it is too easy.

    Suppose you are in a supermarket with your friend shopping. At some moment you noticed that you lost your friend. The question is what is the fastest strategy to find your friend: 1) search him; or 2) just stay at one place, waiting for him/her.

    To make it purely mathematical problem some simplifications are to be made. Your friend is looking for you. Search in the problem is random, it is Brownian motion. In other terms, whether probabilities of collision of the particles in the two strategies are equal? If no, what is the ratio of them? Reformulated strategies;
    1) two Brownian particles are absolutely the same - the same displacement every time and the same rate (search strategy);
    2) trajectory of one particle must intersect the other motionless one, i.e. point (stay strategy).

    I came to answer that 'search' strategy is faster \sqrt{2} times than 'stay' one, but I am not sure, because it is just consideration, not rigorous proof.

    Thank you
    Last edited by brownian; July 2nd 2011 at 11:37 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Dec 2009
    From
    1111
    Posts
    872
    Thanks
    3

    Re: meeting problem: to stay or to go

    Quote Originally Posted by brownian View Post
    I am a physist, but this life problem has been bothering me for a long time. Sorry if it is too easy.

    Suppose you are in a supermarket with your friend shopping. At some moment you noticed that you lost your friend. The question is what is the fastest strategy to find your friend: 1) search him; or 2) just stay at one place, waiting for him/her.

    To make it purely mathematical problem some simplifications are to be made. Your friend is looking for you. Search in the problem is random, it is Brownian motion. In other terms, whether probabilities of collision of the particles in the two strategies are equal? If no, what is the ratio of them? Reformulated strategies;
    1) two Brownian particles are absolutely the same - the same displacement every time and the same rate (search strategy);
    2) trajectory of one particle must intersect the other motionless one, i.e. point (stay strategy).

    I came to answer that 'search' strategy is faster \sqrt{2} times than 'stay' one, but I am not sure, because it is just consideration, not rigorous proof.

    Thank you
    Hi brownian,

    Can you explain how you got the answer, what you used to get it etc. Then we may be able to help.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    May 2010
    Posts
    1,030
    Thanks
    28

    Re: meeting problem: to stay or to go

    EDIT: Corrected an algebra error which affects result [2] but not the overall conclusion
    EDIT 2: Corrected an incorrect assumption in result [1] which doesn't change the result.

    PS: Im not totally sure the density functions i wrote can be compared in the way i'm comparing them!


    This is quite a long and probably confusiong post, so i'll break down what ive done

    What ive done
    I dont have a ratio (although i suspect it may be 1/2). However i think it can be proved that the 2 person search is faster.


    Notation
    Model the x and y coordinates of each particle as independant weiner processes with drift 0 and scale \sigma.

    eg
    X_{1t} = 0 + \sigma \cdot B(t)

    This is convenient later as the two person search can be re-expressed as a 1 person search with a modified sigma.


    Results
    [1] The two person search is equivalent to a 1 person search with \sigma' = \sigma \sqrt{2}

    [2]The probability density of collisions in a 2-man search at time \frac{t}{2} is equal to the density of collisions in a 1-man search at time t

    [3]Finally (and im not sure about this bit), since the chance of a collision occuring is obviously an increasing function of time, (2) is a sufficient condition for the 2-person search to finish faster on average. I dont know how to calculate how much by.



    Working - Part 1: Show that the 2 person search problem is equivalent to the 1 person search problem with a different search speed

    Consider the 2 person search. I assume that for each searcher:
    The X coordinate of each particle follows a weiner process with drift 0 and scale \sigma
    The Y coordinate of each particle follows a weiner process with drift 0 and scale \sigma

    The values of each coordinate are independently distributed at time t as [tex]N(0,\sigma t)[\tex]. It is well known that the difference between 2 independent normal distribution is also normal. It immediately follows that:

    the difference in X coordinates follows a weiner process with drift 0 and scale \sigma \sqrt{2}
    the difference in Y coordinates follows a weiner process with drift 0 and scale \sigma \sqrt{2}

    If both differences are 0 then they collide. Key point: A collission occurs if two weiner processes with scale \sigma \sqrt{2} and drift 0 take the value 0 at the same time.

    1 person search problem
    One guy stays at the origin and moves with scale parameter \sigma '. make his speed a parameter, ie his X and Y coordinates follow independant weiner processes with drift 0 and scale \sigma'

    They collide if the searching player returns to the origin. ie if two independant weiner processes with drift 0 and scale \sigma ' have value 0 at the same time.

    This is the same as the 2-person search process if \sigma '=\sigma\sqrt{2}. So it is sufficient to compare the performance of a 1-person search for the scale values \sigma and \sigma '

    Working - Part 2 Find the relationship between \sigma and the performance of a 1-person search

    Let X and Y be the X and Y coordinates of the searcher. Assume each follows a weiner process with scale \sigma. Since X and Y are independent the joint probability density is just the product of 2 marginal normal densities of distribution N(0,\sigma t):

    f(x,y,t) = f_x(x,t)f_y(y,t) = \frac{1}{\sqrt{4 \pi^2 \sigma ^4 t^2}} e^{-\frac{x^2y^2}{4\sigma ^4 t^2}

    Collissions occur when x=y=0, so the density of a collision at time t if the scale parameter is \sigma is :
    c(t,\sigma ) = f(0,0,t) = \frac{1}{\sqrt{4 \pi^2 \sigma ^4 t^2}} e^{0}

    From result [1] we know already that a 2 person search is the same as a 1-person search with parameter \sigma '. hence the density of collisions in the 2-man search is c(t,\sigma'). Now, lets compare:

    Density of collisions in 1 person search: c(t,\sigma)
    Density of collisions in 2 person search: c(t,\sigma')

    here is the interesting part:
    Look at the density of collisions in the 2-persion search at time \frac{t \sigma^2}{\sigma ' ^2}:

    c(\frac{t \sigma^2}{\sigma' ^2},\sigma') = \frac{1}{\sqrt{4 \pi^2 \sigma ' ^4 \frac{t^2 \sigma^4}{\sigma '^4}}} = \frac{1}{\sqrt{4 \pi^2 \sigma ^4 t^2}} = c(t,\sigma)


    So the probability density of a collision at time \frac{t \sigma}{\sigma ' ^2} in the 2-man search is the same as the probability density at time t in the 1 man search.

    Its easy from here. Note that t \frac{\sigma^2}{\sigma ' ^2} = t \frac {\sigma^2}{(\sigma \sqrt{2})^2} = \frac{t}{2}

    And so finally we have result [2]:

    The probability density of collisions in a 2-man search at time \frac{t}{2} is equal to the density of collisions in a 1-man search at time t




    Working - Part 3 Use the previous result to deduce the relative performance of the searches

    My (intuitive and very loose!) interpretation of the above is that whatever is going to happen will happen 2 times faster in the 2 man search.
    Last edited by SpringFan25; July 7th 2011 at 05:38 AM. Reason: algebra fix
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Abu-Khalil's Avatar
    Joined
    Oct 2008
    From
    Santiago
    Posts
    148

    Re: meeting problem: to stay or to go

    It doesn't affects the result but i think it should be f(x,y,t)=f_x(x,t)f_y(y,t)=\frac{1}{\sqrt{4\pi^2 \sigma^4 t^2}}e^{-\frac{(x^2+y^2)}{2\sigma^2t}}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    May 2010
    Posts
    1,030
    Thanks
    28

    Re: meeting problem: to stay or to go

    Quote Originally Posted by Abu-Khalil View Post
    It doesn't affects the result but i think it should be f(x,y,t)=f_x(x,t)f_y(y,t)=\frac{1}{\sqrt{4\pi^2 \sigma^4 t^2}}e^{-\frac{(x^2+y^2)}{2\sigma^2t}}
    Good spot. Unfortunately the forum wont let me edit it (i think there is a time limit or something)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. how do casinoes stay in business?
    Posted in the Math Forum
    Replies: 19
    Last Post: January 1st 2012, 05:54 PM
  2. How long did i stay
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: August 17th 2009, 12:26 PM
  3. Probability Meeting Problem
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: March 4th 2009, 04:27 PM
  4. Desparet for HELP! Calculate average stay!
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: August 7th 2008, 04:50 PM

Search Tags


/mathhelpforum @mathhelpforum