You are one of many birds arranged at random along an infinitely long telephone wire.
probability/nearest.neighbor New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
You are one of many birds arranged at random along an infinitely long telephone wire. What is the probability that you are the nearest neighbour of your nearest neighbour? What if you are one of many soldiers arranged at random on an infinite flat plane?
Show solution
I think it should be pointed out that "number" should not be taken
literally here, since you must have an infinite number of
birds/soldiers.
The answer to the first problem is as follows:
Assume that the birds are arranged with density m. (This density
factor drops out, as expected.) Now, if your nearest neighbor is
at distance x, then what is the probability that his nearest
neighbor is you? This probability is just the probability that
there are no birds in an interval of length x (on the other side
of your nearest neighbor), which is
F(x) = 1-e^(-mx)
[ Editor: the probability of no birds in an interval of length x is
e^(-mx); 1-e^(-mx) is the probability of at least one. ]
Now, what is the distribution of your nearest neighbor's distance?
This distance is the minimum of the distances of your leftward
nearest neighbor and your rightward nearest neighbor. Since these
two distances are independent and distributed exponentially with
parameter m, their minimum is distributed exponentially with
parameter 2m, so the pdf of the minimum is
g(x) = 2me^(-2mx)
The probability that you are your nearest neighbor's nearest
neighbor is then the integral of F(x)*g(x) dx from x=0 to infinity,
and this is equal to 1/3. (As promised, the m drops out.)
[ Editor: with F(x) = e^(-mx) the integral is the integral of
2m e^(-3mx) dx = 2/3. So the probability that you are your nearest
neighbour's nearest neighbour is 2/3; 1/3 is the probability that you
are not. ]
The answer to the second problem is as follows:
We can proceed in the same manner. Assume that the soldiers are placed
with density m. Suppose that your nearest neighbor is at distance r.
What is the probability that you are his nearest neighbor? It is
F(x) = 1-e^[-zm(x^2)] [Editor: minus sign missing in the original]
where z = [2#+3sqrt(3)]/6, # being the ASCII for pi = 3.14159...
The distribution of the distance of your nearest neighbor is
g(x) = 2#mxe^[-#m(x^2)] [Editor: minus sign missing in the original]
The probability that you are your nearest neighbor's nearest neighbor
is then just the integral of F(x)*g(x) dx from x=0 to infinity, and
that is equal to
2#+3sqrt(3)
-----------
8#+3sqrt(3)
-- Brian Tung <brian@cs.ucla.edu>
[ Editor: the same slip as in the first answer. You are his nearest
neighbour if no soldier lies in the part of the disk of radius x
around him that is not inside the disk of radius x around you; that
region has area z*x^2, so the probability is e^(-zmx^2), not
1-e^(-zmx^2). The integral of e^(-zmx^2)*g(x) dx is #/(#+z) =
6#/(8#+3sqrt(3)), about 0.6215; the value above, about 0.3785, is the
probability that you are not your nearest neighbour's nearest
neighbour. ]
[ Editor: Brian Tung's own corrections, posted the same day (26 August
1993) in the thread "N rifle persons puzzle". ]
An error occurred. F(x) is actually the probability that you are NOT
the nearest neighbor (given distance x), so the probability that you
are your nearest neighbor's nearest neighbor should actually be
1/3
in the first problem, and
6#
-----------
8#+3sqrt(3)
in the second problem.
I am currently trying to verify these solutions.
-- Brian Tung <brian@cs.ucla.edu>
I wrote:
> ...the probability that you are your nearest neighbor's nearest
> neighbor should actually be 1/3...
Aaaaargh! Of course, I meant to write 2/3, again.
-- Brian Tung <brian@cs.ucla.edu>
[ Editor: "Nearest-neighbor probabilities; again.", posted to sci.math
and rec.puzzles in September 1993. "#" stands for pi, as in the
answers above. ]
A few weeks ago this problem appeared on rec.puzzles. I don't recall
seeing any follow-up beyond Byron Elbows' post, excerpted below; so I
thought I'd add a little to it.
>> 1) You are one of a number of birds are arranged at random along an
>> infinitely long telephone wire. What is the probability that you
>> are the nearest neighbour of your nearest neighbour?
>>
>> 2) You are one of a number of soldiers arranged at random on an
>> infinite flat plane. Same question...
>
>2/3
>
>in the first problem, and
>
> 6#
>-----------
>8#+3sqrt(3)
>
>in the second problem.
>
>I am currently trying to verify these solutions.
>
>byron elbows
Byron Elbows gave correct proofs: putting on the line (or plane) a
constant-density Poisson process of point-like birds, calculating the
probabilities above in classical manner, and observing that the density
was irrelevant.
But in fact, the answer for problem 1 can be obtained much quicker,
without having to know about Poisson processes (or equivalent).
Consider five birds, U (you), and your nearest and 2nd-nearest
neighbors on either side: A B U C D. The distances AB, BU, UC, CD are
all independent identically distributed, (though we only need
exchangeable); so we need merely list all 24 possibilities of how they
may be ordered, reducible to 12 by left-right symmetry.
Then 8 of these 12 orderings give the result required. (Details as
exercise).
---
Alas ! No such simple combinatorial proof will work for problem 2.
Byron Elbows' method, though, on closer inspection can be made simpler,
by observing that the essential part of the calculations reduces to
B + C
P(your nearest nbr has no-one nearer than you) = ---------
A + B + C
...where A,B,C are the areas diagrammed below.
Exercise: derive the above formula from a Poisson process.
______ _____
-- -- -- --
-~ X ~-
/ - - \ U = you
' / \ \
/ / \ ` N = nearest nbr
| U N |
\ A \ B / C '
` \ / /
\ - - /
--_ X _-
-- -- -- --
~~~~~~ ~~~~~~
Please excuse the filthy ascii diagram:- 2 circles centred at U and N.
It is trivial that B+C = pi, (WLOG we can assume radius = 1); and some
simple geometry shows that A+B+C = 4 pi/3 + sqrt(3)/2 .
Thus (B+C)/(A+B+C) = 6 pi/(8 pi + 3 sqrt(3)); as Byron obtained.
---
The same method quickly gives 2/3 for problem 1, where the circles
reduce to overlapping intervals.
A similar calculation works in 3 dimensions, where we get that
B + C 4 pi/3
P(your nearest nbr has no-one nearer than you) = --------- = -----------------
A + B + C 4 pi/3 + 11 pi/12
= 16/27. A remarkably simple answer !
So we get....
1 dimension: prob = 2/3 = .6667
2 dimensions: prob = 6p/(8p+3root3) = .6215
3 dimensions: prob = 16/27 = .5926
------
I'll leave it to someone else to calculate the overlapping-area
fractions for still higher dimensions !!
Altogether a fun problem.
-- Bill Taylor <wft@math.canterbury.ac.nz>