Fly and Spider random walk

Question

A spider and fly move along a straight line at times $t = 0, 1, ...$ The initial position of the fly and the spider are integer. At each time period, the fly moves one unit to the left with a probability $p$, one unit to the right with a probability $p$, and stays where it is with a probability $1 − 2p$. The spider, knows the position of the fly at the beginning of each period, and will always move one unit towards the fly if its distance from the fly is more than one unit. If the spider is one unit away from the fly, it will either move one unit towards the fly, or stay where it is. If the spider and the fly land in the same position at the end of a period, then the spider captures the fly, and the process terminates. The spider’s objective is to capture the fly in minimum expected number of steps.

We have to find two things in the given problem, expected time for the process to end when the initial distance is $1$ apart ($t_1$) and expected time for the process to end when the initial distance is $2$ apart ($t_2$)

Here are my recursive equations for the above, I just wanted to ask if they are correct or not.

So when the distance is $1$, there are six possibilities,

1. fly right, spider left -> $\frac{p}{2}(1+t_1)$
2. fly right, spider stays -> $\frac{p}{2}$
3. fly stays, spider left -> $(1-2p)\frac{1}{2}$
4. fly stays, spider stays -> $(1-2p)\frac{1}{2}(1+t_1)$
5. fly left, spider left -> $\frac{p}{2}(1+t_1)$
6. fly left, spider stays -> $\frac{p}{2}(1+t_2)$

And when the distance is $2$, there are three possibilities (because spider move towards fly always)

1. fly right -> $p$
2. fly stays -> $(1-2*p)(1+t_1)$
3. fly left -> $p(1+t_2)$

So finally we have

$$t_1 = \frac{p}{2}(1+t_1) + \frac{p}{2} + (1-2p)\frac{1}{2} + (1-2p)\frac{1}{2}(1+t_1) + \frac{p}{2}(1+t_1) + \frac{p}{2}(1+t_2)$$

and

$$ t_2 = p + (1-2*p)(1+t_1) + p(1+t_2)$$

Answer 1

One problem in your derivation is that you don't define clearly what each expression signifies. For example, you say

fly right, spider left -> $\frac{p}{2}(1+t_1)$

but you don't explain what the expression is, and you don't justify it. I guess you are using the total expectation law: let $T_k$ be the (random) capture time starting from a distance $k$, so $t_k=E[T_k]$ is the expected capture time, and let $X$ be a random variable that takes values $(-1,0,1)$ and represents the (next) fly movement, and let $Y$ $\in (0,1)$ be the spider movement. Then we can write

$$t_k=E[E[T_k | X,Y]]= \sum P(X=x) P(Y=y) E[T_k | X =x,Y=y]$$

where we've used the fact that $X,Y$ are independent.

A second problem, I think, is interpretation: we're told "The spider’s objective is to capture the fly in minimum expected number of steps." But if you assume that "the strategy has been already given", then does not make sense. I rather think that the point is to obtain the optimal probabilities of the spider movements (which are not given). Let $r$ be $P(Y=0)$ for $k=1$ ( and let $s=1-2p$).

By the symmetry of the problem, it's not necessary to consider the two possible cases for a given $k$, so we could just assume that the fly is on the right. Then

$$t_1= \underbrace{s r (1+t_1)}_{X=Y=0} + \underbrace{s(1-r) }_{X=0 \, Y=1} + \underbrace{p r }_{X=-1 \, Y=0} + \underbrace{p (1-r) (1+t_1)}_{X=-1 \, Y=1} + \underbrace{p r (1+t_2)}_{X=1 \, Y=0} + \underbrace{p (1-r)(1+t_1) }_{X=1 \, Y=1} $$

For $t_2$ we don't need to condition on $Y$, because here $Y=1$ always:

$$t_2 = s (1+t_1) + p + p (1+t_2) $$

(we agree here).

Can you go on from here?