meeting problem: stay or to go

**brownian** · July 2nd 2011, 09:31 AM

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

**Sudharaka** · July 6th 2011, 12:27 AM

Originally Posted by brownian

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.

**SpringFan25** · July 6th 2011, 05:05 AM

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.

**Abu-Khalil** · July 7th 2011, 07:35 PM

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}}$

**SpringFan25** · July 8th 2011, 04:25 AM

Originally Posted by Abu-Khalil

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)

Thread: meeting problem: stay or to go

LinkBack

Thread Tools

Display

meeting problem: to stay or to go

Re: meeting problem: to stay or to go

Re: meeting problem: to stay or to go

Re: meeting problem: to stay or to go

Re: meeting problem: to stay or to go

Similar Math Help Forum Discussions

how do casinoes stay in business?

How long did i stay

Probability Meeting Problem

Desparet for HELP! Calculate average stay!

Search Tags