I think the question I am asking might already be derived, but I could not find it. So this is how it goes, suppose I have a 2-state Markov chain having states $\texttt{State-1}$ and $\texttt{State-2}$. The transition matrix of this 2-state Markov chain is as $$P = \begin{bmatrix} p_{11} & p_{12}\\ p_{21} & p_{22} \end{bmatrix}$$ We assume that Markov chain always starts in $\texttt{State-1}$. I want to find the probability that $\texttt{State-1}$ or $\texttt{State-2}$ has been picked exactly $k$ number of times out of $n$ timesteps.
Approach till now,
Suppose $n=2$, In $n=0$, I am in $\texttt{State-1}$, what is the probability I will get $\texttt{State-2}$ exactly $1$ time only, the possible walks would be, $$\underbrace{\texttt{State-1}}_{n=0} \rightarrow \underbrace{\texttt{State-1}}_{n=1} \rightarrow \underbrace{\texttt{State-2}}_{n=2} \quad\text{and}\quad \underbrace{\texttt{State-1}}_{n=0} \rightarrow \underbrace{\texttt{State-2}}_{n=1} \rightarrow \underbrace{\texttt{State-1}}_{n=2}$$ Therefore the probability of such event would be $$P(X_1=1|X_0=1)\times P(X_2=2|X_1=1) + P(X_1=2|X_0=1)\times P(X_2=1|X_1=2)$$ Likewise for $n=4$, what is the probability I will get $\texttt{State-2}$ exactly $2$ times only, the possible walks would be, $$\underbrace{1}_{n=1},\underbrace{1}_{n=2},\underbrace{2}_{n=3},\underbrace{2}_{n=4}\\ 1,2,2,1\\ 2,2,1,1\\ 1,2,1,2\\ 2,1,2,1\\ 2,1,1,2$$
Here in $n=0$ $\texttt{State-1}$ is always picked. There are $\binom{4}{2}$ possible combinations. I idea is not simple as to use binomial distribution, but because the depending upon which state your are, probabilities changes. If anyone has an idea how to solve this for a generalized $k$ and $n$, please help me.