# Stationary distribution for Markov process with non-exponential waiting times

Stochastic processes often are described in terms of transition rates where the length of time waited before a transition occurs is an exponential random variable.

For example: $0\rightarrow 1$ at rate $\alpha$ and $1\rightarrow0$ at rate $\beta$. I.e. the process waits in state 0 for an exponential length of time with mean wait $1/\alpha$ before jumping to state 1. The stationary distribution for this simple process is $\pi(0)=\beta / (\alpha+\beta)$ and $\pi(1)=\alpha / (\alpha+\beta)$.

What if the wait times were not exponential?

Let $\tau_{ij}$ be the length of time the process sits in state $i$ waiting to jump to state $j$. Let the distributions be given by $\tau_{01}\sim f(t)$ and $\tau_{10}\sim g(t)$ so that $P(\tau_{01}\in A)=\int_Af(t)dt$ etc.

What is the stationary distribution of this new process? Intuitively it seems like it should just depend on the mean length of time spent in each state: $\pi(0)=E(\tau_{01}) / (E(\tau_{01})+E(\tau_{10}))$ etc. However, the transient dynamics will be different according the properties of the distributions.

If this is correct, what if the distributions don't have finite means? Does the stationary distribution still exist and can be discovered via some limiting procedure?

UPDATE: Here is the short answer:

1. The process is not necessarily Markov.
2. Limiting or stationary distributions need not exist.

(Original answer below with some corrections and edits noted.)

Part I: Markov-ness. In general, this is not a Markov process. The exponential distribution is the only continuous distribution with the memory-less property. See this example. Markov processes almost always have exponentially-distributed wait times.

In order for a process to have non-exponential wait times and satisfy the Markov property, knowing the current state must give away the precise time that it entered that state. Consider the process that starts in one state, stays there for some random length of time, then jumps to another state and stays there forever. It's Markov, but not very interesting. Knowing the current state means you know whether or not the jump has occurred and can calculate the distribution of future states precisely.

If the process has two or more states and stays in each state for some non-exponential random time whence jumping to another state occurs, then knowing the current state alone will not allow you to calculate the future distribution of the process.

Part II: Stationarity. The stationary distribution does not generally depend on the expected length of time in each state as my intuition had led me to believe. I'm not completely certain, but think there could be bad enough wait-time distributions that actually cause a stationary distribution to not exist, but I'll ask that in a separate question.

EDIT: @Did has confirmed the above in comments on this answer and showed that I had an error in one of my examples. The text below is edited accordingly.

Example 1: Consider the process where $\tau_{01}$ and $\tau_{10}$ are i.i.d. Then the process has stationary distribution $\pi=[0.5, 0.5].$

If $\tau_{01}$ and $\tau_{10}$ are neither i.i.d. nor exponential, then in general, one cannot be certain of the existence of a either stationary distribution or a limiting distribution. However, as long as the wait times are non-deterministic, a limiting distribution will exist but a stationary distribution may or may not exist.

Example 2: If $\tau_{01}=a$ and $\tau_{10}=b$ with $a< b$, deterministically, then neither a limiting nor a stationary distribution exist. This is easy to see as given any starting state, the distribution will oscillate between $[0, 1]$ and $[1,0],$ and given any initial distribution $\mu$ the distribution at time $t$ will oscillate between $\mu$, $[0,1]$, and $1-\mu.$

Example 3: If either $\tau_{01}$ or $\tau_{10}$ is random (or both), then (as I expected in the question) we have limiting distribution

$$\mu(0)=\frac{E(\tau_{01})}{E(\tau_{01})+E(\tau_{10})}, \quad \mu(1)=\frac{E(\tau_{10})}{E(\tau_{01})+E(\tau_{10})},$$

however if $\tau_{01}$ and $\tau_{10}$ are not identically distributed, then no stationary distribution exists.

Of course, the reader may desire rigorous proofs, but I am unable to provide them currently. I've tested several numerical examples though.

My original mistake was confusing "expected wait-time" with "average time spent in a state over a long period of time covering many jumps between states."

Part III: A 3-state, exponential example. Consider the Markov process:

\begin{aligned} 0\rightarrow 1 \ \text{ at rate } \ a \\ 1\rightarrow 0 \ \text{ at rate } \ b \\ 0\rightarrow 2 \ \text{ at rate } \ c \\ 2\rightarrow 0 \ \text{ at rate } \ d \end{aligned}

The stationary distribution is $$\pi=[bd, ad, bc]\cdot \frac{1}{bd+ad+bc},$$ and $\pi(i)$ does not equal the expected length of time the process remains in state $i.$ I.e. with $\tau_i$ denoting the length of time in state $i$ waiting to jump: $$\pi(0)\neq\frac{1}{A} E(\tau_0)=\frac{\frac{1}{a+c}}{\frac{1}{a+c}+\frac{1}{b}+\frac{1}{d}}$$ $$\pi(1)\neq \frac{1}{A} E(\tau_1)=\frac{\frac{1}{b}}{\frac{1}{a+c}+\frac{1}{b}+\frac{1}{d}}$$ $$\pi(2)\neq \frac{1}{A} E(\tau_2)=\frac{\frac{1}{d}}{\frac{1}{a+c}+\frac{1}{b}+\frac{1}{d}}$$

where $A=\sum E(\tau_i).$

• In Part II, the computation leading to $P(X_t=0)=p_0$ or $1-p_0$ is wrong, for example $P(X_t=0)=0$ for $t$ in $(1,2)$, and there is no stationary distribution, not even $\pi$ such that $\pi(0)=\pi(1)=\frac12$.. Later on, the process based on $(1-\epsilon,1+\epsilon)$ and $(2-\epsilon,2+\epsilon)$ for a small $\epsilon>0$ behaves quite differently from what you seem to believe. Finally, in the last example, the stationary distribution is very much given by the expected lengthes of time the chain remains in each state and also, naturally, by the mean number of visits to each state. – Did May 27 '16 at 22:43
• Re the last model, during a long period of time, the chain passes roughly $(a+c)n$ times by $0$, each time for a sojourn with mean $1/(a+c)$. Likewise, the chain passes roughly $an$ times by $1$, each time for a sojourn with mean $1/b$, and roughly $cn$ times by $2$, each time for a sojourn with mean $1/d$. This makes for total times asymptotically $(a+c)n/(a+c)=n$, $an/b$ and $cn/d$ spent in $0$, $1$ and $2$ during the time needed to jump $(a+c)n+an+cn$ times, thus, a proportion $1/(1+a/b+c/d)$ of time spent in $0$, say, in the long run. – Did May 27 '16 at 22:48
• Your first comment is correct; I originally had all wait times deterministically $1$, if which case the calculation is ok, but Durant give me the contradiction I was looking for. Thanks for checking; I'll do some editing later. I understand your second comment, but it's different from what I was referring to. $\pi(i)\neq E(t_i)/\sum_n E(t_n)$ where $t_i$ is the length of time in state $i$ before jumping. That's what was on my original question. – jdods May 27 '16 at 23:21
• @Did, Regarding the "$\epsilon$" process, I suspected I was probably wrong as eventually it can be any state at any time, even if the wait times converge to deterministic lengths. But it seems like there would be a stationary distribution. There's got to be a simple process that has non-exponential waits where the formula suggested in the original question can be easily shown as incorrect but a stationary distribution still exists. Any thoughts? – jdods May 27 '16 at 23:32
• Sojourn times distributed like $\tau_i$ for $i=0,1$ and deterministic jumps $i\to1-i$ yield convergence of the proportion of time spent in $i$ up to time $t$ to $E(\tau_i)/(E(\tau_0)+E(\tau_1))$, yes. But there is no notion of stationary distribution in general. Recall that $\pi$ is a stationary distribution if $X_t\sim\pi$ implies $X_s\sim\pi$ for every $s>t$. The key point is that if $X$ is not Markov, the distribution of $X_t$ alone does not determine the distribution of $X_s$... And the only case when it does is when each $\tau_i$ is exponential. In this sense, your question is empty. – Did May 29 '16 at 7:26