# sum of independent variables

Suppose you have a sum of IID random variables (uniformly distributed in [0, 1])
$$S = \sum_{i=1}^N X_i$$
if I want to have a rough idea of the average value of $N$ such that the sum is equal to some number $S_0$ is it safe to say that $N$ is going to be around $S_0/{\rm E}[X_i]$ (assuming I'm not under the conditions of using Martingale).

UPDATE: I reformulate the problem. Suppose $N$ is a random variable defined as the smallest integer such that $$\sum_{i=1}^N X_i \geq S_0$$ where $X_i$ are IID and uniformly distributed in $[0, x_0]$, with $x_0 < S_0$. What is $E[N]$?

-
"assuming I'm not under the conditions of using martingale" -- Can you clarify what this means? – Srivatsan Jan 4 '12 at 22:51
@Bob $S$ is continuous random variable that follows Irwin-Hall distribution. The probability that it is equal to any specific value is zero, as for any other continuous RV. You should think in terms of $\mathbb{P}(S > S_0) > \alpha$ instead. – Sasha Jan 4 '12 at 22:52
In the light of @Sasha's comment, see if the following is a suitable formalisation of your question: If the random variable $N$ is defined as the smallest number such that $\sum \limits_{i=1}^{N} X_i$ exceeds $S_0$, then what is $\mathbf E[N]$? Is it approximately equal to $\frac{S_0}{\mathbf EX_i}$. – Srivatsan Jan 4 '12 at 22:55
If $N:=\inf\{n:S_n\geq S_0\}$, then Wald's Equation gives that $\mathbb{E}[S_N]=\mathbb{E}[N]\mathbb{E}[X_1]$, giving bounds on $\mathbb{E}[N]$. – Ben Derrett Jan 4 '12 at 23:20
yes, you are both right. I wanted to know $E[N]$ according to Srivatsan's formulation of the problem and, if possible, some higher order statistics. – ACAC Jan 4 '12 at 23:20

$S_N \ge S_0$ (horrid notation) so I would expect $E[N]$ to be greater than $\frac{S_0}{E[X_i]}$.

With $X_i$ iid uniform on $[0,1]$, then $E[X_i]=\frac{1}{2}$ and $\frac{S_0}{E[X_i]}=2S_0$.

For $S_0=1$ I seem to recall from this Ponder This question $E[N]=\exp(1) \approx 2.718$ (it must be more than $2$).

A slightly weaker recollection is that as $S_0$ increases: $E[S_N-S_0] \rightarrow \frac{1}{3}$ and $E[N]-2S_0 \rightarrow \frac{2}{3}$.

Added: my recollection is now stronger, and I gave some detail at a sci.math thread. For $N\ge 3$ the $\frac{2}{3}$ convergence is very close, and this is related to $$\lim_{n->+\infty}\left(\sum_{i=1}^{n}\frac{(-i)^{n-i}e^i}{(n-i)!}\right)-2n=\frac{2}{3­}$$

There I gave the argument: Consider the total distance $N+E$ when the total first hits or exceeds $N$, with a final step $F$. So both the excess distance $E$ and the final step $F$ are in $[0,1]$ with $F\gt E$. $F$ will tend to be big because it is conditioned on passing $N$, while $E$ will tend to be small since it is conditioned on $N$ having been passed.

For large $N$, the probability density of $F$ is close to $2t$ while the density of E is close to $2-2t$. This makes the expected value of $E$ be $1/3$ and so the expected total distance is about $N+1/3$. Since for large $N$ the average distance per step is close to $1/2$ and as this is a stopping time, the expected number of steps is about $2N+2/3$.

I justified the previous paragraph with: the joint distribution of the final step $F$ and the excess $E$ tends toward being flat for large $N$ subject to the constraint $0 \le E \lt F \le 1$. We have $\int_{x=0 }^1 \int_{y=0 }^x dy dx = 1/2$ so the joint probability density must be close to $2$ for large $N$. So $\Pr(F\le t) = \int_{x=0 }^t \int_{y=0}^x 2 dy dx = t^2$ and the marginal probability density for $F$ is (close to) $2t$ while $\Pr(E \le t) = \int_{y=0}^t \int_{x=y}^1 2 dx dy = 2t - t^2$ and the marginal probability density for $E$ is (close to) $2 - 2t$.

-
I think the problem is a little bit different:"Suppose you are trying to achieve a score between n+x and n+1. What are your chances of success in the limit as n --> infinity?" In my case I only need to estimate $E[N]$ – ACAC Jan 5 '12 at 0:49
Yes - but when answering, I looked at slightly more than that question. Another recollection is that $E[X_N]\rightarrow \frac{2}{3}$, which is not intuitively obvious. – Henry Jan 5 '12 at 7:16
Searching my memory and the internet, I came across this thread at Usenet:sci.math where I went into the issue rather more deeply – Henry Jan 5 '12 at 7:50