2
$\begingroup$

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.

$\endgroup$
3
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Many thanks. How did you know the method? $\endgroup$
    – darlove
    Jun 26 '17 at 16:51
  • $\begingroup$ 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$). $\endgroup$
    – darlove
    Jul 4 '17 at 16:21
  • $\begingroup$ Well spotted. The answer is revised, adopting your definition. $\endgroup$
    – Did
    Jul 11 '17 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.