Stochastic Process and Stochastic Calculus

In this chapter, we cover a few topics—Markov chain, random walk and martingale, dynamic programming—that are often not included in introductory probability courses. Unlike basic probability theory, these tools may not be considered to be standard requirements for quantitative researchers/analysts. But a good understanding of these topics can simplify your answers to many interview problems and give you an edge in the interview process. Besides, once you learn the basics, you’ll find many interview problems turning into fun-to-solve math puzzles.

5.1 Markov Chain

A Markov chain is a sequence of random variables $X_0,X_1,\cdots,X_n,\cdots$ with the Markov property that given the present state, the future states and the past states are independent:

for all $n,i_0,\cdots,i_{n-1},i,$ and $j$, where $i,j\in\{1,2,\cdots,M\}$ represent the state space $S=\{s_1,s_2,\cdots,s_M\}$ of $X$.

In other words, once the current state is known, past history has no bearing on the future. For a homogenous Markov chain, the transition probability from state $i$ to state $j$ does not depend on $n$.¹ A Markov chain with $M$ states can be completely described by an $M\times M$ transition matrix $P$ and the initial probabilities $P(X_0)$.

Transition matrix:

where $p_{ij}$ is the transition probability from state $i$ to state $j$.

Initial probabilities:

The probability of a path:

Transition graph: A transition graph is often used to express the transition matrix graphically. The transition graph is more intuitive than the matrix, and it emphasizes 106possible and impossible transitions. Figure 5.1 shows the transition graph and the transition matrix of a Markov chain with four states:

$$\begin{array}{rcl}&\begin{array}{rrrr}i=1&2&3&4\end{array}&j=\\ P=&\begin{bmatrix}0&0.5&0&0.5\\0.5&0&0.25&0.25\\0&0.4&0.4&0.2\\0&0&0&1\end{bmatrix}&\begin{array}{c}1\\2\\3\\4\end{array}\end{array}$$

Classification of states

State $j$ is accessible from state $i$ if there is a directed path in the transition graph from $i$ to $j$ ($\exists n$ such that $P_{ij}^{(n)}>0$). Let $T_{ij}=\min(n:X_n=j\mid X_0=i)$, then $P(T_{ij}<\infty)>0$ if and only if state $j$ is accessible from state $i$. States $i$ and $j$ communicate if $i$ is accessible from $j$ and $j$ is accessible from $i$. In Figure 5.1, state 3 and 1 communicate. State 4 is accessible form state 1, but they do not communicate since state 1 is not accessible from state 4.

We say that state $i$ is recurrent if for every state $j$ that is accessible from $i$, $i$ is also accessible from $j$ ($\forall j,\ P(T_{ij}<\infty)>0\Rightarrow P(T_{ij}<\infty)=1$). A state is called transient if it is not recurrent ($\exists j,\ P(T_{ij}<\infty)>0$ and $P(T_{ij}<\infty)<1$). In Figure 5.1, only state 4 is recurrent. States 1, 2 and 3 are all transient since 4 is accessible from 1/2/3, but 1/2/3 are not accessible from 4.

Absorbing Markov chains: A state $i$ is called absorbing if it is impossible to leave this state ($p_{ii}=1,p_{ij}=0,\forall j\ne i$). A Markov chain is absorbing if it has at least one absorbing state and if from every state it is possible to go to an absorbing state. In Figure 5.1, state 4 is an absorbing state. The corresponding Markov chain is an absorbing Markov chain.

Equations for absorption probability: The probability to reach a specific absorbing state $s$, $a_1,\cdots,a_M$, are unique solutions to equations $a_s=1,\ a_i=0$ for all absorbing state(s) $i\ne s$, and $a_i=\sum_{j=1}^M a_jp_{ij}$ for all transient states $i$. These equations can be easily 107derived using the law of total probability by conditioning the absorption probabilities on the next state.

Equations for the expected time to absorption: The expected times to absorption, $\mu_1,\cdots,\mu_M$, are unique solutions to the equations $\mu_i=0$ for all absorbing state(s) $i$ and $\mu_i=1+\sum_{j=1}^{m}p_{ij}\mu_j$ for all transient states $i$. These equations can be easily derived using the law of total expectation by conditioning the expected times to absorption on the next state. The number 1 is added since it takes one step to reach the next state.

Gambler’s ruin problem

Player $M$ has $1 and player $N$ has $2. Each game gives the winner $1 from the other. As a better player, $M$ wins 2/3 of the games. They play until one of them is bankrupt. What is the probability that $M$ wins?

Solution: The most difficult part of Markov chain problems often lies in how to choose the right state space and define the transition probabilities $P_{ij}$’s, $\forall i,j$. This problem has fairly straightforward states. You can define the state space as the combination of the money that player $M$ has ($$m$) and the money that player $N$ has ($$n$): $\{(m,n)\}=\{(3,0),(2,1),(1,2),(0,3)\}$. (Neither $m$ nor $n$ can be negative since the whole game stops when one of them goes bankrupt.) Since the sum of the dollars of both players is always $3, we can actually simplify the state space using only $m$: $\{m\}=\{0,1,2,3\}$.

The transition graph and the corresponding transition matrix are shown in Figure 5.2.

$$P=\{P_{ij}\}=\begin{bmatrix}p_{0,0}&p_{0,1}&p_{0,2}&p_{0,3}\\p_{1,0}&p_{1,1}&p_{1,2}&p_{1,3}\\p_{2,0}&p_{2,1}&p_{2,2}&p_{2,3}\\p_{2,0}&p_{2,1}&p_{2,2}&p_{2,3}\end{bmatrix}=\begin{bmatrix}1&0&0&0\\\frac13&0&\frac23&0\\0&\frac13&0&\frac23\\0&0&0&1\end{bmatrix}$$

The initial state is $X_0=1$ ($M$ has $1 at the beginning). At state 1, the next state is 0 ($M$ loses a game) with probability 1/3 and 2 ($M$ wins a game) with probability 2/3. So $p_{1,0}=1/3$ and $p_{1,2}=2/3$. Similarly we can get $p_{2,1}=1/3$ and $p_{2,3}=2/3$. Both state 3 ($M$ wins the whole game) and state 0 ($M$ loses the whole game) are absorbing states.

To calculate the probability that $M$ reaches absorbing state 3, we can apply absorption probability equations:

Plugging in the transition probabilities using either the transition graph or transition matrix, we have

So, starting from $1, player $M$ has $4/7$ probability of winning.

Dice question

Two players bet on roll(s) of the total of two standard six-face dice. Player $A$ bets that a sum of 12 will occur first. Player $B$ bets that two consecutive 7s will occur first. The players keep rolling the dice and record the sums until one player wins. What is the probability that $A$ will win?

Solution: Many of the simple Markov chain problems can be solved using pure conditional probability argument. It is not surprising considering that Markov chain is defined as conditional probability:

So let’s first solve the problem using conditional probability arguments. Let $P(A)$ be the probability that $A$ wins. Conditioning $P(A)$ on the first throw’s sum $F$, which has three possible outcomes $F=12,\ F=7$ and $F\notin\{7,12\}$, we have

Then we tackle each component on the right hand side. Using simple permutation, we can easily see that $P(F=12)=1/36,\ P(F=7)=6/36,\ P(F\notin\{7,12\})=29/36$. Also it is obvious that $P(A\mid F=12)=1$ and $P(A\mid F\notin\{7,12\})=P(A)$. (The game essentially starts over again.) To calculate $P(A\mid F=7)$, we need to further condition on the second throw’s total, which again has three possible outcomes: $E=12,\ E=7,$ and $E\notin\{7,12\}$.

Here the second equation relies on the independence between the second and the first rolls. If $F=7$ and $E=12$, $A$ wins; if $F=7$ and $E=7$, $A$ loses; if $F=7$ and 109$E\notin\{7,12\}$, the game essentially starts over again. Now we have all the necessarily information for $P(A)$. Plugging it into the original equation, we have

Solving the equation, we get $P(A)=7/13$.

This approach, although logically solid, is not intuitively appealing. Now let’s try a Markov chain approach. Again the key part is to choose the right state space and define the transition probabilities. It is apparent that we have two absorbing states, 12 ($A$ wins) and 7-7 ($B$ wins), at least two transient states, $S$ (starting state) and 7 (one 7 occurs, yet no 12 or 7-7 occurred). Do we need any other states? Theoretically, you can have other states. In fact, you can use all combination of the outcomes of one roll and two consecutive rolls as states to construct a transition matrix and you will get the same final result. Nevertheless, we want to consolidate as many equivalent states as possible. As we just discussed in the conditional probability approach, if no 12 has occurred and the most recent roll did not yield 7, we essentially go back to the initial starting state $S$. So all we need are states $S$, 7, 7-7 and 12. The transition graph and probability to reach state 12 are shown in Figure 5.3.

Probability to absorption state 12

$$\left.\begin{aligned}a_{12}&=1,a_{7\text{-}7}=0\\a_S&=1/36\times1+6/36\times a_7+29/36\times a_S\\a_7&=1/36\times1+6/36\times0+29/36\times a_S\end{aligned}\right\}\Rightarrow a_S=7/13$$

Here the transition probability is again derived from conditional probability arguments. Yet the transition graph makes the process crystal clear.

Coin triplets

Part A. If you keep on tossing a fair coin, what is the expected number of tosses such that you can have $HHH$ (heads heads heads) in a row? What is the expected number of tosses to have $THH$ (tails heads heads) in a row?

Solution: The most difficult part of Markov chain is, again, to choose the right state space. For the $HHH$ sequence, the state space is straightforward. We only need four states: $S$ (for the starting state when no coin is tossed or whenever a $T$ turns up before $HHH$), $H$, $HH$, and $HHH$. The transition graph is

At state $S$, after a coin toss, the state will stay at $S$ when the toss gives a $T$. If the toss gives an $H$, the state becomes $H$. At state $H$, it has 1/2 probability goes back to state $S$ if the next toss is $T$; otherwise, it goes to state $HH$. At state $HH$, it also has 1/2 probability goes back to state $S$ if the next toss is $T$; otherwise, it reaches the absorbing state $HHH$.

So we have the following transition probabilities: $P_{S,S}=\frac12,\ P_{S,H}=\frac12,\ P_{H,S}=\frac12,\ P_{H,HH}=\frac12,\ P_{HH,S}=\frac12,\ P_{HH,HHH}=\frac12,$ and $P_{HHH,HHH}=1$.

We are interested in the expected number of tosses to get $HHH$, which is the expected time to absorption starting from state $S$. Applying the standard equations for the expected time to absorption, we have

So from the starting state, the expected number of tosses to get $HHH$ is 14.

Similarly for expected time to reach $THH$, we can construct the following transition graph and estimate the corresponding expected time to absorption:

$$\left.\begin{aligned}\mu_S&=1+\tfrac12\mu_S+\tfrac12\mu_T\\\mu_T&=1+\tfrac12\mu_T+\tfrac12\mu_{TH}\\\mu_{TH}&=1+\tfrac12\mu_T+\tfrac12\mu_{THH}\\\mu_{THH}&=0\end{aligned}\right\}\Rightarrow\begin{cases}\mu_S=8\\\mu_T=4\\\mu_{TH}=2\\\mu_{THH}=0\end{cases}$$

So from the starting state $S$, the expected number of tosses to get $THH$ is 8.

Part B. Keep flipping a fair coin until either $HHH$ or $THH$ occurs in the sequence. What is the probability that you get an $HHH$ subsequence before $THH$?²

Solution: Let’s try a standard Markov chain approach. Again the focus is on choosing the right state space. In this case, we begin with starting state $S$. We only need ordered subsequences of either $HHH$ or $THH$. After one coin is flipped, we have either state $T$ or $H$. After two flips, we have states $TH$ and $HH$. We do not need $TT$ (which is equivalent to T for this problem) or $HT$ (which is also equivalent to $T$ as well). For three coin sequences, we only need $THH$ and $HHH$ states, which are both absorbing states. Using these states, we can build the following transition graph:

We want to get the probability to reach absorbing state $HHH$ from the starting state S. Applying the equations for absorption probability, we have

So the probability that we end up with the $HHH$ pattern is 1/8.

This problem actually has a special feature that renders the calculation unnecessary. You may have noticed that $a_T=0$. Once a tail occurs, we will always get $THH$ before $HHH$. The reason is that the last two coins in $THH$ is $HH$, which is the first two coins in sequence $HHH$. In fact, the only way that the sequence reaches state $HHH$ before $THH$ is that we get three consecutive $H$s in the beginning. Otherwise, we always have a $T$ before the first $HH$ sequence and always end in $THH$ first. So if we don’t start the coin flipping sequence with $HHH$, which has a probability of 1/8, we will always have $THH$ before $HHH$.

Part C. (Difficult) Let’s add more fun to the triplet game. Instead of fixed triplets for the two players, the new game allows both to choose their own triplets. Player 1 chooses a triplet first and announces it; then player 2 chooses a different triplet. The players again toss the coins until one of the two triplet sequences appears. The player whose chosen triplet appears first wins the game.

If both player 1 and player 2 are perfectly rational and both want to maximize their probability of winning, would you go first (as player 1)? If you go second, what is your probability of winning?³

Solution: A common misconception is that there is always a best sequence that beats other sequences. This misconception is often founded on a wrong assumption that these sequences are transitive: if sequence $A$ has a higher probability occurring before sequence $B$ and sequence $B$ has a higher probability occurring before sequence $C$, then sequence $A$ has a higher probability occurring before sequence $C$. In reality, such transitivity does not exist for this game. No matter what sequence player 1 chooses, player 2 can always choose another sequence with more than 1/2 probability of winning. The key, as we have indicated in Part B, is to choose the last two coins of the sequence as the first two coins of player 1’s sequence. We can compile the following table for each pair of sequences:

As shown in Table 5.1 (you can confirm the results yourself), no matter what player 1’s choices are, player 2 can always choose a sequence to have better odds of winning. The best sequences that player 2 can choose in response to 1’s choices are highlighted in bold. In order to maximize his odds of winning, player 1 should choose among HTH, HTT, THH and THT. Even in these cases, player 2 has 2/3 probability of winning.

Color balls

A box contains $n$ balls of $n$ different colors. Each time, you randomly select a pair of balls, repaint the first to match the second, and put the pair back into the box. What is the expected number of steps until all balls in the box are of the same color? (Very difficult)

Solution: Let $N_n$ be the number of steps needed to make all balls the same color, and let $F_i,i=1,2,\cdots,n$, be the event that all balls have color $i$ in the end. Applying the law of total expectation, we have

Since all the colors are symmetric (i.e., they should have equivalent properties), we have $P[F_1]=P[F_2]=\cdots=P[F_n]=1/n$ and $E[N_n]=E[N_n\mid F_1]=E[N_n\mid F_2]=E[N_n\mid F_n]$. That means we can assume that all the balls have color 1 in the end and use $E[N_n\mid F_1]$ to represent $E[N_n]$.

So how do we calculate $E[N_n\mid F_1]$? Not surprisingly, use a Markov chain. Since we only consider event $F_1$, color 1 is different from other colors and colors $2,\cdots,n$ become equivalent. In other words, any pairs of balls that have no color 1 ball involved are equivalent and any pairs with a color 1 ball and a ball of another color are equivalent if the order is the same as well. So we only need to use the number of balls that have color 1 as the states. Figure 5.5 shows the transition graph.

State $n$ is the only absorbing state. Notice that there is no state 0, otherwise it will never reach $F_1$. In fact, all the transition probability is conditioned on $F_1$ as well, which makes the transition probability $p_{i,i+1}\mid F_1$ higher than the unconditional probability $p_{i,i+1}$ and $p_{i,i-1}\mid F_1$ lower than $p_{i,i-1}$. For example, $p_{1,0}\mid F_1=0$ and $p_{1,0}=1/n$. (Without conditioning, each ball is likely to be the second ball, so color 1 has $1/n$ probability of being the second ball.) Using the conditional transition probability, the problem essentially becomes expected time to absorption with system equations:

To calculate $P_{i,i-1}\mid F_1$, let’s rewrite the probability as $P(x_{k+1}=i-1\mid x_k=i,F_1),\ \forall k=0,1,\ldots,$ to make the derivation step clearer:

The first equation is simply the definition of conditional probability; the second equation is the application of Bayes’ theorem; the third equation applies the Markov property. To derive $P(F_1\mid x_k=i)=i/n$, we again need to use symmetry. We have shown that if all the balls have different colors, then we have $P[F_1]=P[F_2]=\cdots=P[F_n]=1/n$. What is the probability of ending in a given color, labeled as $c$, if $i$ of the balls are of color $c$? It is simply $i/n$. To see that, we can label the color of each of the $i$ balls of color $c$ as $c_j,\ j=1,\cdots,i$ (even though they are in fact the same color). Now it’s obvious that all balls will end with color $c_j$ with probability $1/n$. The probability for $c$ is the sum of probabilities of $c_j$’s, which gives the result $i/n$.

Similarly we have $P(F_1\mid x_{k+1}=i-1)=(i-1)/n$. For $P(x_{k+1}=i-1\mid x_k=i)$, we use a basic counting method. There are $n(n-1)$ possible permutations to choose 2 balls out of $n$ balls. In order for one color 1 ball to change color, the second ball must be color 1, which has $i$ choices; the first ball needs to be another color, which has $(n-i)$ choices. So $P(x_{k+1}=i-1\mid x_k=i)=\dfrac{i(n-i)}{n(n-1)}$.

Applying the same principles, we can get

Plugging into $E[N_i\mid F_1]$ and simplifying $E[N_i\mid F_1]$ as $Z_i$, we have

Using these recursive system equations and the boundary condition $Z_n=0$, we can get $Z_1=(n-1)^2$.⁴