Class 15
Recurrent: \(f_i = 1\), \(g_i = 0\), if \(j \leftrightarrow i\) then \(f_{ij} = 1\)
Positive recurrent: \(\pi_i > 0\), \(m_i < \infty\)
\(\displaystyle \pi_j = \sum_i P_{ij}\pi_i\)
\(\displaystyle \sum_i \pi_i = 1\)
Null recurrent: \(\pi_i = 0\), \(m_i = \infty\)
Transient: \(f_i < 1\), \(g_i > 0\).
If \(j\) is also transient,
\(s_{ij} < \infty\), \(\mathbf{S} = (\mathbf{I} - \mathbf{P}_T)^{-1}\)
\(\displaystyle f_{ij} = \frac{s_{ij} - \delta_{ij}}{s_{jj}}\)
\[ \small \mathbf{P} = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & \cdots & 0 & 0 \\ 1-p & 0 & p & 0 & 0 & \cdots & 0 & 0 \\ 0 & 1-p & 0 & p & 0 & \cdots & 0 & 0 \\ 0 & 0 & 1-p & 0 & p & \cdots & 0 & 0 \\ 0 & 0 & 0 & 1-p & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & 0 & \cdots & 0 & p \\ 0 & 0 & 0 & 0 & 0 & \cdots & 0 & 1 \end{bmatrix} \]
\(P_{00} = P_{NN} = 1\)
and for \(i = 1, 2, \dots, N-1\):
\(P_{i,i+1} = p = 1 - P_{i,i-1}\)
If \(i\) is transient (\(i \in \{1, 2, \dots, N-1\}\)), whats is \(f_{iN}\)?
Let \(P_i = f_{iN}\) for \(i = 0, 1, 2, \dots, N\).
Clearly \(P_0 = 0\) and \(P_N = 1\).
Let \(i \in \{1, 2, \dots, N-1\}\). Conditioning on the next step:
\(P_i = p P_{i+1} + qP_{i-1}\) where \(q = 1-p\).
\({\color{red}(p + q)}P_i = p P_{i+1} + qP_{i-1}\) because \(1 = p + q\)
\(pP_i + qP_i = p P_{i+1} + qP_{i-1}\) (distribute)
\(q(P_i - P_{i-1}) = p(P_{i+1} - P_i)\) (move \(q\)’s on the left, \(p\)’s on the right)
\(p(P_{i+1} - P_i) = q(P_i - P_{i-1})\) (flip sides)
\(P_{i+1} - P_i = \frac{q}{p}(P_i - P_{i-1})\) (divide by \(p\))
\(P_0 = 0\)
\(P_2 - P_1 = \frac{q}{p} (P_1 - P_0) = \frac{q}{p} P_1\) and so \(P_2 = P_1 + \frac{q}{p} P_1\).
\(P_3 - P_2 = \frac{q}{p} (P_2 - P_1) = \left(\frac{q}{p}\right)^2 P_1\) and so \(P_3 = P_2 + \left(\frac{q}{p}\right)^2 P_1\).
\(P_4 - P_3 = \frac{q}{p} (P_3 - P_2) = \left(\frac{q}{p}\right)^3 P_1\) and so \(P_4 = P_3 + \left(\frac{q}{p}\right)^3 P_1\).
\(\vdots\)
\(P_i - P_{i-1} = \frac{q}{p} (P_{i-1} - P_{i-2}) = \left(\frac{q}{p}\right)^{i-1} P_1\) and so \(P_i = P_{i-1} + \left(\frac{q}{p}\right)^{i-1} P_1\).
\(\vdots\)
\(P_N - P_{N-1} = \frac{q}{p} (P_{N-1} - P_{N-2}) = \left(\frac{q}{p}\right)^{N-1} P_1\) and so \(P_N = P_{N-1} + \left(\frac{q}{p}\right)^{N-1} P_1\).
\(\color{green}P_i = P_1 + \frac{q}{p}P_1 + \left(\frac{q}{p}\right)^2 P_1 + \cdots + \left(\frac{q}{p}\right)^{i-1}P_1 = \left(1 + \frac{q}{p} + \left(\frac{q}{p}\right)^2 + \cdots + \left(\frac{q}{p}\right)^{i-1}\right)P_1\)
\(P_0 = 0\)
\(P_i = \left(1 + \frac{q}{p} + \left(\frac{q}{p}\right)^2 + \cdots + \left(\frac{q}{p}\right)^{i-1}\right)P_1\)
\(\displaystyle P_i = \left(\frac{1 - \left(q/p\right)^i}{1 - q/p}\right)P_1\) for \(i = 1, 2, 3, \dots, N\), if \(q/p \neq 1\).
What is \(P_1\)?
We know \(P_N = 1\).
\(\displaystyle \left(\frac{1 - \left(q/p\right)^N}{1 - q/p}\right)P_1 = 1\), so \(P_1 = \displaystyle \frac{1 - q/p}{1 - \left(q/p\right)^N}\).
\(\displaystyle P_i = \frac{1 - \left(q/p\right)^i}{1 - \left(q/p\right)^N}\) for \(i = 1, 2, 3, \dots, N\), if \(q/p \neq 1\).
What happens if \(q = p\)?
Two drugs:
Is \(P_1 > P_2\) or \(P_2 > P_1\)?
Take two patients, randomly treat them with Drug 1 and Drug 2. Repeat.
Define:
Stop when \(\displaystyle\left\lvert \sum_{i = 1}^n X_i - \sum_{i = 1}^n Y_i\right\rvert = M\).
What is the probability that the process will reach \(M\) before reaching \(-M\)?