Say I have two types of days, A and B. We have that:
- A is followed by A with probability $p$.
- A is followed by B with probability $1 – p$.
- B is followed by B with probability $q$.
- B is followed by A with probability $1 – q$.
Over a year with 365 days, what’s the expected number of A days?
Edit: I’m not sure how to even start this problem. It’s not even specified if the sequence begins with A or B!
This problem however reminds me of a similar problem that is simpler, which is to calculate the expected number of runs given however many coin flips. That’s going to be the total number of coin flips + 1, divided by 2. But I’m wondering how to generalize this to the problem at hand here.
Best Answer
Here is the brute force method:
Notation: Let us give the state $A$ the value $1$ and the state $B$ the value $0$. Let us denote the state in time $n$ as $X_n$. $X_0$ will now denote the starting state. Now when we are in state $A$ at time $n$, we say $X_n = 1$ and when we are in state $B$ at that time we say $X_n = 0$. Now let us define $S_n := X_0 + \dots + X_{n-1}$. Now the advantage of giving $A$ the value $1$ becomes apparent: $S_n$ counts the number of times the state $A$ was visited up to time $n$ since $1$ is added for every time we are in state $A$ and nothing is added when we are in state $B$.
How does the process start?: Since we do not know how the system is started, the best thing we can do is assume it starts with a starting distribution vector $$B = \begin{pmatrix} B_1, & B_2 \end{pmatrix},$$ where $B_1 = \mathbb{P}\left(X_0 = A \right) = \mathbb{P}\left(X_0 = 1 \right)$ and $B_2 = \mathbb{P}\left(X_0 = B \right) = \mathbb{P}\left(X_0 = 0\right)$ (I choose the letter $B$ for Begin), thus $B_1 + B_2 = 1$. Note that $B = \begin{pmatrix} 1 & 0 \end{pmatrix}$ corresponds to starting in $A$ with probability 1 and likewise $\begin{pmatrix} 0 & 1 \end{pmatrix}$ is starting in $B$ with probability 1, but for now we take general $B_1$ and $B_2$.
Probability to be in $A$ at time $n$: Now let us calculate the probability to be in state $A$ at time $n$. For that we first write down the transition matrix. For that, see the following figure.
So now we have the transition matrix
$$P = \begin{pmatrix} p & p-1 \\ 1-q & q \end{pmatrix}.$$
Now to determine the probability that we are in state $A$ at time $n$, we need the probability transition matrix for $n$ time steps, which is simply the $n$-th power of the probability transition matrix. I leave it up to the OP to verify (either via induction of diagonalization) that
$$P^n = \frac{1}{2 - p - q} \begin{pmatrix} 1 - q + (1- p)(p + q - 1)^n & 1 - p - (1- p)(p + q - 1)^n \\ 1 - q - (1- q)(p + q - 1)^n & 1 - p + (1- q)(p + q - 1)^n \end{pmatrix}.$$
Now the probability vector at time $n$ given that we start with the probability vector $B$ will be
\begin{align*} BP^n &= \begin{pmatrix} B_1 & B_2 \end{pmatrix} \frac{1}{2 - p - q}\begin{pmatrix} 1 - q + (1- p)(p + q - 1)^n & 1 - p - (1- p)(p + q - 1)^n \\ 1 - q - (1- q)(p + q - 1)^n & 1 - p + (1- q)(p + q - 1)^n \end{pmatrix}\\ &= \begin{pmatrix} B_1 & B_2 \end{pmatrix} \frac{1}{2 - p - q}\left[ \begin{pmatrix} 1 - q & 1 - p \\ 1 - q & 1- p \end{pmatrix} + (p + q - 1)^n\begin{pmatrix} 1 - p & p -1 \\ q - 1 & 1 - q \end{pmatrix}\right]\\ &=\frac{1}{2 - p - q}\left[ \begin{pmatrix}B_1(1 - q) + B_2(1-p), & B_1(1 - q) + B_2(1-p)\end{pmatrix}\\ + (p + q -1)^n \begin{pmatrix}B_1(1-p) - B_2(1-p), & -B_1(1-q) + B_2(1-q)\end{pmatrix} \right], \end{align*} where the last expression is a sum of two row matrices again. Now since the first coördinate corresponds to state $A$, we find that $$\mathbb{P}\left(X_n = A \right) = \frac{1}{2 - p - q}\left( B_1(1 - q) + B_2(1-p) + (p + q -1)^n\cdot (B_1(p-1) - B_2(1-p)) \right).$$ We will later denote the above probability again by $\mathbb{P}\left(X_n = 1\right)$.
Expected number of $A$ days: Now we are ready to calculate the expected number of $A$ days up to day $n = 365$. That is, we determine $\mathbb{E}\left[S_n\right]$. Here you have to remember that we give $X_n$ value $1$ if it is in state $A$ and value $0$ if it is in state $B$. Using linearity of the expectation we can calculate \begin{align*} \mathbb{E}\left[S_n\right] &= \mathbb{E}\left[ X_0 + \dots + X_{n-1} \right]\\ &= \sum_{k = 0}^{n-1}\mathbb{E}\left[X_n\right]\\ &= \sum_{k = 0}^{n-1}\left( 1\cdot \mathbb{P}\left( X_n = 1\right) + 0\cdot \mathbb{P}\left( X_n = 0\right) \right) \\ &= \sum_{k = 0}^{n-1} \frac{1}{2 - p - q}\left[ B_1(1 - q) + B_2(1-p) + (p + q -1)^n\cdot (B_1(1-p) - B_2(1-p)) \right] \\ &= \frac{n(B_1(1-q) B_2(1-p))}{2 - p - q} + \frac{B_1(1-p) - B_2(1-p)}{2 - p - q}\sum_{k = 0}^{n-1}(p + q - 1)^k\\ &= \frac{n(B_1(1-q) B_2(1-p))}{2 - p - q} + \frac{B_1(1-p) - B_2(1-p)}{2 - p - q}\cdot \frac{1 - (p + q - 1)^n}{2 - p - q}. \end{align*} Now filling in $n = 365$ we get that the expected number of $A$ days in a year of 365 days will be: $$\mathbb{E}\left[S_{365}\right] = \frac{365(B_1(1-q) B_2(1-p))}{2 - p - q} + \frac{B_1(1-p) - B_2(1-p)}{2 - p - q}\cdot \frac{1 - (p + q - 1)^{365}}{2 - p - q}.$$
If you see any typos / mistakes, please let me know.