Non-exponentially distributed holding times implies non-Markovian?

Question

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?

Answer 1

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)$$

Answer 2

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.