2
$\begingroup$

This question is a follow-up to Expected number of steps for reaching a specific absorbing state in an absorbing Markov chain because I don't understand the answer given there. I think I need to see a concrete example.

Suppose I play red and black at a casino. On each play, I either win the amount I staked, with probability $p<\frac12$ or I lose my stake. Let's say I start with a bankroll of $2$ and I decide to play until I have won $3$ or lost everything. My strategy is to bet just enough to reach my goal, or everything I have, whichever is less.

We have a Markov chain with $6$ states, $2$ of which are absorbing. There are well-known methods to determine the probability of winning, and of determining the average number of plays I make, but what if I want to know the average number of plays I make if I reach my goal? The transition matrix, with $q=1-p$ is $$\begin {bmatrix} 1&0&0&0&0&0\\ q&0&p&0&0&0\\ q&0&0&0&p&0\\ 0&q&0&0&0&p\\ 0&0&0&q&0&p\\ 0&0&0&0&0&1 \end{bmatrix}$$

Henning Malcolm suggests two approaches, neither of which I can follow. (This is because of my limitations, and is in no way intended as a criticism of the answer.) The first assumes that I have figured out the probability of winning starting with every possible bankroll. Then we are to compute new transition probabilities that describe the experience of the winners, as I understand it, and compute the time to absorption in the new chain. Let $p_k$ be the probability of winning, if my bankroll is $k$. How should I calculate the new transition matrix?

Henning Malcolm gives an alternative method if there is only one starting state we're interested in, and I'm only interested in the actual case where I start in state $2$. He says, "first set up a system of equations that compute for each state the expected number of times one will encounter that state before being absorbed." If we let $e_k$ be this number for state $k=1,2,3,4,$ how do we construct the equations relating the $e_k?$ I can see how to do this if we only care about the number plays until the game ends, but how do I make it reflect only the number of plays until winning?

$\endgroup$
  • $\begingroup$ Did you deliberately choose an example where each state has only two successors? I think in this case, in the first method you can set up a system of linear equations for the transition probabilities conditional on winning; but that won't work in the same way if you have a more general transition matrix, as you'll have too many unknowns and too few equations. $\endgroup$ – joriki Jul 15 '18 at 7:20
  • $\begingroup$ @joriki No I didn't. I wanted to make a simple example, so that it wasn't asking to much to request a solution, but it didn't occur to me that I might be over-simplifying the problem. $\endgroup$ – saulspatz Jul 15 '18 at 14:06
1
$\begingroup$

[A partial answer illustrating the first method.]

State $1$ represents losing the game, so remove it from the system and condition the remaining transition probabilities on the event that the system does not transition from state $i$ to state $1$. In practical terms, this means that you delete from your transition matrix column $1$ and every row that had a $1$ in this column, and scale each remaining row $i$ by $1/(1-p_{1i})$. For your example system, this produces the reduced matrix $$P' = \begin{bmatrix}0&1&0&0&0 \\ 0&0&0&1&0 \\ q&0&0&0&p \\ 0&0&q&0&p \\ 0&0&0&0&1 \end{bmatrix}.$$ Applying standard techinques to this matrix, we can verify that the absorption probability is $1$ for any starting state and that the expected conditional absorption times are $$\begin{bmatrix}{3+q\over1-q^2} \\ {2+q+q^2\over1-q^2} \\ {1+3q\over1-q^2} \\ {1+q+2q^2\over1-q^2}\end{bmatrix}.$$

$\endgroup$
  • $\begingroup$ Perfect. Thank you. $\endgroup$ – saulspatz Oct 27 '18 at 15:58
  • $\begingroup$ @saulspatz I also answered your original question. The thing to watch out for when doing this is that you also have to prune any dead-end branches that result from deleting the “bad” absorbing states. $\endgroup$ – amd Oct 27 '18 at 19:22
  • $\begingroup$ Actually, that was someone else's question, but I went and looked at your answer. I don't think I really understood what you meant by "dead-end branches" till I read the other answer, but now it makes perfect sense to me. $\endgroup$ – saulspatz Oct 27 '18 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.