First step analysis¶

First step analysis is a general strategy for solving many Markov chain problems by conditioning on the first step of the Markov chain.

We understand this from the first example of the book Stochastic Calculus and Financial Applications¹. We will derive a recurrence⁴ relationship of the probability of a gambler winning before he goes bankrupt, and find the expected time taken for the game to end.

Problem setup¶

A gambler starts with a principal of \( 0 \), and he can borrow a maximum of \( b \). He stops playing if his net value is \( a \) at any point of time. At each instant \( i \), his wealth \( S_i \) either increases or decreases by one amount depending on the output of the Bernoulli random variable \( X_i \) with up probability \( p \). This gives rise to the finite state space \( 𝒮 = \bcrl{-b, -b + 1, …, 0, …, a - 1, a} \). Note that \( (S_n) \) is a time-homogeneous Markov chain on \( 𝒮 \) with transition probabilities as follows:

• \( P_{-b, j} = P_{a, j} = 0 \) (absorbing barriers),
• \( P_{i, i + 1} = p \) and \( P_{i, i - 1} = q \) with \( q = 1 - p \), and
• \( P_{i, j} = 0 \) in all other cases.

Some interesting questions are as follows.

1. What is the probability that the gambler wins?
2. What is the expected time for the game to finish?

In order to answer these questions, we define the following.

• \( τ = \inf\bcrl{n ≥ 0 ∣ S_n = a \text{ or } S_n = -b} \) is the exit time.
• \( f(k) = ℙ\bcrl{S_τ = a ∣ S_0 = k} \) for \( k ∈ 𝒮 \) is the probability that the gambler wins if they start with a principal of \( k \).
• \( g(k) = 𝔼\brnd{τ ∣ S_0 = k} \) for \( k ∈ 𝒮 \) is the mean exit time if the gambler start with a principal of \( k \).

Note that we can write \( f(k) = ℙ\bcrl{S_τ = a ∣ S_0 = k} = ℙ_{\bcrl{S_0 = k}} \bcrl{S_τ = a} \), where \( ℙ_{\bcrl{S_0 = k}} \) is the conditional probability measure.

Aim 1: Calculate the winning probabilities¶

Aim 1a: Obtain a recursive formula for \( f \)¶

Note that \( f(-b) = 0 \) and \( f(a) = 1 \); these serve as our boundary conditions. Now

and so

where we have used the Markov property in the penultimate step and time-homogenity in the ultimate step.

Since \( P_{k, l} = 0 \) for all \( l \) except for \( k ± 1 \), we obtain the recursive formula

Aim 1b: Obtain a closed-form formula for \( f \)¶

Let us denote by the odds of a down movement \( o_- = \frac{q}{p} \). Then using the fact that \( p + q = 1 \), the recursive formula \eqref{eq:f-recursive} gives \( (p + q) f(k) = p f(k + 1) + q f(k - 1) \), which is equivalent to

and gives us the useful relation

Let \( α = Δf(-b) \). Then \( Δf(-b + j) = o_-^j Δf(-b) \). Now using the lower boundary conditions, we get

where we substituted \( j = b + i \) in the second step. Therefore, we have

Using the upper boundary condition \( f(a) = 1 \), we determine \( α \) to be the inverse of the coefficent of \( α \) in \eqref{eq:f-prelim} with \( k = a \) in both cases. Combine this with \eqref{eq:f-prelim} to finally obtain

Aim 2: Calculate the mean exit times¶

Aim 2a: Obtain a recursive formula for \( g \)¶

Since \( g(-b) = g(a) = 0 \), we can ignore those cases as they will not contribute to the expectation. These also serve as our boundary conditions. So we assume \( k ∉ \bcrl{-b, a} \), and take one step. Just like in the case of \( f \), we have

In our particular case, this gives the recursive formula

Aim 2b: Obtain a closed-form formula for \( g \)¶

Let us try to apply the same idea as we had used for \( f \). We get

This does not look as simple as the last time. What can we do? Since we have a constant term, let us try to apply the difference operator again to remove it. <!-- We get

which is exactly the kind of formula that we were looking for. -->

References¶

This note is partially based on the following resources.

Comments