2
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ I edited the title to be consistent with the post. $\endgroup$
    – user44143
    Commented May 3, 2019 at 16:38
  • 3
    $\begingroup$ $Z$ has mean $-1$, standard deviation $3$, so $f(100) \sim \Phi(-10/3) \sim .000429$. $\endgroup$
    – user44143
    Commented May 3, 2019 at 18:00
  • 1
    $\begingroup$ @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. $\endgroup$
    – Dieter Kadelka
    Commented May 4, 2019 at 8:17
  • 1
    $\begingroup$ @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. $\endgroup$
    – Dieter Kadelka
    Commented May 4, 2019 at 9:47
  • 1
    $\begingroup$ Sorry, the probability is $P(Z > -30) \sim 0.00009$. $\endgroup$
    – Dieter Kadelka
    Commented May 4, 2019 at 13:02

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Bogdan
    Commented May 7, 2019 at 16:27
  • $\begingroup$ @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. $\endgroup$
    – Iosif Pinelis
    Commented May 7, 2019 at 17:18
  • $\begingroup$ Previous comment continued: So, I think the best (if not the only) way to proceed here is indeed to go through lots of pretty hard calculations required by the mentioned result by S. V. Nagaev. $\endgroup$
    – Iosif Pinelis
    Commented May 7, 2019 at 17:20
  • $\begingroup$ 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. $\endgroup$
    – Bogdan
    Commented May 8, 2019 at 8:40
  • $\begingroup$ Of course, it would be even nicer to have the EXACT asymptotic, but, unless I am mistaken, some of the conditions before Theorem 2.1 not only difficult to verify - they just does not hold. It looks like Theorem 2.1 corresponds to one of the "main cases" in [26], while my case is exactly the "intermediate" one covered only by [26, Theorem 5]. $\endgroup$
    – Bogdan
    Commented May 8, 2019 at 8:49

You must log in to answer this question.

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