8

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

0fnt
  • 381
  • 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 01 '10 at 13:15
  • 1
    @David Bar Moshe: That can't be right, because the number must be at least 2. – Nate Eldredge Nov 01 '10 at 13:25
  • 3
    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 01 '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: http://mathoverflow.net/questions/10567/number-of-uniform-rvs-needed-to-cross-a-threshold – David Bar Moshe Nov 01 '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 – 0fnt Nov 01 '10 at 20:04

3 Answers3

10

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

Community
  • 1
Dinesh
  • 3,049
6

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

Shai Covo
  • 24,077
3

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

Nate Eldredge
  • 97,710