Random Walk with Edges

Question

The setup for the specific problem that led to this question is as follows:

You are playing a game at a casino and have \$10,000; The bank has \$2,000. You are making \$1,000 bets, with a equal payout. You play until either you or the bank run out. What is the probability that you will be the one to run out, versus the bank, and what is the distribution for the path lengths in either case?

The way I interpret it is that this is a random walk that is biased in one direction, with the added factor that if it reaches either end it will stay there permanently.

In addition to just solving the problem, I would like to find out what the general solution is for this, and how you would find it.

The state diagram for a smaller instance of the problem with the start location in the middle would be the one here, where $a$ is the probability of losing and $b$ that of winning ($b=1-a$).

$$0 \overset{a}{\leftarrow} 1 \overset{a}{\underset{b}\leftrightarrows} 2 \overset{a}{\underset{b}\leftrightarrows} 3 \overset{a}{\underset{b}\leftrightarrows} 4 \overset{a}{\underset{b}\leftrightarrows} 5 \overset{b}{\rightarrow} 6$$

Assuming I am starting at 3, the probabilities for being in each state after some number of iterations follow an interesting pattern

$$\begin{matrix} \text{Iterations } (i)&\text{0}&\text{1}&\text{2}&\text{3}&\text{4}&\text{5}&\text{6}\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & a & 0 & b & 0 & 0 \\ 2 & 0 & a^2 & 0 & 2ab & 0 & b^2 & 0 \\ 3 & a^3 & 0 & 3a^2b & 0 & 3ab^2 & 0 & b^3 \\ 4 & a^3 & 3a^3b & 0 &6a^2b^2 & 0 & 3ab^3 & b^3 \\ 5 &a^3+3a^4b & 0 &9a^3b^2& 0 &9a^2b^3& 0 &b^3+3ab^4 \\ 6 &a^3+3a^4b &9a^4b^2& 0 &18a^3b^3& 0 &9a^2b^4&b^3+3ab^4 \\ 7 &a^3+3a^4b+9a^5b^2& 0 &27a^4b^3& 0 &27a^3b^4& 0 &b^3+3ab^4+9a^2b^5\\ \end{matrix}$$

It starts out looking like a binomial expansion, but after a few rows the ends begin siphoning away stuff from the tree, changing it. It is especially interesting to examine a table like this from an asymetric one, like the original problem, but there isn't enough space here to show it.

Particularily, I can't seem to be able to find the general term for the probabilities from each column. I know that for a regular binomial expansion,you can use combinations $\binom{n}{r}$ and get a general term, but I can't figure out how you modify that for my case.

I did figure out the general term for the small case ends (at least after step 3). Here is the left one: $$\sum_{n=0}^{\frac{i}{2}-1} 3^na^{n+3}b^n$$

So,

1. What is the general term for the pattern described above for the more general case (with variable width and start position)?
2. How would I find the probability distributions for the number of iterations required to reach each end state?

Answer 1

For 2, in a fair game the player will win $\frac {10}{12}$ of the time. As the game is fair, the expectations must be equal to the initial bankrolls, so the winning probabilities are in proportion to the initial bankrolls. Not as obvious is that the expected length of the game is $20$, the product of the number of bets each has in the initial bankroll.

If the game is unfair, the formulas for winning percentages are given in Wikipedia with a justification.

Answer 2

The idea is to compute these quantities simultaneously for every starting point. Assuming that the game stops at $0$ and $n$, call $u_i$ the probability that the game stops at $n$ and $t_i$ the number of steps necessary to reach $0$ or $n$, in both cases starting at $i$, for every $0\leqslant i\leqslant n$.

Then $u_0=t_0=t_n=0$, $u_n=1$, and, considering what happens during the first step of the random walk, one gets $u_i=au_{i-1}+bu_{i+1}$ and $t_i=1+at_{i-1}+bt_{i+1}$ for every $1\leqslant i\leqslant n-1$. These are Cràmer systems of size $n+1$, to be solved.