# Calculate the expected time for the spider to catch the fly.

The question:

A spider and a fly move along a straight line. At each second , the fly moves a unit step to the right or to the left with equal probability $$p$$, and stays where it is with probability $$1 - 2p$$. The spider always takes a unit step in the direction of the fly. The spider and the fly start D units apart. If the spider lands on top of the fly, it's the end. What is the expected value of the time it takes for this to happen?

What I've tried:

Define

$$A_d$$: The event that initially the spider and the fly are $$d$$ units apart.

$$B_d$$: The event that after one second the spider and the fly are $$d$$ units apart.

Let $$E(T|A_d)$$ be the expected amount of time for the spider to catch the fly for an initial distance of $$d>1$$.

Then, $$E(T|A_{d})=p(1+E(T|A_{d}))+p(1+E(T|A_{d-2}))+(1-2p)(1+E(T|A_{d-1}))$$.

This yields $$E(T|A_{d})-E(T|A_{d-1})=1+p((E(T|A_{d})-E(T|A_{d-1}))-(E(T|A_{d-1})-E(T|A_{d-2})))$$.

$$E(T|A_{d})-E(T|A_{d-1})=\frac{1}{1-p}-\frac{p}{1-p}(E(T|A_{d-1})-E(T|A_{d-2}))$$

$$\sum_{d=2}^{D} E(T|A_{d})-E(T|A_{d-1})=\sum_{d=2}^{D}(\frac{1}{1-p}-\frac{p}{1-p}(E(T|A_{d-1})-E(T|A_{d-2})))$$

$$E(T|A_D)-E(T|A_1)=\frac{D-1}{1-p}-\frac{p}{1-p}(E(T|A_{D-1})-E(T|A_0))$$

As $$E(T|A_0)=0$$,

$$E(T|A_{D})=E(T|A_1)+\frac{D-1}{1-p}-\frac{p}{1-p}E(T|A_{D-1})$$

In the solution of the book I'm referring to, they also evaluate $$E(T|A_1)$$ as follows:

$$A_1=(A_1 \cap B_1) \cup (A_1 \cap B_0)$$

$$E(T|A_1)=P(B_1|A_1)E(T|A_1 \cap B_1) + P(B_0|A_1)E(T|A_1 \cap B_0)$$

From the problem data, $$P(B_1|A_1)=2p$$, $$P(B_0|A_1)=1-2p$$, $$E(T|A_1 \cap B_1)=1+E(T|A_1)$$ and $$E(T|A_1 \cap B_0)=1$$.

So, $$E(T|A_1)=2p(1+E(T|A_1))+(1-2p)$$ or $$E(T|A_1)=\frac{1}{1-2p}$$

So, $$E(T|A_{D})=\frac{1}{1-2p}+\frac{D-1}{1-p}-\frac{p}{1-p}E(T|A_{D-1})$$

$$\tag*{where D>1 and E(T|A_1)=\frac{1}{1-2p}}$$

I'm not sure how to solve from here to get the expression for $$E(T|A_D)$$. Any assistance would be appreciated.

• I have not gone through all your calculations, but often with problems like these where there are couple of parameters, I first try to simplify it but actually choosing a value of $p$ and a value of $D$ and then try to calculate the expected time. From there, seeing how to numbers come into place, I would try to generalize it. – imranfat Jun 12 '19 at 16:07
• The distance between fly and spider reduces by either $0$, $1$, or $2$ units during a turn, so I would expect you to find a recurrence that relates three expected times. (Indeed, if $p=\frac12$, the fly will be safe forever if only the distance is odd, and it looks unlikely that this can be predicted by a first-order recurrence). – hmakholm left over Monica Jun 12 '19 at 16:20
• @HenningMakholm In the recurrence I started with, I had three terms, $E(T|A_d), E(T|A_{d-1})$ and $E(T|A_{d-2})$. I was able to simplify that to a recurrence with only two terms. – Amit Rajaraman Jun 12 '19 at 16:32
• Sorry to be nitpicky, but what happens if the fly is $1$ unit to the right of the spider, and decides to move left $1$ unit while the spider moves right $1$ unit? Do they miss each other??? Or does this still count as the end? – antkam Jun 12 '19 at 18:05
• @antkam They miss each other. This is what is explained in the quoted part from the book. The only way they hit each other if they are next to each other is if the fly remains still. – Amit Rajaraman Jun 12 '19 at 18:13

I managed to solve it myself after a while:

$$E(T|A_{D})=\frac{1}{1-2p}+\frac{D-1}{1-p}+\frac{p}{p-1}E(T|A_{D-1})$$

$$(\frac{p-1}{p})^{D}E(T|A_{D})=\frac{1}{1-2p}(\frac{p-1}{p})^{D}+\frac{D-1}{1-p}(\frac{p-1}{p})^{D}+(\frac{p-1}{p})^{D-1}E(T|A_{D-1})$$

Putting $$(\frac{p-1}{p})^{D}E(T|A_{D})=F_D$$,

$$F_D-F_{D-1}=\frac{1}{1-2p}(\frac{p-1}{p})^{D}+\frac{D-1}{1-p}(\frac{p-1}{p})^{D}$$

$$\sum_{D=2}^{N}F_D-F_{D-1}=\sum_{D=2}^{N} (\frac{1}{1-2p}(\frac{p-1}{p})^{D}+\frac{D-1}{1-p}(\frac{p-1}{p})^{D})$$

$$F_N-F_1=\sum_{D=2}^{N} (\frac{1}{1-2p}(\frac{p-1}{p})^{D}+\frac{D-1}{1-p}(\frac{p-1}{p})^{D})$$

$$F_1=\frac{p-1}{p}E(T|A_1)=\frac{p-1}{p(1-2p)}$$

On evaluating the right side, we get the required result:

$$E(T|A_N)=\frac{2p(p-1)((\frac{p}{p-1})^N-1)}{1-2p}+N$$

Edit: For $$p=\frac{1}{2}$$ and even $$N$$, calculate the limiting value of the expression of $$E(T|A_N)$$ as $$p \to \frac12$$.

• When $p=\frac{1}{2}$ your answer gives infinite expected time for all values of $N$ which looks strange because fly would be save forever in this case only when initial distance is odd. For example $E(T|A_2) = 4$ in this case. – Anton Grudkin Jun 13 '19 at 12:58
• If $p=\frac{1}{2}$, then it will be infinite expected time for only odd $N$. For even $N$, both the numerator and denominator will tend to $0$ in the first term. If we evaluate the limit of the first term as $p \to \frac{1}{2}$, it will give the required answer. For example, $\lim_{p \to \frac{1}{2}} \left( \frac{2p(p-1)((\frac{p}{p-1})^2-1)}{1-2p}+2 \right) = 4$ which, as you mentioned, is $E(T|A_2)$. I edited my answer to include this. – Amit Rajaraman Jun 13 '19 at 13:17
• Oh, indeed, you are right – Anton Grudkin Jun 13 '19 at 13:30

Writing down what said in the question we get for $$n > 1$$ $$E(T|A_n) = pE(T|A_n \cap B_{n-2}) + (1-2p)E(T|A_n \cap B_{n-1}) + pE(T|A_n \cap B_n).$$ From $$E(T|A_n \cap B_m) = 1 + E(T|A_m)$$ we get following recurrent sequence $$E_n = E(T|A_n)$$: $$E_n = \frac{1}{1 - p} + \frac{1 - 2p}{1- p}E_{n-1} + \frac{p}{1 - p}E_{n-2}$$ with initial conditions $$E_0 = 0$$ and $$E_1 = \frac{1}{1 - 2p}$$.

• That was what I wrote in my first step as well, I don't know how to solve the recurrence though. – Amit Rajaraman Jun 13 '19 at 2:57