Markov Chains

Let us consider a two-state Markov chain, where the states are denoted as S1 and S0. The Markov chain's initial state is determined by two possible states, S1 and S0, with corresponding probabilities p1 and p0. The likelihood of transitioning from state Si to state Sj is denoted as pij. The issue at hand pertains to determining the likelihood that state S1 has been visited precisely k times after N steps, given the starting state probability p1 for state S1. 

It is important to observe that staying in state S1 is considered as an additional visit to this particular state. Upon conducting an extensive investigation in various probability and stochastic processes literature, it became apparent that the subject at hand, once perceived as straightforward, lacks a theorem that yields the desired outcome. In this blog, I have endeavored to independently verify the answer, which appears to be somewhat laborious. I have validated my response through the use of simulation, the code for which is provided at the conclusion.

Solution:

The task at hand involves calculating the probability, indicated as P(N1 = k|N), which represents the likelihood that the number of trips to state S1 (referred to as N1) is equal to k after N state changes. If state S1 is revisited from state S1, this is considered as an additional visit. The quantification of trips to state S1 involves the enumeration of state transitions originating from S1. Specifically, it entails determining the frequency of occurrences for the transitions S1→S0 and S1→S0. The notation P1(k,N|Si) is used to represent the probability of visiting state S1 exactly k times in N state transitions, given that the initial state is Si. Note that the initial transition to state S0 and S1 is also considered as a visit. Then

The first term is when the initial state is S1 and the second term is when the initial state is S0. We can find the first term as,

where in X0-Y0 and X1-Y1, the final state is assumed to be S0 and S1, respectively. The final state is supposed to be denoted as S0 and S1, respectively. First, I will provide an explanation of X0-Y0. In order to reach state S1 a total of k times, it is important to have precisely a total of k S1→S0 and/or S1→S1 state transitions. Specifically, there exist k−j and j S1→S1 and S1→S0 state transitions, respectively. Given that the end state is denoted as S0 and there are j occurrences of the S1→S0 transition, it follows that there must exist a total of j−1 S0→S1 state transitions. If the total number of state transitions is denoted as N, then the total number of transitions from state S0 to state S0 must be equal to N minus the sum of k, and j. Now, let us direct our attention to X0. For every S0→S1 transition, there exists a collection of S1→S1 state transitions that may occur. The overall count of S1→S1 transition sets is denoted by j, which is equivalent to the sum of the number of S0→S1 transitions and one. The entire number of k−j , S1→S1 state transitions is distributed over j, S1→S1 transition sets. The overall count of feasible combinations corresponds to the weak composition of j natural numbers that add up to k−1−j . The acquisition of Y0 follows a similar process, wherein each transition from state S1 to S0 may be accompanied by a collection of transitions from state S0 to S0. Therefore, the number of transitions from state S0 to state S0 can be calculated as N−k−j, distributed among j sets of transitions. Therefore, the overall quantity of potential combinations can be determined by examining the weak composition of j natural numbers, which collectively yield a sum of N−k−j.  Likewise for X1-Y1, the final state is S1 and end the same kind of equation except we sum to only k−1 steps because the final and initial state are same. 

The second term of  P(N1 = k|N) is as,

This completes the solution. Follows this link to find the code: https://drive.google.com/file/d/1Aw66DOaVZ76M5mAuyfMIuCoo1JaAVJjL/view?usp=sharing