# Why this random walk can't go on forever?

$$A$$ starts with $$i$$ coins, $$B$$ with $$N-i$$. At each trial, $$A$$ gives one coin to $$B$$ with probability $$p$$ or $$B$$ gives one coin to $$A$$ with probability $$q$$ where $$p+q=1$$.

This can be modeled as a 2D random walk starting from $$i$$ where probability of moving right = $$p$$, left = $$q$$, and the walk ends at reaching either $$0$$ or $$N$$

Nothing in this statement seems to say that oscillating around i and never reaching either $$0$$ or $$N$$ is not a possibility. However, doing the following calculation, something seems off.

Let $$p_i$$ be the probability that A will end up with all money, that is, the object will reach N, when starting position is $$i$$. $$p_i = p*p_{i+1} + q*p_{i-1}$$ Solving this difference equation gives $$p_i = \frac{1-(\frac{q}{p})^i}{1-(\frac{q}{p})^N}$$ for $$p\neq q$$

Now, P(reaching N starting from $$i$$) = $$p_i$$ By symmetry, P(reaching 0 starting from $$i$$) = $$\frac{1-(\frac{p}{q})^{N-i}}{1-(\frac{p}{q})^N}$$

Adding those together equals 1. Which means either A wins or B wins. That is no probability left for just oscillating around $$i$$ and never reaching either $$0$$ or $$N$$. Why is that so?

The probability for the event, going from i to i+1, then back to i, then i+1 and so on = $$p*q*p*q*... = (pq)^n$$ where n can go up to infinity. However small, this is a positive number. And unless n goes to infinity, it is greater than zero.

I understand that $$\lim_{n \to \infty} (pq)^n = 0$$. But how is that applicable here. As $$n \to \infty$$, probability $$\to 0$$. But $$n$$ is always less than $$\infty$$, so probability is always greater than $$0$$. Please tell me if I am wrong with my interpretation of limits.

Is it correct that either A or B has to win? Why?

• Hint: try to calculate the duration $T$ of the game, i.e. the number of steps it takes for the "walker" to reach $x=0$ ($T_{0}$) or x = $N$ ($T_{N}$). The $T$'s are, of course, random variables, accompanied with corresponding distribution functions. Start with the simplest non trivial case, $N=3$, $i=1$. You can even simplify things letting $N\to\infty$ which then amounts to calculate the probability that the "walker" which has started at $x=i$ will reach $x=0$. – Dr. Wolfgang Hintze Nov 8 at 14:34
• @Dr.WolfgangHintze Time $T$ taken to reach $0$ while assuming $N \to \infty$ for simplicity, has a distribution. It can be arbitrarily but finitely large. But how does that mean, in the "end", the walker has to come to $0$. For every possible value of T, there is a small but positive probability that the walker has not come to zero until T. Therefore, for every finite duration of the game, there is a probability left for the event that walker has not come to $0$. – sourav goyal Nov 8 at 16:16
• This seems more like a question about interpretation of limits, now. – sourav goyal Nov 8 at 16:19
• The probability of oscillating forever is 0. That does not mean it is impossible, just that it's likelihood is smaller than any positive real number. For a simpler example, the probability of rolling a coin repeatedly and getting tails every time, forever, is 0, but it's not impossible. – Ned Nov 9 at 0:43
• @ sourav goyal Please consider: I have given you the first answer here yesterday, and I would have expected a response, instead of seing acceptance of a later very similar answer. – Dr. Wolfgang Hintze 2 days ago

This seems to be a question about the meaning of limits. I think the following much simpler example captures all the issues.

Suppose you flip a fair coin again and again, and consider the event that all results are Heads. Clearly $$Prob(first\ N\ are\ all\ Heads) = p_N = {1 \over 2^N}$$. The following statements are all true and not contradictory:

• For any finite $$N, p_N > 0$$.

• $$lim_{N \rightarrow \infty} \ p_N = 0$$.

• Suppose you lose when the first Tail shows up. The event $$E$$ that you don't lose is non-empty, i.e. $$E \neq \emptyset$$, or equivalently, there exists a sample point (namely, all Heads forever) where you don't lose. However $$P(E) = 0$$ (or equivalently, $$P(lose) = 1$$).

• $$E \neq \emptyset$$ and yet $$P(E)=0$$ is not that surprising. After all, the sample space contains an infinite number of sample points (all infinitely-long sequences of H/T, i.e. $$\{H,T\}^\infty$$). This kind of thing happens all the time with continuous random variables. E.g. if $$X = Uniform(0,1)$$ then $$P(X=0.1) = 0$$ even though it is clearly a non-empty event.

Back to your example, the analogous $$E =$$ the set of sample points where the random walk never reaches either boundary (more precisely, $$\forall t$$ the position at $$t \neq$$ either boundary). Clearly $$E \neq \emptyset$$, but you have also shown that $$P(E)= 0$$.

Does this help, or at least, help to distill the issue?

• This is exactly what I was looking for. $P(E)=0$ even when $E\neq\emptyset$. In the cases where a sample point, that is, a sequence of HT.. in your example, can be of arbitrarily large length, To calculate $P(E)$, one has to take a limit $n\to\infty$ . It seems rather stupid, but I ask why do we take limits. If n approaches $\infty$ but never reaches $\infty$, Why doesn't it mean $P(E)$ approaches $0$ but never reaches $0$? Shouldn't we say $\lim P(E) = 0$ instead of $P(E)=0$? – sourav goyal Nov 9 at 18:57
• The $P(X=0.1) = 0$ for $X=Uniform(0,1)$ example is very illuminating. – sourav goyal Nov 9 at 18:59
• To be precise, we have to define the sample space. I'd prefer to define it as $\{H,T\}^\infty$, in which case $H^\infty$ is a valid sample point. Now $P()$ is a probability which means it maps Events to $[0,1]$. For the event $E = \{H^\infty\}$, we have $P(E)=0$. $N$ doesnt even figure into this discussion. A different event is $E_N = \{H^N + \{H,T\}^\infty\}$ i.e. the first $N$ flips are heads. This has $P(E_N) = 1/2^N$. Note that every sample point in $E_N$ is still infinitely long (and therefore each individual pt's $P=0$). – antkam Nov 9 at 19:22
• (cont'd) My point is $P(E)$ has to be a number, in $[0,1]$... that is what probability $P()$ does. (Alternatively, you can take the view that $E$ is not a valid event, so that $P(E)$ is undefined.) And if $P(E)$ is a number, then $\lim_{N\rightarrow \infty} P(E)$ is just the same number since $P(E)$ doesnt even depend on $N$. – antkam Nov 9 at 19:27
• BTW, since every real number has a binary expansion, the $Unif(0,1)$ example is actually very analogous with $\{H,T\}^\infty$. (It'd be an exact bijection if not for the fact that $0.011111... = 0.100000...$.) – antkam Nov 9 at 19:32

Your problem can be visualized and explained with the most simple case.

Take $$N=3$$, $$p=q=\frac{1}{2}$$, for simplicity. $$t$$ is the running time (or step number), and $$T$$ is the duration, i.e. the time $$t$$ at which either $$x(t)=0$$ or $$x(t)=3$$.

Let the walker start at $$x=1$$ i.e. $$x(t=0) = 1$$.

For $$t=1$$ there are two possibilities, $$x(1) = 0$$ which gives $$T=1$$ with probability $$p$$, and $$x(1) = 2$$ with probability $$p$$.

In the next time step we have $$x(2)=3$$, i.e. $$T=2$$ with probability $$p^2$$, and $$x(2)=1$$ with prob. $$p^2$$. For $$t=3$$ we have $$x(3)=0$$ giving $$T=3$$ with prob $$p^3$$, and so on.

Generally, the probability that the game ends at time $$t=T$$ is $$w(T) = 2^{-T}$$. The average duration is hence $$T_{ave}=\sum_{T=1}^\infty T 2^{-T} = 2$$

Hence the result is that the walk can be aribitrarily long but the probability decreases with increasing length in a manner that the average length is (only) 2.

Remark: if we drop the assumption $$p=q$$ then the probability for a duration $$T$$ is given by

$$w(T) = \left\{ \begin{array} (p^{\frac{T-1}{2}} q^{\frac{T+1}{2}} & T \;\text{odd}, T\ge1 \\ p^{\frac{T+2}{2}} q^{\frac{T-2}{2}} & T \; \text{even}, T\ge2 \\ \end{array} \right.$$

and the average is given by

$$T_{ave} = \frac{p+1}{1-p q}$$

The formula is not symmetric in $$p$$ and $$q$$. This was not to be expected since the walker started at the unsymmteric point $$x=1$$.

• What you are saying is totally right. However, you didn't answer why the probability of infinite length is zero. I understand that it decreases. My question was why does it go to zero. – sourav goyal 2 days ago
• Honestly, that $2^{-T}$ goes to $0$ for $T\to\infty$ was all too obvious to be mentioned. – Dr. Wolfgang Hintze yesterday