# Markov Chains to find total reward

I have the following state space corresponding to the subscription details of customers with number of months: $S=\{C,0,1,2,3,4,5,6,7,8,...\}$. This corresponds to the number of months of subscription and $C$ means cancelled.

Can I use stationary probabilities to model this? I think it has to be a positively recurrent process, to find stationary probabilities. Since in the long run, all customers will leave and end up at $C$.

What I tried:

Let $p_{i,i+1}$ be the probability of going from state $i$ to $i+1$.

Let $q_{i,C} = 1 - p_{i,i+1}$

$p_{C,C}=1$

I'm trying to find out the value of each customer. I formulated the problem as a total reward problem when starting from state $0$, where $r=10$ is the reward at every month. Then expected total reward for state $0$ is: $$\phi_i=10+q_{i,C}\phi_{C}+p_{i,i+1}\phi_{i+1} \text{ for } i\geq 0$$ and $$\phi_C=0$$

However, ($p_{i,i+1}=0.9$ for $i\geq 0)$ I can't seem to solve this system of equation to get $\phi_0$.

• Do you mean $p_{i, C}$ when you write $q_{i,0}$? (A customer can cancel after any month, not go back to month zero.) – ploosu2 Oct 24 '17 at 11:48

Let's cut the chain at level $i=N$ to get a finite Markov chain and set transition from the state $N$ to $C$ with probability $1$. Now this is a finite Markov chain with an absorbing state $C$. With results that can be found for example here (see page 418) we have that the expected number of times the chain is at state $j$ starting from the state $i$ (before being absorbed to the state $C$) is given by the fundamental matrix entry $n_{ij}$. The fundamental matrix is $N = (I-Q)^{-1}$ where $Q$ is the non-absorbing part of the transition matrix (see the link).

If we assume the transition probablility is constant $p_{i,i+1}=p$, we have

$$I-Q=\begin{bmatrix} 1 & -p & & & \\ & 1 & -p & & \\ & & \ddots & \ddots & \\ & & & & 1 \end{bmatrix}$$

It can be seen that the inverse of this is

$$N = \begin{bmatrix} 1 & p & p^2 & \dots & p^N \\ 0 & 1 & p & \dots & p^{N-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \dots & 1 \end{bmatrix}$$

So when starting from the state $0$ the expected number of times the chain visits any state before $C$ is

$$\sum_{k=0}^N p^k.$$

If for each state we get the reward $r$ then the expected reward is $r\sum_{k=0}^N p^k$. It's at least intuitively clear that cutting the chain at larger and larger $N$ leads to an answer that is closer and closer to the infinite case. As we let $N\to\infty$ this geometric sum approaches $\frac{r}{1-p}$.

• Thanks I've looked over the notes, how would you model this problem if I set custom $p_{i,i+1}$ for lets say $i=1,2,3$, the first 3 months and make them constant $p=0.9$ afterwards? If considering a transition matrix $P$, which is $n \times n$, the $Q$ matrix is $n-1$ square matrix since I have all transient and only 1 recurrent states. I will need to compute the inverse of the $I-Q$ (which is infinite for my real case), and sum over the $0$th row of this $N$. – GRS Oct 24 '17 at 13:18
• @GRS First calculate the expected visits in the states $i=1,2,3$ by cutting the chain at $i=3$ (so going to $C$ from state $i=3$ with prob 1). And then add the visits of the chain that has constant $p=0.9$ and starts from the state $i=3$. You might have to subtract $1$ from the expected visits, since the fundamental matrix includes the 'visit' of starting in the state. This works since the chain can't return from higher states to the lower states (except to $C$). This can also be seen from the form of the matrix $Q$ (and $N$ there of): it has a block form so the inverse can be taken separately – ploosu2 Oct 24 '17 at 13:36
• And you must multiply the outcome from the later chain (constant $p$) with the probability of reaching the state $i=3$ in the first chain (calculation of that probability is explained in the linked notes), since the complete chain can go to former states only if it reaches the state $i=3$ first. – ploosu2 Oct 24 '17 at 14:06
• I think I have to correct myself once more: Set the state $i=3$ to also be absorbing and then calculate the probability of reaching it (rather than the state $C$). That is what the later chain expectancies must be multiplied with. – ploosu2 Oct 24 '17 at 15:07
• Thanks a lot :) – GRS Oct 24 '17 at 15:45