# Expected stopping time

Let $X_1,X_2,\ldots,$ be iid uniform in $[0,1]$ and define $S_n:=\sum_{i=1}^n X_i$. Let $\tau$ be the smallest $n$ for which $S_n>1$. It is known that $E[\tau]=e\approx 2.7183$, and this can be easily shown using the Irwin-Hall https://en.wikipedia.org/wiki/Irwin%E2%80%93Hall_distribution distribution. Indeed, $$P(\tau\ge n) = P(S_{n-1}< 1)=1/(n-1)!,$$ whence $$E[\tau]=\sum_{n=1}^\infty P(\tau\ge n) = \sum_{n=0}^\infty 1/n! = e.$$ Here, all of the heavy-hitting is done by the Irwin-Hall distribution, and I'm wondering: is there a clever "soft" martingale argument that gives the answer with less heavy-hitting?

• Typo in the discussion: $S_n$ should be $S_{n-1}$. It should read $P(\tau \ge n)=P(S_{n-1} \le 1)=1/{(n-1)!}$ Aug 31, 2017 at 23:47
• Thanks @yuval, fixed. Sep 1, 2017 at 7:28

The linear map $T(x):=(x_1,x_1+x_2,\ldots,x_1+\ldots+x_n)$ taking a vector in $[0,1]^n$ to its partial sums is volume preserving, as it corresponds to a triangular matrix of determinant 1 (or by induction.) Consider the set $A_n$ of vectors $x$ in $[0,1]^n$ such that $x_1+\ldots+x_n \le 1$. The image $T(A_n)$ is the simplex $\{y \in [0,1]^n: y_1 \le y_2 \ldots \le y_n \}$ that has volume $1/n!$ by symmetry. Therefore Vol$(A_n)=1/n!$ as well. In other words, ${\bf P} (\tau>n)={\bf P}(S_n \le 1)=1/n!$.

For $x \in [0, 1)$, let $\tau(x)$ denote the smallest $n$ for which $S_n > x$. Let $g(x) := E[\tau(x)]$. We're interested in $g(1)$.

Using its definition, $g$ satisfies an integral recurrence

$$g(x) \ = \ \int_{y = 0}^{x} [1 + g(x - y)] \ dy \ + \ \int_{y = x}^{1} 1 \ dy$$

which if I'm not mistaken, is satisfied by the function $e^{x}$. It also satisfies the "limit boundary condition" $\lim_{x \rightarrow 0} g(x) = 1$, which I believe can be established using crude arguments. I am not going to attempt to argue that these two conditions force the unique solution $g(x) = e^{x}$, but it looks true and doable.

(Note, this might be isomorphic to some of the work on Irwin-Hall; I haven't checked.)

• Hi Andy- indeed, the same argument as the one in my answer above shows that ${\bf P}(\tau(x)>n)=x^n/n!$ . Summing this over all $n \ge 0$ yields ${\bf E}(\tau(x))=e^x$. Aug 31, 2017 at 23:58
• Please excuse the fact that my answer is basically the same as this one. Mine is a little bit different in that it emphasizes that this technique is quite general for calculating expected hitting times of Markov processes, but for this particular problem they are almost exactly identical.
– Ian
Sep 1, 2017 at 2:16

One way, although it does not use martingales, is to consider a discrete time Markov process whose state space is $[0,1] \cup \{ \square \}$ (the choice of symbol for the extra state is not important). This process says that $X_{n+1}$ conditioned on $X_n$ is equal to $X_n+u$ for $u \sim U([0,1-X_n])$ with probability $1-X_n$ and is equal to $\square$ with probability $X_n$. And $X_{n+1}$ conditioned on $X_n=\square$ is $\square$. Define

$$(Pf)(x)=E[f(X_{n+1}) \mid X_n=x]$$ Explicitly: $$(Pf)(x)=\int_x^1 f(y) dy + x f(\square) \quad x \in [0,1] \\ (Pf)(\square)=f(\square).$$

Then define $L=P-I$. Renewal theory tells you that if $\tau$ is the time to hit $\square$ then $E[\tau \mid X_0=x]$ satisfies the equation

$$(Lu)(x)=-1 \quad x \in [0,1] \\ u(\square)=0$$

which expands out to

$$\int_x^1 u(y) dy - u(x) = -1 \quad x \in [0,1].$$

You want $u(0)$. Differentiating, you get $-u(x)-u'(x)=0$ so that $u=Ce^{-x}$. Plugging back into the integral equation you get $-\frac{C}{e}=-1$ so $C=u(0)=e$. Alternately you could note that $u(1)$ must be $1$ (why?) and get the same result.

When I say "renewal theory" this is not really something complicated; it is just saying that $E[\tau \mid X_0=x]$ is $E[\tau \mid X_1=y]$ integrated in $y$ against the conditional distribution of $X_1$ given $X_0=x$. Then the thing being integrated is the same as $1+E[\tau \mid X_0=y]$, where this $1$ takes into account the fact that a step takes $1$ time.