Expected state of a Markov chain

Question

Let's start with a slightly trivial Markov chain defined as follows: the beginning state is called $1$ and the set of states is $\mathbb{N}$. At each step, when the current state is $n$, the probability the state changes to $n+1$ is $f(n)$ for some function $f: \mathbb{N} \to [0,1]$ with $f(1) =1$. Otherwise the states remains unchanged.

To be more descriptive, the initial state is $1$. At the first step, the state changes to $2$ (with probability $f(1)=1$, so it always does). Then at the second step, the state changes to $3$ with probability $f(2)$ but otherwise stays there.

Call this first chain "chain 1". If one wants to know what's the expected value of the state after $k$ steps, there seems to be a trick:

• Let $T_{n,n+1}$ be the random variable for the time to go from state $n$ to $n+1$.

• Then $\mathbb{E}(T_{n,n+1}) = 1/f(n)$.

• Next, let $t_k = \mathbb{E} \big( \sum_{i=1}^{k-1} T_{n,n+1} \big) = \sum_{i=1}^{k-1} \mathbb{E}(T_{n,n+1}) $.

• Then $\mathbb{E}(X_{t_k}) = k$.

So it suffices to invert the function $k \mapsto t_k$ to get a good idea of the answer.

$\mathbf{Sub-Question:}$ Is there a name to the above trick? or a reference where this is done rigorously?

Now look at this other chain, called "chain 2". The initial state is $1$. Then, at each step, when the state is at $n$,

• the probability the state changes to $n+1$ is $w(n)$ for some function $w: \mathbb{N} \to [0,1]$ with $w(1) =1$;

• the probability the state changes to $n-1$ is $l(n)$ for some function $l: \mathbb{N} \to [0,1]$ with $l(n) < w(n)$ and $l(n)+w(n) \leq 1$;

• Otherwise the states remains unchanged.

$\mathbf{Question:}$ Is the expected value of "chain 2" (for $w$ and $l$ fixed) the same as the expected value of "chain 1" for $f(n) = w(n) - l(n)$.

Answer 1

Sub−Question: Is there a name to the above trick? or a reference where this is done rigorously?

No name, since the "trick" does not exist. A proper definition would include a definition of $E(X_{t_k})$ when $t_k$ is not an integer.

Question: Is the expected value of "chain 2" (for $w$ and $l$ fixed) the same as the expected value of "chain 1" for $f(n)=w(n)−l(n)$.

No, for example $E_0(X_3)$ differs for chain 1 and for chain 2 when $w(n)=\frac12(1+f(n))$ and $l(n)=\frac12(1-f(n))$ for $0\leqslant n\leqslant 2$.

Answer 2

I've managed to come up with a solution for what is equivalent to your first chain.

Let $P_{n,k}$ denote the probability that the Markov process is in state $k$ after $n$ timesteps, and let $p_k:=f(k)$ denote the probability to transition from state $k$ to the next. Notice that your first state, which is guaranteed to be transitioned in the first time step, can be omitted - the stochastic process starts afterwards. So we start with $P_{0,0}=1$.

You can easily see that the cases $P_{n,0}$ occur if the first transition has failed to happen $n$ times, so $P_{n,0}=(1-p_0)^n$.

We can approach all other cases ($k>0$) by identifying a recurrence relation, since for the process to be in state $k$ at time $n$, at time $n-1$ it must have either been in state $k-1$ and transitioned, or already in state $k$ and not. Therefore:

$$P_{n,k}=P_{n-1,k}*(1-p_k)+P_{n-1,k-1}*p_{k-1}$$

However, actually solving this recurrence relation turned out to be quite difficult for anything with $k>1$. When trying you'll notice a sum coming up that, after excluding all common factors, looks very similar to the multinomial theorem, but lacks any multinomial coefficients (i.e. all coefficients are equal to one). When you think about it this makes sense: Our total probability should be equal to the sum of the probabilities of all paths that lead to its position on a $(k\times n)$ grid. Each of these paths must contain the $k$ successful transitions and $n-k$ failures, the latter of which can occur at $k+1$ discernible positions with repetition, yielding ${{n-k+k+1-1}\choose{n-k}}={{n}\choose{k}}$ different paths, or summands in the emerging sum, respectively.

Nonetheless, it's possible to express this sum as one part of the factorization of a compact polynomial. After slicing it up and conducting numerous transformations, I discovered the following, rather compact solution:

$$P_{n,k}=\sum_{i=0}^k \left((1-p_i)^n*\prod_{j=1}^k \frac{p_{j-1}}{p_{(i+j)mod(k+1)}-p_i}\right)$$

So there you have it, with this you can calculate anything about chain 1. The expected state after $n$ timesteps you asked for, for example, is then given by:

$$E_n[K]=\sum_{k=0}^nk*P_{n,k}$$

Regarding your trick, I've used this as well and compared the results to numerically obtained exact solutions before I finished the compact formula. I agree that conceptually this should give a decent impression of roughly where the results are situated, but I suppose the performance of this approximation depends quite unpredictably on $f(k)$. In the example function I used, I did notice a systematic error in the results this gives, the error terms were diverging for larger $n$, albeit slowly. But with the given formula, this will no longer be necessary anyways.