# Non-exponentially distributed holding times implies non-Markovian?

I'm learning about continuous-time Markov chains and am trying to hone my intuition.

Let $T_1, T_2, \ldots$ be i.i.d random variables.

Let $S$ be some state space, we can take it to be finite. Let $P$ me some Markov transition matrix defined on $S$. Let $X_1, X_2, \ldots$ be a corresponding sequence of random variables distributed according to this discrete-time Markov chain.

Consider the following process: Start in state $X_1$, wait for time $T_1$, transition to state $X_2$, wait for time $T_2$, transition to state $X_3$, etc...

My understanding is that this defines a continuous-time Markov chain if and only if the $T_i$ are exponentially distributed. Correct?

So if the $T_i$ are, say, uniformly distributed in $[0,1]$, then we don't get a Markov process? How exactly does having uniform hold times give the process memory?

• If for all $t\geqslant 0$, $i,j\in S$, and positive integers $n$ $$\mathbb P(T_{n+1}\leqslant t, X_{n+1}=j\mid (X_0,T_0),\ldots, (X_n=i,T_n) = \mathbb P(T_{n+1}\leqslant t, X_{n+1}=j\mid X_n=i),$$ then the sequence $\{(X_n,T_n)\}$ is a Markov renewal process, and the process $$Y_t = X_n\cdot\mathsf 1_{[T_n,T_{n+1})}(t)$$ is a semi-Markov process. Intuitively, $Y_t$ has the Markov property only at the jump times. – Math1000 May 26 '18 at 1:02
• It depends. It can be Markov, but most probably won't be. See one of my old posts: math.stackexchange.com/questions/1372024/… – jdods May 26 '18 at 1:04
• @Math1000 So you are essentially augmenting the state space to include a time coordinate? I guess you can do this to any sort of process and get something Markovian? Is there a catch? Is there some sort of theory that characterizes what happens when you do this? – theQman May 26 '18 at 1:49
• A Markov process has the Markov property at all times. A semi-Markov process only has the Markov property at jump times. And yes, Markov renewal processes are a generalization of discrete-time Markov chains, continuous-time Markov chains, and renewal processes. – Math1000 May 26 '18 at 2:15

Suppose $T_i$ are iid uniform over (0,1). If you have waited 0.9 units of time, then you know with certainty that there will be an event within 0.1 unit of time. On the other hand, if the last event happened 0.5 units of time ago, then the next event will happen in 0.1 with only 20% probability. Therefore, future events are not independent of past events conditioned on the present. That is, the process is not Markov.

The exponential distribution is special because of its memoryless property. That is, if $T_i$ are iid exponential, then it doesn’t matter how long you’ve been waiting, the probability that he next event will happen within 0.1 unit of time will remain the same. That is,

$$\mathbb{P}(T_i < s+ t| T_i > t) = \mathbb{P}(T_i < s)$$

The exponential distribution is the $\mathbf{\underline{only}}$ distribution that has the memoryless property. See this MathSE post.

Now that doesn't necessarily imply a Markov process must have only exponential jump times, but any examples without exponential jump times will likely be fairly trivial. The requirement is that the distribution of the future states of the process only depend on the most recent state known and not any other information about the past.

To answer your question: "how does having a non-exponential distribution give the process memory?" It is simply because The distribution of the process at a future time will depend on more than just the most recently known state. Memorylessness means not that we don't know the past, but that we don't need to know it (except for the most recent memory). I.e. that $P(X_t\in A \mid X_s \text{ for } s\leq s_0<t)=P(X_t\in A \mid X_{s_0})$.

With a uniform wait time, there is a maximum amount of time that will be spent in that state. Without knowing when the state was entered, there is no way to calculate probabilities on when it will leave the state.

Even if we choose some other nonuniform random distirbution that has support on $[0,\infty)$ that isn't exponential, it still won't have the memoryless property though, since as discussed above, the exponential is the only distribution with this property.

See this MathSE post for a process with uniform jump times and is not Markov.

Here is a MathSE post that is relevant. Here is the important paragraph:

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.

Example of a process with a uniform jump time that is Markov:
Consider the process that starts in state $0$ and jumps to state $1$ after a uniform time in $[0,1]$. Let's assume that we know $X_s$ for all $s\leq s_0$. We want to show that $$P(X_t\in A\mid X_s \text{ for } s\leq s_0<t)=P(X_t \in A\mid X_{s_0})$$ so that this process does indeed have the Markov property.

Let $t<1$. If $A=\{0\}$, then $P(X_t=0\mid X_s \text{ for } s\leq s_0<t)$ equals $0$ if $X_s$ is $1$ (the jump has already occurred) for any $s\leq s_0$ (i.e. if $X_{s_0}=1$, so we only need to know $X_{s_0}$). Furthermore, $P(X_t=0\mid X_s \text{ for } s\leq s_0<t)$ equals $P(u> t \mid u>s_0)=P(X_t=0 \mid X_{s_0}=0)$. So we conclude that $$P(X_t=0\mid X_s \text{ for } s\leq s_0<t)=P(X_t=0 \mid X_{s_0})$$

Similarly, if $A=\{1\}$, then $P(X_t=1\mid X_s \text{ for } s\leq s_0<t)$ equals $1$ if the jump has already occurred, that is if $X_{s_0}=1$. And it equals $P(u\leq t \mid u>s_0)=P(X_t=1 \mid X_{s_0}=0)$ if the jump has not occurred yet during the know interval $[0,s_0]$.

Let $t\geq 1$. Then $P(X_t=0\mid X_s \text{ for } s\leq s_0<t)=P(X_t=0\mid X_{s_0})=P(X_t=0)=0$ and $P(X_t=1\mid X_s \text{ for } s\leq s_0<t)=P(X_t=1\mid X_{s_0})=P(X_t=1)=1$.

Thus $$P(X_t \in A\mid X_s \text{ for } s\leq s_0<t)=P(X_t \in A \mid X_{s_0}).$$

So this is indeed a Markov process where the wait time is not exponentially distributed.

For an even more trivial example, consider the process $X_t=1$ for all $t\in[0,\infty)$. Trivially, $$P(X_t\in A \mid X_s, s\leq s_0)=\begin{cases} 0 &\text{ if } 1\notin A\\ 1 &\text{ if } 1\in A \end{cases}$$ and $$P(X_t\in A \mid X_{s_0})=\begin{cases} 0 &\text{ if } 1\notin A\\ 1 &\text{ if } 1\in A \end{cases}$$ showing that it is indeed a (trivial) Markov process.