Skip to main content
2 of 4
style
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

Second approach, which follows the ideas from this answer to other question.

Consider the game as a random walk on the real line, starting at vertex $n$ and making steps +1 with probability $p$ and $-1$ with probability $q=1-p$. To answer the question, we need to find the probabilities of the following outcomes:

  1. Path of length $\ell\leq t$ from $n$ to $n+m$, not visiting $0$ and not visiting $n+m$ except at the end.

  2. Path of length $\ell\leq t$ from $n$ to $0$, not visiting $n+m$ and not visiting $0$ except at the end.

  3. Path of length $t$ from $n$ to $k$, where $0<k<n+m$, not visiting $0$ or $n+m$.


  1. First, we notice that the probability of a path of length $\ell-1<t$ from $n$ to $n+m-1$, not visiting $0$, equals

$$[x^{n+m-1}]\ x^n (px + qx^{-1})^{\ell-1} - [x^{-(n+m-1)}]\, x^n (px + qx^{-1})^{\ell-1}$$ $$=[x^0]\ (x^{-(m-1)}-x^{m-1})(px + qx^{-1})^{\ell-1}$$

Second, the probability of a path of length $\ell-1<t$ from $n$ to $n+m-1$, not visiting $0$ and $n+m$, equals $$[x^0]\ (x^{-(m-1)}-x^{m-1}-x^{-(m+1)}+x^{m+1})(px + qx^{-1})^{\ell-1}$$

Finally, the probability of a path of length $\ell\leq t$ from $n$ to $n+m$, not visiting $0$ and not visiting $n+m$ except at the end, equals $$p\cdot [x^0]\ (x^{-(m-1)}-x^{m-1}-x^{-(m+1)}+x^{m+1})(px + qx^{-1})^{\ell-1}$$

For all these paths the capital at the end is $n+m$ and their contribution to the expectation is given by the sum over $\ell=1,\dots,t$, i.e., $$(n+m)p\ [x^0]\ (x^{-(m-1)}-x^{m-1}-x^{-(m+1)}+x^{m+1})\frac{1-(px + qx^{-1})^t}{1-(px + qx^{-1})}$$

  1. The probability of such paths can be computed similarly, but their contribution to the capital expectation is zero.

  2. Similarly, the probability of a path of length $t$ from $n$ to $k$, where $0<k<n+m$, not visiting $0$ or $n+m$, equals $$[x^0]\ (x^{n-k}-x^{-(n-k)}-x^{-(n+2m-k)}+x^{n+2m-k})(px + qx^{-1})^t.$$

Their contribution is given by $$[x^0]\ \sum_{k=1}^{n+m-1} k(x^{n-k}-x^{-(n-k)}-x^{-(n+2m-k)}+x^{n+2m-k})(px + qx^{-1})^t$$ $$=[x^0]\ x\frac{x^{n+2m}-x^{-(n+2m)}+(n+m)(x^{-(m+1)}-x^{m+1}+x^{m-1}-x^{-(m-1)})+x^n-x^{-n}}{(1-x)^2}(px + qx^{-1})^t.$$

The expectation can now be computed routinely.

Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152