Deceptively simple problem to find expected number of seconds it takes a particle to exit $(-1, 1)$

Question

I've been working through past MIT Primes problems, and got stuck on 2021 Problem M4:

A particle is initially on the number line at a position of $0$. Every second, if it is at position $x$, it chooses a real number $t \in [−1, 1]$ uniformly and at random, and moves from $x$ to $x+t$. Find the expected value of the number of seconds it takes for the particle to exit the interval $(−1, 1)$.

I've been trying to solve it differently from the solution they provided. Let me outline my approach.

---

Let $X$ denote the number of seconds it takes the particle to exit $[-1, 1]$. Then, we are looking for

$$ \text{E}[X] = \sum_x x \Pr(X=x) $$

The PMF of $X$ is

$$ \Pr(X = x) = \Big( 1 - \Pr(-1 < X_x < 1) \Big) \prod_{i=1}^{x-1} \Pr(-1 < X_i < 1) $$

where $X_t$ is $X$ at time $t$. We have now punted the problem to finding $\Pr(-1 < X_i < 1)$ for all $i$. Remember, each $X_i$ is dependent on $X_{i-1}$. We can make a step towards finding $\Pr(-1 < X_i < 1)$ using the law of total probability:

$$ \Pr(X_i \leq x) = \int_{-\infty}^\infty \Pr(X_i \leq x \mid X_{i-1}=y) f_{X_{i-1}}(y) \ \text{d}y $$

$\Pr(X_i \leq x \mid X_{i-1}=y)$ can be defined as a piecewise function (I derived this by fixing $y$, and then considering $x$):

$$ \Pr(X_i \leq x \mid X_{i-1}=y) = \begin{cases} \frac{x+1}{2+y} & -1 \leq y < 0 \; \land \; x \leq y + 1 \\ 1 & -1 \leq y < 0 \; \land \; x > y + 1 \\ \frac{x-y+1}{2-y} & 0 \leq y < 1 \; \land \; x \geq y - 1 \\ 0 & 0 \leq y < 1 \; \land \; x < y - 1 \end{cases} $$

We also know that $f_{X_{i-1}}(y)$ is the derivative of $\Pr(X_{i-1} \leq y)$. Because $\Pr(X_1 \leq x) = (x + 1)/2$, we can now find $\Pr(X_2 \leq x)$.

---

Now here is the problem. I evaluated $\Pr(X_2 \leq x)$ using the following Mathematica script:

(* the piecewise function *)
XiCDFconditional[x_, y_] = Piecewise[{
    {(x + 1) / (2 + y), -1 <= y < 0 && x <= y + 1},
    {1, -1 <= y < 0 && x > y + 1},
    {(x - y + 1) / (2 - y), 0 <= y < 1 && x >= y - 1},
    {0, 0 <= y < 1 && x < y - 1}
}];
X1CDF[x_] = (x + 1) / 2;
(* Pr(X2 <= x) *)
X2CDF[x_] = Integrate[XiCDFconditional[x, y] * X1CDF'[y], {y, -Infinity, Infinity}]

when I execute X2CDF[1] - X2CDF[-1] (i.e. $\Pr(-1 \leq X_2 \leq 1)$), I get $1$, which is obviously incorrect. Where did I screw up?

I feel like I might have subtly screwed up $\Pr(X_i \leq x \mid X_{i-1}=y)$. Or maybe I didn't screw up, and I'm almost surely (pun intended) getting confused in the continuous world.

Answer 1

As discussed in the comments, this approach isn't going to work as it stands, because the positions at different times aren't independent. But just to answer the original question: because the jumps $(t\in[-1,1])$ are chosen uniformly, and in particular don't depend on the initial position, you must have $\Pr(X_i \leq x \mid X_{i-1}=y)=g(x-y)$ for some $g$. (In other words, only the distance from the old position to the new one can matter.) And pretty clearly this should be $$ \Pr(X_i \leq x \mid X_{i-1}=y) = \begin{cases} 0 \qquad &\text{if }& x-y<-1; \\ \frac{1}{2}(x-y+1) \qquad &\text{if }& x-y \in [-1,1]; \\ 1 \qquad &\text{if }& x-y>1. \end{cases} $$ If you fix $y$ and take the derivative with respect to $x$, then this gives you the expected and properly normalized probability distribution for the position after a random jump starting at $y$: zero outside the interval $[y-1,y+1]$, and uniformly equal to $1/2$ inside it.

Answer 2

Your notation is really confusing! Let $X_n$ be the position of the particle at time $n$, and let $N$ be the first exit time from $(-1,1)$. As others have already mentioned, your first line is already totally wrong: the events $X_i \notin (-1,1)$ are not independent for different $i$, so you can't decompose $P(X_n = x)$ as a product over previous times. An explicit expression for $P(X_n \in (-1,1))$ would be more than enough to get the expected exit time, by summing:

$E[N] = \sum_{n \geq 0} P(N > n) = \sum_{n \geq 0} P(X_n \notin (-1,1)).$

There is a standard method to solve these kinds of problems, where you form a martingale out of the underlying random walk and use the optional stopping theorem (see this nice post, for example: Variance of exit time for simple symmetric random walk). Namely,

$\frac{1}{2} X_n^2 - \frac{1}{6} n$

is a martingale, and applying the optional stopping theorem gives

$E[N] = 3 E[X_N^2].$

This doesn't quite give the answer, since $X$ has continuous steps (for SRW, for example, $X_N$ is a Bernoulli random variable, so the story ends here). Generally though, this method is really robust. To get an explicit expression for $P(N > n)$, you could use the full exponential martingale and (try to) do a Laplace transform.

Here's an elementary approach that follows the hint from the problem set you linked. Write $n(x)=n(-x)$ for the expected exit time started from position $X_0 = x \in (0,1)$, and use a one-step decomposition (I think this is usually called the renewal equation):

$n(x) = 1+\int_{-1}^1 \frac{1}{2}n(x+t) dt.$

This comes from taking one step, then adding the expected exit time from your new location $x + t$. Using that $n$ is even, $n(x') = 0$ for $x' \notin (-1,1)$ and taking a derivative gives the equation

$2n'(x) = 1-n(1-x)$ for $x \in (0,1)$.

Playing with this equation a little bit gives $n = 1-4n''$, which can be solved explicitly.