5
$\begingroup$

The Law of large numbers addresses the issue of the average result of a large number of random trials. Is there a similar law which addresses the probability of obtaining an unusual result for a large number of trials?

For instance, consider a normal probability distribution with mean 10 and standard deviation 2. I am testing a computational method which will run only if the result is above 18, that is four standard deviations off the mean and so the likelyhood of ever seeing the if condition met is very low. Therefore, to test the method I must run a very large number of trials. Just as one could expect the average value of the trials to approach 10 as more trials are performed, one could also expect that the probability of receiving the unusual result 18 to increase as more trials are performed. Is there a term for this phenomenon?

$\endgroup$
5
$\begingroup$

You can use geometric distribution to reason about such events after several trials.

Let $p$ be the probability of obtaining 18 or more ($p = P(X > 18)$). Then the amount of trials $k$ until success (that is, until 18+ is generated) is distributed according to the geometric distribution:

$$ k \sim (1-p)^{k-1} p $$

Then you can use quantiles of that distribution to estimate how many trials you need to get this event in, say, 95% of runs. Or, just use the mean of that distribution ($\frac{1}{p}$) as the average number of trials until a rare event.

$\endgroup$
1
  • $\begingroup$ I think that you are right: the geometric distribution does describe this use case and this phenomenon. $\endgroup$ – dotancohen Jan 22 '15 at 12:22
6
$\begingroup$

If you want to learn about some general results (and general phenomena) for probabilities of "extreme" values, or values very far away from the mean, you should look into extreme value theory or large deviations theory.

To get you started, some links here on CV: Extreme value theory for count data

Extreme Value Theory and heavy (long) tailed distributions

Large deviation theory exercise

$\endgroup$
0
6
$\begingroup$

You have a sequence of trials, with probability $p$ per trial of a "success" (that the simulation runs).

a) If you want P(simulation is triggered at least once in $n$ trials) that's a calculation from a binomial distribution, but you can work the probability out from first principles by working out the probability of the complementary event (no successes) and subtracting from 1.

In your case, $p = 3.167\times10^{-5}$, P(0 successes) = $(1-p)^n$, so P(at least 1 success) = $1-(1-p)^n$.

b) If you want the distribution of the number of trials to the first success that's a geometric($p$); it has mean $1/p$.


One useful rule of thumb: The probability that you observe success at least once when $n=1/p$ is $1-(1-p)^{1/p} =1-(1-1/n)^{n} \approx 1-1/e \approx 63.2\%$.

So the expected number of trials to the first success is $1/p \approx 31574$ and the probability of at least one success in that many trials is about 63.2%

If $n$ is some multiple of $\frac{1}{p}$, $n = k\cdot\frac{1}{p}$, say, then it has an approximate probability of $1-\exp(-k)$ of seeing at least one success.

So in 10000 trials you have about $1-\exp(-10000/31574)\approx 27\%$ chance of the simulation starting at least once.

This approximation can also be seen directly by applying the Poisson approximation to the binomial. With $n$ trials with probability of success per trial $p$, P(0 successes) = ${n}\choose{0}$$p^0(1-p)^n = (1-p)^n$, and the Poisson approximation (with $\lambda=np$) is $\exp(-\lambda)\lambda^0/0!=\exp(-np)$.

[This approximation is also related to the one mentioned at the end of the section on related distributions in the Wikipedia page on the geometric distribution (just above "See also"), which deals with the probability that it will take more than $a$ trials to start]

--

On the terminology part of the question -- that the probability of at least one success increases as you add more trials might be called a number of things, but I don't know that it has any particularly widespread names.

$\endgroup$
1
  • $\begingroup$ Thank you. Now that I know about the geometric distribution I see that the phenomenon is implicit in the geometric distribution. $\endgroup$ – dotancohen Jan 22 '15 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.