Expected stopping time

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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.