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.

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: