Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I define $X_i$ as a random variable that is uniformly distributed between (0,1). What is the expected number of such variables I require to make the sum go just higher than 1. Thanks

share|improve this question
1  
The answer is $e-1$ because the probability that a sum of $n$ random variables uniformly distributed in [0,1] to be less or equal to 1 is $1/n!$. I remember that a similar question was asked on mathoverflow but I couldn't find the link. –  David Bar Moshe Nov 1 '10 at 13:15
1  
@David Bar Moshe: That can't be right, because the number must be at least 2. –  Nate Eldredge Nov 1 '10 at 13:25
2  
The answer to the question as asked is e. What David Bar Moshe has computed is the expected number of variables added without going over 1. –  Cap Khoury Nov 1 '10 at 14:17
2  
Nate, you are right, thank you for the correction, the right answer is $e$. I had an error in the summation. Also, I managed to find the mathoverflow link: mathoverflow.net/questions/10567/… –  David Bar Moshe Nov 1 '10 at 14:17
    
Thanks for all the answers. I'm actually looking for a precise way of computing this number, I'd be happy you can give me some hints or pointers. I'm actually very new to continuous probability though I have a fair bit of experience in discrete probability –  user2988 Nov 1 '10 at 20:04

3 Answers 3

up vote 5 down vote accepted

I asked a related question in MathOverflow a while back. Here is the link. Let $N$ be the number of $U(0,1)$ random variables needed for the sum to cross $1$. It is in fact possible to derive the pmf of $N$ and compute $E(N)$ as David Bar Moshe has indicated. But there is a nifty derivation if we are only interested in $E(N)$ that involves conditioning on the very first random variable $U_1$ that we pick. I have sketched an outline below. Let me know if any part of the derivation isn't clear.

Let $N(x)$ be expected number of $U(0,1)$ random variables needed for the sum to cross $x$ where $0 \leq x \leq 1$. Then, a recursion can be derived for $f(x) = E(N(x))$ as

$f(x) = \int_{0}^{1} E(N(x) \mid U_1 = y) dy$.

This integral naturally splits into two - that between $0$ and $x$ and that between $x$ and $1$. If $U_1 < x$, $E(N(x))$ is simply $1 + f(x-U_1)$. If $U_1 > x$, $E(N(x))$ is just $1$. This will give us an integral equation for $f(x)$ that can be solved to get the solution (with suitable initial condition) as $f(x) = e^x$.

share|improve this answer

This problem is well-known. For an answer, see, for example, the first part of Section 2 in http://myweb.facstaff.wwu.edu/curgus/Papers/27Unexpected.pdf, or Equations (7)-(10) in http://mathworld.wolfram.com/UniformSumDistribution.html

share|improve this answer

I don't know the exact value, but by Wald's equation it is between 2 and 4.

Edit: Let $N$ be the number of terms required. $N$ is a stopping time for the sequence $X_1, X_2, \dots$, so Wald's equation gives us $$E[X_1 + \dots + X_N] = E[N] E[X_1].$$ We have $E[X_1] = 1/2$, and $1 \le X_1 + \dots + X_N \le 2$, so rearranging gives us $2 \le E[N] \le 4$.

share|improve this answer
    
Can you please elaborate how you used Wald's equation? I'd like to know. –  user2988 Jan 25 '13 at 7:27
    
@user2988: I added some details. –  Nate Eldredge Jan 25 '13 at 13:49
    
Thanks Nate, I have to admit that i don't have much experience with Wald's equation, however, the wikipedia page tells me that N is independent of this sequence, so we cannot define N as stopping time for X1,...,XN. Can you please explain a little more if defining N in this way is fine? –  user2988 Jan 28 '13 at 5:43
    
@user2988: Wald's equation also applies when $N$ is a stopping time. This case is described further down on the Wikipedia page. –  Nate Eldredge Jan 28 '13 at 13:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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