# Compute $P(X_1+\cdots+X_k\lt 1)$ for $(X_i)$ i.i.d. uniform on $(0,1)$

Consider $N=\min\{n: S_n>1\}$, where $S_n=X_1+\cdots+X_n$ and $(X_i)_{i=1}^\infty$ is i.i.d. uniform on $(0,1)$. So, $N$ is the first time that $(S_n)_{n=1}^\infty$ crosses $1$. I'd like to calculate $E(N)$. To this end I'd like to calculate $\Pr(N\gt k)=\Pr(S_k\lt 1)$.

Is there a way to actually do this for any arbitrary $k$? I mean, certainly there is as I know about the distribution of $S_n$ but the formula is just formidable when you move with $k$ toward $\infty$ and even though tractable with a computer, I don't think it's tractable without it.

Is there maybe a better way to calculate the expectation? Thanks for any help.

• Do you mean $N=\min\{n: S_n>1\}$? Jun 26 '17 at 16:32
• Sure, it must be a MIN. Sorry for the mistake :) Jun 26 '17 at 16:32
• Oct 8 '20 at 15:39

This is a typical situation where enlarging the problem makes it easier to solve... That is, consider $N_x=\max\{n: S_n\leqslant x\}$ for every $x$, then $N$ in the question is $N_1$ hence one is after $u_k(1)=P(N>k)$ where, for every $x$ and $k$, $$u_k(x)=P(N_x>k)$$ Conditioning on the value of $X_1$, one gets, for every $x$ in $[0,1]$, $$u_k(x)=\int_0^xu_{k-1}(x-y)dy=\int_0^xu_{k-1}(y)dy$$ Thus, $$u'_k(x)=u_{k-1}(x)$$ and, since $u_0(x)=1$ for every positive $x$ and $u_k(0)=0$ for every $k$, $$u_k(x)=\frac{x^k}{k!}$$ in particular, $$P(N>k)=u_k(1)=\frac1{k!}$$ This question is related, and shows how to compute $E(N)$ without computing the full distribution of $N$ as above.
Edit: Re-reading the question, I am not sure why you failed to use PDFs since, as shown by a simple recursion, the PDF $f_k$ of each $S_k$, when restricted to $[0,1]$, is merely $$f_k(x)=\frac{x^{k-1}}{(k-1)!}$$ hence $$P(S_k<1)=\int_0^1\frac{x^{k-1}}{(k-1)!}dx=\frac1{k!}$$ True, the full PDF of each $S_k$ is more complicated, coinciding with some specific polynomial on each interval $(i-1,i)$ for $1\leqslant i\leqslant k$, but here, one can take advantage of the fact that the PDF is relevant, only on $(0,1)$.
• I've noticed that instead of considering $N_x=max\{n:x+S_n\le 1\}$ you could consider $N_s=max\{n:S_n\le s\}$ where $s\in\left(0, 1\right]$. The formulae would be a bit easier (no negative derivative and $x$ instead of $1-x$). Jul 4 '17 at 16:21