8
$\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

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 1, 2010 at 13:15
  • 1
    $\begingroup$ @David Bar Moshe: That can't be right, because the number must be at least 2. $\endgroup$ Nov 1, 2010 at 13:25
  • 3
    $\begingroup$ 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. $\endgroup$
    – Cap Khoury
    Nov 1, 2010 at 14:17
  • 2
    $\begingroup$ 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/… $\endgroup$ Nov 1, 2010 at 14:17
  • $\begingroup$ 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 $\endgroup$
    – 0fnt
    Nov 1, 2010 at 20:04

3 Answers 3

10
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ @user2988: I added some details. $\endgroup$ Jan 25, 2013 at 13:49
  • $\begingroup$ @user2988: Wald's equation also applies when $N$ is a stopping time. This case is described further down on the Wikipedia page. $\endgroup$ Jan 28, 2013 at 13:34

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .