A frog is jumping on $N$ stones which are numbered from $1$ to $N$ from left to right. The frog is jumping to the previous stone (to the left) with probability $p$ and is jumping to the next stone (to the right) with probability $1-p$. If the frog has jumped to the left from the leftmost stone or to the right from the rightmost stone, it will fall into the water. The frog is initially on the leftmost stone. If $p< \tfrac 13$, show that the frog will fall into the water from the rightmost stone with a probability higher than $\tfrac 12$.
Problem
Source:
Tags: probability, algebra proposed, algebra
modularmarc101
13.03.2011 23:17
Let $T_k$ denote the probability that the frog will eventually fall into the water from the rightmost stone when the frog is at stone $k$, where $T_k=0$ for $k=0$ and $T_k=1$ for $k \geq n+1$. Then, we find the following recursive relation: \[ T_k = pT_{k-1} + (1-p)T_{k+1} \ \text{with} \ T_0 = 0, T_{n+1}=T_{n+2}=... = 1 \] or, equivalently, \[ T_{k+1} = \frac{1}{1-p} T_k - \frac{p}{1-p}T_{k-1} \]. We have that the characteristic equation of this sequence is $\lambda^2 - \frac{1}{1-p} \lambda + \frac{p}{1-p} = 0$, which implies that $\lambda_1 = 1$ and $\lambda_2 = \frac{p}{1-p}$. Hence, \[ T_k = (\frac{p}{1-p})^k c_1 + c_2 \\ \] for some constants $c_1,c_2$. Now, we notice that $T_1 = (1-p)T_2$, so \[ \frac{p}{1-p} c_1 + c_2 = (1-p)[ (\frac{p}{1-p})^2c_2 + c_2) \\ \\ pc_2 = \frac{p(p-1)}{1-p}c_1 \\ \\ c_2 = -c_1 \\ \\ \implies T_k = c_1 [ (\frac{p}{1-p})^k - 1] \] Also, we use the fact that $T_{N} = pT_{N-1} + (1-p)$: \[ c_1 [ (\frac{p}{1-p})^N - 1] = pc_1 [ (\frac{p}{1-p})^{N-1} - 1] + (1-p)\\ \\ c_1[ p^N - (1-p)^N] = c_1[ p^N(1-p)- p(1-p)^N] + (1-p)^{N+1} \\ \\ c_1[ p^{N+1} - (1-p)^{N+1} ] = (1-p)^{N+1} \\ \\ c_1 = \frac{(1-p)^{N+1} }{p^{N+1} - (1-p)^{N+1}} \\ \\ \implies T_k = \frac{(1-p)^{N+1} }{p^{N+1} - (1-p)^{N+1}} [ ( \frac{p}{1-p})^k - 1] \\ \\ \implies \boxed{T_k =\frac{(1-p)^{k+N+1} - p^k(1-p)^{N+1}}{ (1-p)^{k+N+1} - p^{N+1}(1-p)^k} }\\ \] Finally, we show that $T_1 > \frac{1}{2}$, or \[ \frac{(1-p)^{N+2} - p(1-p)^{N+1}}{(1-p)^{N+2} - p^{N+1}(1-p)} > \frac{1}{2} \\ \\ \iff \frac{(1-p)^{N+1} - p(1-p)^{N}}{(1-p)^{N+1} - p^{N+1}} - \frac{1}{2} > 0 \\ \\ \iff \frac{2(1-p)^{N+1} - 2p(1-p)^{N} - (1-p)^{N+1} + p^{N+1} }{2(1-p)^{N+1} - 2p^{N+1}} > 0\\ \\ \iff \frac{(1-p)^{N+1} - 2p(1-p)^{N} + p^{N+1} }{ 2(1-p)^{N+1} - 2p^{N+1} } > 0 \\ \\ \iff \frac{(1-p)^{N} (1-3p) + p^{N+1}}{2(1-p)^{N+1} - 2p^{N+1} } > 0 \] which is true, since $p < \frac{1}{3}$ (the denominator is positive because $(1-p)^{N+1} > p^{N+1}$ and the numerator is positive because both $(1-p)^N (1-3p)$ and $p^{N+1}$ are positive). Q.E.D.
Batominovski
14.03.2011 15:24
modularmarc101 wrote: \[ T_k = pT_{k-1} + (1-p)T_{k+1} \ \text{with} \ T_0 = 0, T_{n+1}=T_{n+2}=... = 0 \] Just wonder. Why didn't you set $T_{N+1}=1$, when $T_{N+1}$ is indeed the probability that the frog falls into the water from the rightmost stone, when it is already in the water there!?!
modularmarc101
15.03.2011 01:07
Yeah, that makes more sense. I fixed it .