# Estimating probability that a large sum of i.i.d variables is positive

Let $$X$$ and $$Y$$ be i.i.d. random variables with exponential distribution with mean $$1$$, and let $$Z=(X-1)(Y-X)$$. Let $$Z_1,...,Z_n$$ are i.i.d. copies of $$Z$$, and let $$f(n)=P[\sum_{i=1}^n Z_i > 0]$$. My question is to estimate $$f(n)$$. I am interested in asymptotic upper and lower bounds for large $$n$$, and also in efficient procedure to approximately compute, for example, $$f(100)$$.

The problem with asymptotic estimates is that the standard tool, Cramer's Theorem, is not applicable because the (logarithmic) moment generating function of $$Z$$ is not finite. So, the global question is how to estimate probabilities of large deviations for the sum of i.i.d copies of such $$Z$$.

The problem with computing $$f(100)$$ is that naive simulation (generate $$100$$ copies of $$Z$$ and compute the sum) returns negative sum all the time. The global question here is how to modify the naive experiment to be able to compute very small probabilities.

• I edited the title to be consistent with the post. – Matt F. May 3 at 16:38
• $Z$ has mean $-1$, standard deviation $3$, so $f(100) \sim \Phi(-10/3) \sim .000429$. – Matt F. May 3 at 18:00
• @Bogdan: The estimation given by Matt F. seems to be very crude. The same sort of problems arise in estimating probabilities in risk theory. The technique of "Importance Sampling" (en.wikipedia.org/wiki/Importance_sampling) may be useful in your situation. – Dieter Kadelka May 4 at 8:17
• @Bogdan: I have simulated the problem for myself. The estimation of Matt F. seems to be useless for your problem. For instance with 1000000 runs I got an estimation of the probability $P(Z < -30) = 90/1000000 = 0.00009$, far away from $0.000429$. Confirming your obeservation, even with 1000000 runs there was no success for the original problem. – Dieter Kadelka May 4 at 9:47
• Sorry, the probability is $P(Z > -30) \sim 0.00009$. – Dieter Kadelka May 4 at 13:02

The exact asymptotics of $$f(n)$$ for large $$n$$ follows by Theorem 2.1, more specifically formula (2.4).
However, to use that formula (2.4), you will have to compute lots of asymptotics regarding the distribution of the random variable $$Z$$, and also a few moments of it. Whereas these calculations are straightforward, it's lots of them!
I think the crude, logarithmic asymptotics of $$f(n)$$ for large $$n$$ is given by $$\log f(n)\sim-c\sqrt n$$ for a certain real constant $$c>0$$.
• Thank you! The conditions in Theorem 2.1 are indeed complicated and difficult to verify in my case, but the paper has a reference to another paper (reference [26]) in which Theorem 5 looks like exactly what is needed! The only problem is that $\sigma^2$ in [26, Theorem 5] is undefined, but this already looks like a minor issue. – Bogdan May 7 at 16:27
• @Bogdan : I am glad this was of help. However, I am afraid that the less general result [26, Theorem 5] in the paper by A. V. Nagaev referred to in the paper by his brother S. V. Nagaev will not suffice in your case, because A. V. Nagaev assumes a rather narrow condition on the density -- in his formula (2), which I think the density of your $Z$ will not quite satisfy. A. V. Nagaev does have a footnote statement about this on the first page of his paper, but that statement is not proved and seems too optimistic to me, especially in light of S. V. Nagaev's result. – Iosif Pinelis May 7 at 17:18
• My question was about upper and lower bounds, and, inspired by [26, Theorem 5], I was able to rigorously prove some bounds in my case, which, in particular, imply the crude logarithmic asymptotic $\log f(n) \sim c\sqrt{n}$. This is already sufficient for publication. – Bogdan May 8 at 8:40