A Neurotic Bug

Let us analyze this two-state Markov chain. Our main goal is to find a closed formula for the probability that the bug is at vertex A after having crawled $n$ meters.

Let $p_n=\frac{1}{4}+d_n$ be the probability that the bug finds itself at vertex $A$ after having traveled $n$ meters, where $\frac{1}{4}$ is the equilibrium state and $d_n$ is the deviation from the equilibrium. The probability that the bug isn't at $A$ after having traveled $n$ meters is $q_n=\frac{3}{4}-d_n$ so that $p_{n+1}=\frac{q_n}{3}=\frac{1}{4}-\frac{d_n}{3}$ . (The probability is 1/3 that the bug travels from a point other than $A$ to $A$ .) Note that $d_{n+1}=-\frac{d_n}{3}$ . Starting from $p_1=0=\frac{1}{4}-\frac{1}{4}$ , we find that $d_n=\frac{(-1)^n}{4*3^{n-1}}$ and $p_n=\frac{1}{4}+d_n=\frac{1}{4}\left(1+\frac{(-1)^n}{3^{n-1}}\right)$ In particular, we have $p_7=\boxed{\frac{182}{729}}$ .

For full disclosure: I copied this solution from here , where the same problem was posed.

For n = 0,1,2,..., let $a_n$ be the probability that the bug is at vertex A after crawling exactly n meters. Then we have the recursive relation $a_{n+1}$ = $\frac{1}{3}(1 -a_n)$ , _ _ (1)

because the bug can be at vertex A after crawling n + 1 meters if and only if

(a) it was not at A following a crawl of n meters (this has probability $1-a_n$ ) and

(b) from one of the other vertices it heads toward A (this has probability $\frac{1}{3}$ .

Now, since $a_0$ = 1 (i.e., the bug starts at vertex A), from the recursive relation (1), we have $a_1 = 0$ , $a_2 = \frac{1}{3}$ , .... , and the desired probability is p = $a_7 = \frac{182}{729}$

Now p=182, q=729 yields p+q=911.

911 is also the 'Emergency' number of many countries including India and the U.S.A. (Hence the title.)