How does recursion work in stochastics?

Question

How do I justify recursive equations when it comes to solving basic probability/stochastic questions?

(I am attending a basic stochastic/probability class so we can't use measure theory or advanced concepts from probability theory)

One can think for example of questions like

Consider the following gambling game for two players, Black and White. Black puts $b$ black balls and White puts $w$ white balls in a box. Black and White take turns at drawing at random from the box, with replacement between draws until either Black wins by drawing a black ball or White wins by drawing a white ball. Supposed black draws first.

Black wins or continues playing if either he picks a black ball ($p$) or he picks a white ball & then White picks a black ball ($qp$); at this stage he will be faced with exactly the same situation so \begin{eqnarray*} P(B)= p +pq P(B). \end{eqnarray*}

(see How Does Probability Recursion Work?)

After asking our professor mutliple times how to justify the recursive equation the only answers I have received were "the validity of the recursion is intuitive" or "if you take a closer look then it's trivial..." or she simply draws pictures with arrows and assigns probabilties to the arrows... Sure in situations like above it's indeed intuitive but intuition is not a rigorous mathematical argument.

In this easy example it is possible to define a countable probability space that fits the situation. Based on this probability space we can derive the recursive formula that solves the problem by using conditional probabiliteis and the law of total probability.

1.) So I am wondering why did our professor not deem it as necessary to argue like this but using some hand waving arguments?

And more importantly,

2.) What if we face problems that involve a bit more complex recursions where it is not so obvious how to define a proper probability space? How does a sound reasoning for the recursive equation then looks like?

I have the feeling that problems like this can only be solved if one has more tools at hand. Using recursive arguments only hide the problems that arise when it comes to uncountable probability spaces but do not make them disappear...

Any help or feedback is welcome

Answer 1

So this is my perspective on the problem, and I do think the other question seems to provide a reasonable proof. However, I'll take a different approach since maybe the issue is how the initial equation is arrived at. However, this will require linear algebra and this may or may not be satisfying. I do think, to an extent, there is a level of handwaving that is necessary if very little background is assumed. With that disclaimer out of the way...

Suppose there was a really large room, with a large number $N \gg 0$ of these games being executed, turn-by-turn, in parallel. Consider the sequence of proportions of games that continue to run in a given turn as given by

$$P_1, P_2, \ldots, P_k, \ldots,$$

the proportion of games where the player with Black has won given by,

$$B_1, B_2, \ldots, B_k, \ldots,$$

and finally the proportion of games where the player with White has won given by,

$$W_1, W_2, \ldots, W_k, \ldots.$$

Effectively, $B_k$ is the probability of you picking any given game and seeing that the player playing Black had won in the time history of the game prior to turn $k$. Based on the problem description we know that these proportions observe the following recursion,

$$ \begin{aligned} P_{k+1} &= p q P_k\\ B_{k+1} &= p P_k + B_k\\ W_{k+1} &= q^2 P_k + W_k \end{aligned} $$

Explicitly this encodes that,

• the proportion of running games $P_k$ proceeding to the next turn with no winners $P_{k+1}$ is $p q$.
• $p$ percent of those currently running games $P_k$ result in the player playing Black winning.
• $q^2$ percent of those currently running games $P_k$ result in the player playing White winning.
• Those games with winners, i.e. $W_k$ and $B_k$, proceed to stay in that state.

I think this law is clear from the rules of the game, and doesn't rely on anything more. Under the assumption that $q = 1 - p$, you can check that the sum of these proportions stay equal to $1$ so this recursion makes sense. Use a little linear algebra to write this as,

$$ \begin{pmatrix} P_{k+1} \\ B_{k+1} \\ W_{k+1}\end{pmatrix} = \begin{pmatrix} p q & 0 & 0 \\ p & 1 & 0 \\ q^2 & 0 & 1 \end{pmatrix} \begin{pmatrix} P_k \\ B_{k} \\ W_{k}\end{pmatrix} $$

Consider the following question:

If it exists and is non-zero, what is the proportion of game where the player playing Black wins as $k\to\infty$?

That is, what is $B_k$ tend towards as $k\to\infty$? This is simply a discrete recursion and we have to verify (1) it converges, and (2) what it converges to. To aid in this, it helps to find a coordinate change $T$ where the matrix in question becomes diagonal. Define,

$$T = \begin{pmatrix} 1 - pq & 0 & 0\\ -p & 1 & 0 \\ -q^2 & 0 & 1\end{pmatrix}$$

and write

$$Z_k = T^{-1} \begin{pmatrix} P_k \\ B_k \\ W_k \end{pmatrix}$$

Verify that in these new coordinates the previous discrete recursion transforms into,

$$Z_{k+1} = \begin{pmatrix} p q & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} Z_k$$

We can find a closed-form solution to this recursion and clearly the first component of $Z_k$ vanishes as $k\to\infty$ (since $pq < 1$) while the other two components stay constant. As a result, the system converges as $k\to\infty.$ Because the first component of $Z_k$ vanishes as $k \to\infty,$ the last two components of $Z_k$ determine $B_k$ and $W_k$ in the limit. From this fact, deduce that,

$$Z_\infty^2 = B_\infty,\quad Z_\infty^3 = W_\infty,$$

where the superscript indicates the component of that vector and I'm abusing the subscript notation to indicate the limiting value as $k\to\infty.$ Technically, we could also just find the limiting behaviour of $Z_k$ and then use the transformation to figure out what $B_k$ and $W_k$ will tend to. Here I will take the shortcut. So as long as we can figure out how the initial condition,

$$\begin{pmatrix} P_0 \\ B_0 \\ W_0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}$$

is written in $Z$ coordinates, we can compute what $B_\infty$ and $W_\infty$ will be: it will just be the last two components of $Z_0$. Ok, so that means we have to solve the equation,

$$ T Z_0 = \begin{pmatrix} P_0 \\ B_0 \\ W_0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}$$

If you run through the algebra, you will find that the first two equations in this system appear as,

$$\begin{aligned} 1 &= (1 - p q) Z_0^1\\ 0 &= (-p) Z_0^1 + Z_0^2 \end{aligned}$$

Multiply the first equation by $p$ and eliminate $Z_0^1$ to find,

$$ p = -p q Z_0^2 + Z_0^2 $$

You should recognize this equation immediately. Recalling that $B_\infty = Z_0^2,$

$$ p = -p q B_\infty + B_\infty $$

arriving at the critical equation. Solving it yields an answer to aforementioned question. Then it is a matter of arguing why we would consider this "probability of picking a random game and seeing the player playing Black winning" as a measure of "the probability of the player in Black winning".

Note this procedure relies on the initial intuition for the problem setup after which the rest is purely linear algebraic. Here the problem is simple since there is only three game states (one playing, two termination states). You could also do the exact same derivation with four play states or more states if you want, but the result should be same regardless. This approach builds into Markov Theory, and applies as long as you can model it with a Markov Model. It also can generalize to countable number of game states, but one has to be a bit more careful then.

Answer 2

Recursion requires:

1. That you can describe, in some fashion, the state of the system at any given step $n$, $S_n$.

2. That you can relate, in some fashion, how the state of the system at step $n+1$ relates to the state of the system at step $n$, i.e. $S_{n+1} = f(S_n)$. Or more generally, you might need to relate the state to a sequence of previous states, so you have something more like $S_{n+k} = f(S_n, S_{n+1}, \ldots, S_{n+k-1})$.

That's all that recursion is. The above lets you recursively define future states of the system in terms of its past states, and there's usually some number of base states $S_0, S_1, \ldots, S_k$ to kick things off.

A usable recursion also requires that the things in points 1 and 2 are somehow tractable with the tools at your disposal. In the case of the game you described, the states the game can be in are:

1. It's Black's turn.

2. It's White's turn.

3. The game is over and Black has won.

4. The game is over and White has won.

So on turn $n$, the state of the game is going to be one of the above, and each one of those states has a set of probabilities as to how it can transition into another state. For example, states 3 and 4 will stay exactly the same all the time, while state 1 will go to state 3 with probability $p$ (i.e. the probability that Black draws a black ball on their turn) and to state 2 with probability $q$ (i.e. the probability that Black draws a white ball). Then, since 3 and 4 are "stopping" states, we then know that the game has three possible outcomes:

1. $B$: The game eventually reaches state 3 (i.e. Black wins).

2. $W$: The game eventually reaches state 4 (i.e. White wins).

3. $?$: The game never ends, so we go into an infinite loop between states 1 and 2.

We then can talk about the probability of each outcome occurring overall, as well as the probability of it occurring conditional on the state of the game at turn $n$, and we then use the fact that the system is somewhat "memoryless" (i.e. if you're in state $i$ on turn $n$ then the probability of reaching each outcome from this point is the same regardless of $n$) to then construct recursive equations for $P(B), P(W), P(?)$ in terms of each other.

If the system is more complicated, you still do the same basic thing - find formulas relating the evolution of the system from its current state to a future state, and rearrange those to find the explicit formula you're after. That might involve having a bunch of parameters - for example, if the draws in the game were without replacement then your recursive formula will be a function of the number of black and white balls left in the box, so now you've got things like $P(B | b, w)$.

Technically, one thing that sits underneath all of this is an assumption that the things being calculated are well-defined. For example, if I'd omitted the possibility of the game going on forever, then the probabilities of Black and White respectively winning implicitly rely on the game eventually ending. In this case, you can do a bit of algebra to show that the probability of the game lasting until turn $n$ is bound by an exponentially decreasing function in $n$ so you don't actually have to worry about the infinite game, but there are definitely cases where you have to be more careful to note the possible limiting behaviours of $S_n$ as $n \rightarrow \infty$.