Skip to main content
4 of 4
added 19 characters in body
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

UPD. Formulae corrected.

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^{2n+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^{n+2m-1}-x^{-(m+1)}+x^{n+2m+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^{n+2m-1}-x^{-(m+1)}+x^{n+2m+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^{n+2m-1}-x^{-(m+1)}+x^{n+2m+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+k-2m}+x^{n+2m-k})(px + qx^{-1})^t.$$

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

The expectation can now be computed routinely.

Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152