Alice starts in the middle of a 5 foot pole. There are n other ants placed randomly on the pole and they start scampering in random directions with constant speed of 1 inch per second. Alice has a cold. When an ant with a cold bumps into another ant, the uninfected ant catches a cold too. What is the expected number of ants who catch cold before they all fall off the pole?
This puzzle is from http://www.cs.cmu.edu/puzzle/solution9.pdf
I know this has a solution inbuilt in it but I cannot figure out why P(X=0) = $(3/4)^n$, X being the number of ants on the right of Alice that move left.
I thought that it would be $\sum_{0,n-1} P(X=0|a_i)*(P(a_i))$, where ai is the number of ants on the right side of Alice. So, P(ai) [the prob that ai ants are on right of Alice] = $(C(n-1,a_i))/2^{n-1}$, and thus the value is $(1/2)^{n-1} * (C(n-1,0) (1/2)^{0} + C(n-1,1) (1/2)^{1} ... )$ thus giving $3^{n-1}/4^{n-1}$, thus I am confused.