Consider a chain which is not Markov that waits a time $T^{*}$ before leaving the current state, where $T^{*}$ has uniform distribution over the set of times $\{1, 2, 3, 4\}$ . I would like to show that it does not hold the memoryless property, i.e: $$\Bbb P(T \gt t+s \mid T \gt t)= \Bbb P(T \gt s)$$
So, here's how I tackle the problem:
I deduce that $T^{*}\sim\mathcal U\{1,4\}$ (discretely uniformly distributed on the interval $[1,4]$. So, the support is $x\in \{1,2,3,4\}$
The cumulative distribution function is:
$$\text{CDF}= \frac{\lfloor x \rfloor - 1+1}{4} = \frac{\lfloor x \rfloor}{4}= \Bbb P(T \leq x)$$
$$\Rightarrow 1- \text{CDF} = \Bbb P(T \geq x)= 1- \frac{\lfloor x \rfloor}{4}= \frac{4-\lfloor x \rfloor}{4}$$
$$\Rightarrow \Bbb P(T \geq s+t | T \geq t)= \frac{\Bbb P(T\geq s+t ; T\geq t)}{\Bbb P(T \geq t)}= \frac{\Bbb P(T \geq s+t)}{\Bbb P(T \geq t)} = \frac{\frac{4- \lfloor s+t \rfloor}{4}}{\frac{4- \lfloor t \rfloor}{4}}= \frac{4 - \lfloor s+t \rfloor}{4 - \lfloor t \rfloor} \neq \Bbb P(T\geq s) = \frac{4- \lfloor s \rfloor}{4}$$ Hence $T^{*}$ does not hold the memoryless property
Is this alright?
Also, if $(W_k)_{k\geq}$ would be a stochastic process constructed so that it stays in each state $i$ for a time distributed to $T^{*}$, what would be an intuitive explanation of why this is not a Markov chain?
I assume your $T$ and $T^*$ are the same thing. The memoryless property is that, for all values of $s,t$:
$$P(T > t + s \mid T > t) = P(T > s)$$
So to show that $T$ lacks the memoryless property, all you need is to find one counter-example - you do not need to show that the equation is invalid generally.
In this case almost every example you find is already a counter-example, e.g. pick $s = t = 2$:
$$P(T > 2 + 2 \mid T > 2) = 0 \neq P(T > 2) = 1/2$$