5 ms·
An easier almost-proof of the N trials with 1/N chance bit uses the approximation log(1+x)~=x for small x. See: let's find what is Q such that Prob(no success
by thanatropism 7y ago
An easier almost-proof of the N trials with 1/N chance bit uses the approximation log(1+x)~=x for small x.
See: let's find what is Q such that Prob(no successes in M trials)~=Q. This is:
(1-(1/N)^M ~= Q
therefore
M log(1-1/N) ~= loq Q
Using the approximation,
-M/N ~= log Q
that is
exp(-M/N) ~= Q
M=N yields the result.
Now, if we slightly change the problem so Q is a probability threshold such that Prob(no successes in M trials)>Q, we get an exact statement: since x>log(1+x) exactly, -M/N > log(1-1/N) > log Q.