Random walk with a constant delay There is an interesting extension of the standard random walk problem (RW). However, I was having trouble analyzing it.
Like in the case of the regular RW, we look at a one dimensional axis that represents all the integers in $[-\infty,\infty]$ and a starting point $r_0>0$.
At every step $t$, a player that is located at point $r_i$ has a probability $p_r$ to jump to the right, probability $p_l$ to jump to the left and $p_n = 1 - p_r - p_j$ to stay in place.
Probability $p_l$ is constant but $p_r$ changes depending on the history and can be either $p_0$ or $0$. If in the end of a certain step we jumped to the left, $p_r$ stays 0 for $\Delta$ steps, otherwise it is always $p_0$.
Intuitively, this is a RW where upon jumping right, we have to wait a cooldown period.
The question is what is the probability that we reach point $0$ as a function of $r_0$, $\Delta$, $p_l$ and $p_0$.
The answer can be a tight bound.
Since we don't have a memoryless process like in regular RW, all approaches I tried failed.
If you have any ideas or references, I would be happy to hear them.
 A: As you noted, the issue with this process is that it isn't memoryless -- but, you can render a memoryless process out of it. The problematic epochs in the random walk always immediately follow a rightward step, so you might bundle that step along with the next $\Delta$ steps together.
As a concrete example, let's suppose that $p_l = p_r = 0.5$, and that $\Delta = 1$, meaning that after every rightward step, we incur a 1-step censoring penalty for further rightward steps. When we put that rightward step together with the step that follows it, in aggregate those two have a net effect of:

*

*$+1$ with probability $0.5$ (meaning the $\Delta$ step was a rest)

*$0$ with probability $0.5$ (meaning the $\Delta$ step moved backward)

So, we might reimagine our original process as having two steps: a leftward step with probability $0.5$, a rightward step with probability $0.25$, and no movement with probability $0.25$. (The latter two steps are now just a combination of a rightward step and the step immediately following.) This is now a genuine Markov chain, because the censoring action is buried completely inside the step distribution. Moreover, this particular process will drift to $0$ with probability $1$ because its mean increments are negative.
For higher $\Delta$, the only change is that you'd need to build in a binomial variable reflecting how many leftward steps are taken during the penalty period. Conceptually, it's identical to the example I outlined above.

EDIT: Upon reflection of your comments, I don't think I did a good job of answering the question. Specifically, as you noted, I did not adequately answer this part:

The question is what is the probability that we reach point 0 as a function of $r_0$, $\Delta$, $p_l$ and $p_0$. The answer can be a tight bound.

I agree that this is likely to be harder since you want to retain the parametric nature of the problem. Here are some more thoughts of things you could try to circumvent the messy nature of the collapsed process.

*

*Let $\mu$ denote the mean increment of the revised process. (In the example I outlined above, $\mu = -0.25$.) Note that $\mu$ can be rendered parametrically from $p_r, p_l, \Delta$; moreover, if $\mu \leq 0$, then you could make a martingale argument to show that the process will reach $0$ almost surely regardless of its starting point.


*For the case where $\mu > 0$, I think you can adapt the argument here to get a good bound on the probability: https://math.stackexchange.com/a/4532634/485314
