1

While studying Markov processes, I faced to the following task. Please help to solve.

We have the Markov Chain with two states. This Markov chain is shown here: enter image description here

The probabilities of transitions $p$ and $q$ are known. The initial state is $1$ with probability = $1$. A walk along this chain is started and it is interrupted as soon as state $2$ has been visited $n$ times. Let the random variable $\xi$ be the number of visits to state $1$ before the interruption. How can we find the variance of $\xi$?

Upd. The first thought I had was to represent $\xi$ as a random variable with Negative binomial distribution. But this is incorrect because different sequences of states 1, 2 have different probability of realizations.

The next attempt was like this. Let $F_m(k)$ be the probability of visiting the state 1 $k$ times with interrupt condition is the second state is visited $m$ times. Then variance of $\xi$ is $V(x) = E \xi^2 - E^2 \xi$, when $$ E \xi = \sum_{k=1}^{\infty} k F_n(k), E \xi^2 = \sum_{k=1}^{\infty} k^2 F_n(k) . $$

$F_n(k)$ can be expressed using recursion. Recursion base is $$ F_1(k) = (1-p)^{k-1} p . $$ For $F_n(k), n > 1$ we get $$ F_n (k) = \sum_{j=1}^{k-1} F_{n-1} (k-j) (1-p)^{j-1} p + F_{n-1}(k)(1-q). $$ I tried to switch from recursion to an closet formula, but power terms appear together with Bernoulli numbers and it becomes completely unclear how to count $E \xi, E \xi^2$.

ets_ets
  • 19
  • 1
    This shouldn't be solved as a Markov chain question. It is difficult to find this quantity for a general Markov chain, but here, we can express $\xi$ as a sum of Geometric random variables. Try it. – Misha Lavrov Nov 28 '22 at 15:27
  • @MishaLavrov , please, can you tell us in more detail what you mean. I tried to interpret $xi$ as Negative binomial distribution random variable . but I faced to this problem due to random walk, different sequences of the states have different probability of realization. – ets_ets Nov 28 '22 at 15:41
  • If that's the case, then you should edit your question, because your question led me to believe you had not tried anything. Write up what you attempted and where you got stuck. – Misha Lavrov Nov 28 '22 at 15:42
  • @MishaLavrov , I added my attempts with edit. But, as you can see, I have reached a dead end. – ets_ets Nov 28 '22 at 16:07

1 Answers1

1

The negative binomial approach is the correct one here, it just needs some modification.

Let $X_1$ be the number of times state $1$ is visited before visiting state $2$ for the first time. Then, for $2 \le i \le n$, let $X_i$ be the number of times state $1$ is visited between the $(i-1)^{\text{th}}$ and $i^{\text{th}}$ visit to state $2$. We have:

  • $X_1 \sim \text{Geometric}(p)$ (with the convention that the range of a geometric distribution starts at $1$). We have $\Pr[X_1 = k] = p(1-p)^{k-1}$ for $k=1, 2, 3, \dots$
  • For $i \ge 2$, $X_i$ has a very similar distribution if we go from $2$ back to $1$, but we can also stay at $2$ and get $X_i=0$. We have $\Pr[X_i = 0] = 1-q$ and $\Pr[X_i = k] = pq(1-p)^{k-1}$ for $k=1, 2, 3, \dots$. A useful way to think of $X_i$ is as a mixture distribution: it is $0$ with probability $1-q$ and $\text{Geometric}(p)$ with probability $q$.

We have $\text{Var}[X_1] = \frac{1-p}{p^2}$ by the usual formula, but for $X_2, \dots, X_n$ a bit more work needs to be done to compute $\text{Var}[X_i]$. One approach is to condition the first step to compute $\mathbb E[X_i]$ and $\mathbb E[X_i^2]$ (in which case the law of total expectation can be used).

Since $X_1, X_2, \dots, X_n$ are independent, we have $$\text{Var}[\xi] = \text{Var}[X_1] + \dots + \text{Var}[X_n].$$

Misha Lavrov
  • 142,276