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

Question

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.

Answer 1

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$.

Answer 2

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}$.