# Random walk length and maximum

The following a gambling game:

We have a sequence of i.i.d. random variables, $X_1, X_2, \dots,$ with $P(X_n=1)=p, P(X_n=-1)=1-p, p<1/2$. A game is played by generating a sequence of realizations of the X's. The game ends when a sequence of $k$ (a given parameter) consecutive "losses" is first encountered. For example if $k=4$ a possible game would be

$$(1,1,-1,1,-1,-1,-1,1,-1,1,-1,-1,-1,-1)$$

All sequences of consecutive losses have length at most 3 except one which has length 4 and is at the tail.

We know for sure that the game will end in a finite time. Question is now what's the distribution of the game time and what's the distribution of the maximum of the partial sums of the X's over the game duration.

I've done some poking around with this using recurrence relations but didn't quite crack it. For $k=1$ the game is a series of "wins" until the first "loss". In this case $T$ (the game time) is given by the geometric distribution. Is there a generalization of that for $k>1$ ?

All ideas appreciated.

EDIT:

Can we find the probability that a sequence of $t$ trials does not contain a $m$ losing streak ? We could take it from there

This only deals with the distribution for when the game ends, not with the partial sums:

I do not think you need $p \le \frac12$, and in any case you are only almost sure in a probability $1$ sense that the game will end in a finite time

The recurrence for the probability $q_n$ that the game ends after $n$ moves is not too complicated:

$$q_n = p \left(q_{n-1} + q_{n-2}(1-p) + q_{n-3}(1-p)^2 + q_{n-4}(1-p)^3 \right)$$

starting with $q_0=q_1=q_2=q_3=0$ and $q_4=(1-p)^4$

though this is not going to be a common distribution: $q_n$ is weakly decreasing from a mode at $q_4=(1-p)^4$, but $q_5=q_6=q_7=q_8=p(1-p)^4$ are all equal, as show in the illustration below

The expected number of steps until you stop is $\sum nq_n$ which with some manipulation is $$4+\dfrac{p \left(1 + 2(1-p) + 3(1-p)^2 + 4(1-p)^3 \right)}{1-p \left(1 + (1-p) + (1-p)^2 + (1-p)^3 \right)} = \dfrac{(2-p)(2-2p+p^2)}{(1-p)^4}$$

So for example if $p=\frac13$ this gives an expected time to stop of $\frac{195}{16} = 12.1875$ and the start of the distribution from $q_1$ up to $q_{20}^{\,}$ looks like this, with the tail then continuing to the right with $q_n$ marginally less than $0.9 q_{n-1}$ for $n\ge 16$

Thanks for your reply! In the case $k=4$ I presume. Is it possible to generalize to any $k$? Say $Y=$ number of trials (successes and failures) until k consecutive successes. I just came across a paper where they state the probability generating function of $Y$ as

$$G(t)=\frac{p^k(1-pt)t^k}{1-t+qp^kt^{k+1}},$$

the "geometric distribution of order $k$". And then mathematica will crunch out the series I guess.