413 probability/lights.p
Description
This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.
413 probability/lights.p
Waldo and Basil are exactly m blocks west and n blocks north from
Central Park, and always go with the green light until they run out of
options. Assuming that the probability of the light being green is 1/2
in each direction, that if the light is green in one direction it is
red in the other, and that the lights are not synchronized, find the
expected number of red lights that Waldo and Basil will encounter.
probability/lights.s
Let E(m,n) be this number, and let (x)C(y) = x!/(y! (x-y)!). A model
for this problem is the following nxm grid:
^ B---+---+---+ ... +---+---+---+ (m,0)
| | | | | | | | |
N +---+---+---+ ... +---+---+---+ (m,1)
<--W + E--> : : : : : : : :
S +---+---+---+ ... +---+---+---+ (m,n-1)
| | | | | | | | |
v +---+---+---+ ... +---+---+---E (m,n)
where each + represents a traffic light. We can consider each
traffic light to be a direction pointer, with an equal chance of
pointing either east or south.
IMHO, the best way to approach this problem is to ask: what is the
probability that edge-light (x,y) will be the first red edge-light
that the pedestrian encounters? This is easy to answer; since the
only way to reach (x,y) is by going south x times and east y times,
in any order, we see that there are (x+y)C(x) possible paths from
(0,0) to (x,y). Since each of these has probability (1/2)^(x+y+1)
of occuring, we see that the the probability we are looking for is
(1/2)^(x+y+1)*(x+y)C(x). Multiplying this by the expected number
of red lights that will be encountered from that point, (n-k+1)/2,
we see that
m-1
-----
\
E(m,n) = > ( 1/2 )^(n+k+1) * (n+k)C(n) * (m-k+1)/2
/
-----
k=0
n-1
-----
\
+ > ( 1/2 )^(m+k+1) * (m+k)C(m) * (n-k+1)/2 .
/
-----
k=0
Are we done? No! Putting on our Captain Clever Cap, we define
n-1
-----
\
f(m,n) = > ( 1/2 )^k * (m+k)C(m) * k
/
-----
k=0
and
n-1
-----
\
g(m,n) = > ( 1/2 )^k * (m+k)C(m) .
/
-----
k=0
Now, we know that
n
-----
\
f(m,n)/2 = > ( 1/2 )^k * (m+k-1)C(m) * (k-1)
/
-----
k=1
and since f(m,n)/2 = f(m,n) - f(m,n)/2, we get that
n-1
-----
\
f(m,n)/2 = > ( 1/2 )^k * ( (m+k)C(m) * k - (m+k-1)C(m) * (k-1) )
/
-----
k=1
- (1/2)^n * (m+n-1)C(m) * (n-1)
n-2
-----
\
= > ( 1/2 )^(k+1) * (m+k)C(m) * (m+1)
/
-----
k=0
- (1/2)^n * (m+n-1)C(m) * (n-1)
= (m+1)/2 * (g(m,n) - (1/2)^(n-1)*(m+n-1)C(m)) - (1/2)^n*(m+n-1)C(m)*(n-1)
therefore
f(m,n) = (m+1) * g(m,n) - (n+m) * (1/2)^(n-1) * (m+n-1)C(m) .
Now, E(m,n) = (n+1) * (1/2)^(m+2) * g(m,n) - (1/2)^(m+2) * f(m,n)
+ (m+1) * (1/2)^(n+2) * g(n,m) - (1/2)^(n+2) * f(n,m)
= (m+n) * (1/2)^(n+m+1) * (m+n)C(m) + (m-n) * (1/2)^(n+2) * g(n,m)
+ (n-m) * (1/2)^(m+2) * g(m,n) .
Setting m=n in this formula, we see that
E(n,n) = n * (1/2)^(2n) * (2n)C(n),
and applying Stirling's theorem we get the beautiful asymptotic formula
E(n,n) ~ sqrt(n/pi).
Continue to:
My Books
