How do we justify certain steps in the solution to gambler's ruin?

Question

The problem of gambler's ruin asks the following: suppose a player begins with $k$ units of money, $0<k<N$. Each turn he flips a coin and either gains a unit of money with probability $p$ or loses a unit of money with probability $1-p$. The game ends when he reaches $N$ and wins or $0$ in which case he loses the game. What is the probability of losing?

The usual solution, which you can find for example on http://en.wikipedia.org/wiki/Gambler%27s_ruin or in Grimmett & Stirzaker - Probability and Random processes, page 17, proceeds by constructing a linear difference equation using the fact (using the notation from wikipedia) that $P(R_n|H)=P(R_{n+1})$ where $R_n$ is the event "that the player is ruined having started with $n$ units of money" and $H$ is the event "of winning the first flip".

What event exactly is $R_n$? Is it correct to consider $H$ to be a single event or should we take a separate event for every coin flip?

The approach taken by Grimmett and Stirzaker seems conceptually the same, but instead of using a single probability measure, they use $P_k$ - the probabilities calculated relative to the starting point $k$. Then they use the equation $P_k(A) = P_k(A|B)P(B) + P_k(A|B^C)P(B^C)$, where A is the event of losing the game and B is the event of winning the first flip. I am not completely sure what they mean by $P$, my best guess is that because the probability of $B$ is independent of $k$, they just drop the index. Next they use the fact that $P_k(A|B) = P_{k+1}(A)$ which looks essentially as expressing the same relation as the equation with $R_n$ before.

Anyway, I haven't been able to completely justify this relation theoretically, so here comes my main question:

How exactly do we justify $P(R_n|H)=P(R_{n+1})$ and $P_k(A|B) = P_{k+1}(A)$?

I have tried translating this problem to a more familiar measure-theoretical language, using $\Omega = \lbrace-1,1\rbrace^\mathbb{N}$ as the underlying sample space and defining $M:\lbrace-1,1\rbrace^\mathbb{N}\times\mathbb{Z}\to\mathbb{N}\cup\lbrace\infty\rbrace,$ $M(f,k) = \min\lbrace m\in\mathbb{N}|\sum_{i=1}^m f(i) = k \rbrace$ (where $\min\emptyset := \infty$), which then enables us to define $R_n = \lbrace f\in\Omega|M(f,-n) < M(f,N-n)\rbrace$ and $H = \lbrace f\in\Omega|f(1) = 1\rbrace,$ but this hasn't given me any new intuition and may not even be the correct formalization.

It seems increasingly likely that I am missing some implicit assumption in the statement of the problem that is obvious to probabilists but not so much to me ... In this case:

What exactly is this assumption?

Answer 1

David gives the probabilistic perspective, which is the most useful way of thinking about problems like this once you're confident that you could reason about them formally. Terence Tao's excellent review of probability theory discusses the "probabilistic way of thinking" (and contains much other goodness besides).

Your formalisation works (you just need to define a measure for it to be complete).

How exactly do we justify $P(R_n|H)=P(R_{n+1})$ and $P_k(A|B)=P_{k+1}(A)$?

If we were to go line by line, it would look like this:

$\begin{align} \mathbb{P}[R_n|H] &= \mathbb{P}[\lbrace f\in\Omega|M(f,-n) < M(f,N-n)\}|f(1)=1]\\ &= \mathbb{P}[\lbrace f\in\Omega|\min\{m\in\mathbb{N}|\sum_{i=2}^m f(i)=-n-1\} < \min\{m\in\mathbb{N}|\sum_{i=2}^m f(i)=N-n-1\}| f(1)=1]\\ &= \mathbb{P}[\lbrace f\in\Omega|\min\{m\in\mathbb{N}|\sum_{i=2}^m f(i)=-n-1\} < \min\{m\in\mathbb{N}|\sum_{i=2}^m f(i)=N-n-1\}]\\ \end{align}$

, since $f(1)=1$ and $\lbrace f\in\Omega|\min\{m\in\mathbb{N}|\sum_{i=2}^m f(i)=-n-1\} < \min\{m\in\mathbb{N}|\sum_{i=2}^m f(i)=N-n-1\}$ are independent events.

$\begin{align} \mathbb{P}[R_n|H]&= \mathbb{P}[M((f(2),f(3),\cdots),-n-1)<M((f(2),f(3),\cdots),N-n-1)]\\ &= \mathbb{P}[M((f(1),f(2),\cdots),-(n+1)) < M((f(1),f(2),\cdots),N-(n+1))]\\ &=\mathbb{P}[R_{n+1}] \end{align} $

The penultimate line follows because the sequences $(f(1),f(2),\cdots)$ and $(f(2),f(3),\cdots)$ have the same distribution.

Answer 2

$R_n$ is simply the event that the gambler starts with $n$ units of money, plays the game, and loses (that is loses all his money). $H$ is indeed the event that the gambler wins on the first flip, thus increasing his fortune by 1 (and allowing him to continue playing).

This is the reason why $P(R_n|H)=P(R_{n+1})$. Given the event $H$, the gambler increases his fortune by 1; and at this point, it's as if he had just started playing the game with a fortune of $n+1$ units of money. So, the probability that he loses the game starting with $n$ units of money, given that he wins the first flip, is exactly the same as the probability that he loses the game starting with $n+1$ units of money.

I'm not quite sure what $P_k$ represents (what do you mean by "relative to the starting point"?), but I suspect similar reasoning will establish its formula.