$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?

  • $\begingroup$ 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$. $\endgroup$ – Dr. Wolfgang Hintze Nov 8 '18 at 14:34
  • $\begingroup$ @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$. $\endgroup$ – sourav goyal Nov 8 '18 at 16:16
  • $\begingroup$ This seems more like a question about interpretation of limits, now. $\endgroup$ – sourav goyal Nov 8 '18 at 16:19
  • $\begingroup$ 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. $\endgroup$ – Ned Nov 9 '18 at 0:43
  • $\begingroup$ @ 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. $\endgroup$ – Dr. Wolfgang Hintze Nov 11 '18 at 16:53

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?

  • $\begingroup$ 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$? $\endgroup$ – sourav goyal Nov 9 '18 at 18:57
  • $\begingroup$ The $P(X=0.1) = 0$ for $X=Uniform(0,1)$ example is very illuminating. $\endgroup$ – sourav goyal Nov 9 '18 at 18:59
  • $\begingroup$ 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$). $\endgroup$ – antkam Nov 9 '18 at 19:22
  • $\begingroup$ (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$. $\endgroup$ – antkam Nov 9 '18 at 19:27
  • $\begingroup$ 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...$.) $\endgroup$ – antkam Nov 9 '18 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$.

  • $\begingroup$ 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. $\endgroup$ – sourav goyal Nov 11 '18 at 19:44
  • $\begingroup$ Honestly, that $2^{-T}$ goes to $0$ for $T\to\infty$ was all too obvious to be mentioned. $\endgroup$ – Dr. Wolfgang Hintze Nov 13 '18 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.