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.

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]$?

share|improve this question
    
"assuming I'm not under the conditions of using martingale" -- Can you clarify what this means? –  Srivatsan Jan 4 '12 at 22:51
1  
@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
1  
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
1  
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
add comment

1 Answer

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

share|improve this answer
    
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
add comment

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.