3.7 Expected Numbers of Visits
Let \(V_{ij}^{(n)}\) be the number of visits to state \(j\) at times \(0, 1, \dots , n - 1\) by a chain started at \(i\). Writing it as a sum of indicators of the events \(\{X_k = j\}\), \[E\left (V_{ij}^{(n)}\right ) = \sum _{k=0}^{n - 1}P_{ij}^{(k)},\qquad \text {that is}\qquad V^{(n)} = I + P + P^2 + \cdots + P^{n - 1}\] for the matrix of expected visits.
Example 3.7.1. For the taxi of example 3.6.4, find the expected numbers of hours, from 8 a.m. to 11 a.m. inclusive, that it spends in each town, given that it starts in town \(A\).
Solution. Four hourly positions (times \(0\) to \(3\)) are counted, so \[V^{(4)} = I + P + P^2 + P^3 = \begin {pmatrix}2.037 & 0.609 & 1.354\\ 0.800 & 1.750 & 1.450\\ 0.896 & 0.897 & 2.207\end {pmatrix}.\] Starting from \(A\), the expected numbers of the four hours spent in \(A\), \(B\) and \(C\) are \(2.04\), \(0.61\) and \(1.35\). Each row sums to \(4\).
3.7.1 Visits to transient states
Suppose the chain is finite and \(T = \{1, 2, \dots , t\}\) are its transient states. Let \(P_T\) be the \(t\times t\) matrix of transition probabilities among the transient states; its rows may sum to less than \(1\), since the chain can leave \(T\). For \(i, j\in T\) let \(s_{ij}\) be the expected number of visits to \(j\), including time \(0\), by a chain started at \(i\). Conditioning on the first step, and noting that a transient state cannot be reached from a recurrent one, \[s_{ij} = \delta _{ij} + \sum _{k\in T}P_{ik}s_{kj},\qquad \delta _{ij} = \begin {cases}1, & i = j,\\ 0, & i\ne j .\end {cases}\] In matrix form \(S = I + P_TS\), so \[S = (I - P_T)^{-1} .\] Moreover the probability \(f_{ij}\) that a chain started at \(i\) ever visits \(j\) satisfies \(s_{ij} = \delta _{ij} + f_{ij}s_{jj}\), since a visit to \(j\) is followed by \(s_{jj}\) expected visits in all; so \(f_{ij} = \frac {s_{ij} - \delta _{ij}}{s_{jj}}\).
Example 3.7.2 (Gambler’s ruin). A gambler with \(i\) units bets one unit at a time, winning with probability \(0.4\) and losing with probability \(0.6\), and stops on reaching \(0\) or \(7\). Starting with \(3\) units, find the expected number of times the gambler has \(5\) units and has \(2\) units, and the probability of ever having \(5\) units.
Solution. States \(0\) and \(7\) are absorbing and \(1, \dots , 6\) are transient, with \(P_{i,i + 1} = 0.4\) and \(P_{i,i - 1} = 0.6\) inside \(T\): \[P_T = \begin {pmatrix} 0 & 0.4 & 0 & 0 & 0 & 0\\ 0.6 & 0 & 0.4 & 0 & 0 & 0\\ 0 & 0.6 & 0 & 0.4 & 0 & 0\\ 0 & 0 & 0.6 & 0 & 0.4 & 0\\ 0 & 0 & 0 & 0.6 & 0 & 0.4\\ 0 & 0 & 0 & 0 & 0.6 & 0 \end {pmatrix}.\] Inverting \(I - P_T\) numerically, the row for state \(3\) is \((1.4206, 2.3677, 2.9990, 1.7533, 0.9228, 0.3691)\). So, starting from \(3\), the gambler expects to have \(5\) units \(0.9228\) times and \(2\) units \(2.3677\) times. With \(s_{55} = 2.5625\), the probability of ever reaching \(5\) units is \(f_{35} = \frac {0.9228}{2.5625} = 0.360\).
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.