9
$\begingroup$

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

  • 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.2010-11-01
  • 1
    @David Bar Moshe: That can't be right, because the number must be at least 2.2010-11-01
  • 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.2010-11-01
  • 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-threshold2010-11-01
  • 0
    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 probability2010-11-01

3 Answers 3

8

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

5

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

2

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

  • 0
    @user2988: I added some details.2013-01-25
  • 0
    @user2988: Wald's equation also applies when $N$ is a stopping time. This case is described further down on the Wikipedia page.2013-01-28