Suppose we have a particle which start at zero on the set of integers on time $t = 0$ mark this spot with a coloured dot. On $t=1$, mark one of your neighbours with equal probability. Suppose now our particle moves according to the following rules for $t>1$: if both your neighbours are marked, then move to either one of them with probability $\frac{1}{2}$. Else, if there is one neighbour which is not marked, mark that neighbour with a coloured dot with probability $p$ with $p \in (\frac{1}{2}, 1)$ and stay on your current spot or move to your coloured neighbour with probability $1-p$.
Suppose now I'm interested in the expected number of coloured dots at time $t$, let this quantity be denoted by $D_{t}$. I wanted to calculate the expectation in the following way, note that $D_{t} = D_{t-1}+B\cdot\mathbb{I}_{t-1}$ with $B$ a bernoulli distributed random variable with parameter $p$ and $\mathbb{I}_{t-1}$ the indicator function which is $1$ if our particle is on a number which has an unmarked number and zero otherwise. We let $B$ be independent of $D$ or $\mathbb{I}$. Now by linearity of expectation we find that $\mathbb{E}[D_{t}]=\mathbb{E}[D_{t-1}]+p\cdot\mathbb{P}($the probability of our particle being at a spot with an unmarked dot at time $t)$ and that $\mathbb{E}[D_{1}]=2$
I hoped that by solving this problem recursively I wouldn't have to deal with the probability of the position of our particle, which is a bit tedious.I suspect we can find the probability of our particle being at a spot with a neigbour which is unmarked using markov chains, but the markov chain would be quite big and cumbersome. So is this even a winning strategy? Or are there more elegant ways of finding this expectation?
Also, if there is no closed expression for this expectation I am also interested in the following properties: Is the expectation bounded? By which I mean, if $t \to \infty$, does $\mathbb{E}[D_{t}]$ converge? Intuitively, I think this would be the case considering that for large values of $t$, we will have a larg row of marked neigbours and the probability of our particle being at a spot with an unmarked neighbour will approach zero. Therefore our expected value will not grow much in time for $t$ big enough.
Any answers, hints or otherwise helpfull commentary would be greatly appreciated!
It seems much easier to study a sort of "transpose" problem: what is the expected time $T_k$ at which we first have $k$ colored dots?
We can write $T_k = X_1 + X_2 + \cdots + X_{k-1}$, where $X_i$ is the number of steps it takes to go from first having $i$ dots to first having $i+1$ dots.
Each $X_i$ is itself a variable-length sum. Starting one step away from the edge, it takes you $Y_{i,1}$ steps to get to one of the edges. At that point, you flip an $\operatorname{Bernoulli}(p)$ coin to see if you get to color an extra dot. If so, great: you're done. If not, you take $Y_{i,2}$ more steps to get to one of the edges again, and repeat. All told, $$X_i = \sum_{j=1}^{Z_i} Y_{i,j}$$ where $Z_i \sim \operatorname{Geometric}(p)$.
Each segment of the random walk counted by $Y_{i,j}$ ends with a step to the edge and then another guaranteed step: either back to one-away-from-the-edge or coloring a new dot. So $Y_{i,j}$ has the same distribution as the length of a walk in the path graph $P_i$ (on $i$ vertices) where we start on one end and walk until we get back or get to the other end. (This random walk looks superficially different, but it differs only in that instead it has a guaranteed step at the beginning, where we step away from the end of the path.)
We can further recast $Y_{i,j}$ as the length of an excursion from a vertex and back in the cycle graph $C_{i-1}$. This is because we don't care about which end we get to, only that we get to an endpoint, so we can merge the two ends.
So far, everything I've said has been a statement about distributions. I'll go just one step further, and compute the expected value $\mathbb E[T_k]$.
For this, we want $\mathbb E[X_i]$. Since the number of trials $Z_i$ is independent from the lengths of each trial, we have $\mathbb E[X_i] = \mathbb E[Z_i] \cdot \mathbb E[Y_{i,1}]$. $\mathbb E[Z_i] = \frac1{p}$, and $\mathbb E[Y_{i,1}]$ is the length of an excursion in the cycle $C_{i-1}$, which is $i-1$. Therefore $\mathbb E[X_i] = \frac{i-1}{p}$, with the exception of $\mathbb E[X_1] = 1$.
So $\mathbb E[T_k] = 1 + \sum_{i=2}^{k-1} \frac{i-1}{p} = 1 + \frac{(k-1)(k-2)}{2p}$.
It probably shouldn't be too hard to prove some sort of concentration on $T_k$. This will let you get back to the distribution of $D_t$: if $T_k$ is certain to be very very close to $\frac{k^2}{2p}$, then we can conclude that $D_t$ is likely to be close to $\sqrt{2pt}$. Without learning more about $T_k$, though, we can't even make any conclusions about $D_t$'s expected value.