5/2 Math people: if I have a password generator that doesn't generate
any collsions in 1,000,000 runs, is there a way to estimate a lower
bound on the size of the space with a certain confidence?
\_ yes. Lower bound of 1,000,000.
\_ You expect a collision at about \sqrt{n} trials, if there are
n elements in your space. See birthday paradox. -chialea
\_ What chialea means to say is that, if you trust it to be using
reasonably strong random bits (which aren't, for instance, cyclic
and loop in a cycle of length 1,000,001), there's good reason
to expect the space size to be >=1e12. However, there are
many real-world issues that would make this analysis null and
void, and to actually get statistical confidence intervals
on it, you'd need to assume quite a bit about the world, and
then talk to somebody who knows more statistics than I. -alexf
\- hola i havent done the math but is there a rule of thumb
that says "for n buckets with equal/indep probability, the
number of instaces to have say 50% collsions is some f(n)"?
withthe birthday problem it's 365 with close enough to
equal probability to hit 50% collision chance at 24 or 28
[i forgot the number] ... i am wondering about a rule of
thumb like the "rule of 70" on interest rate doubling, or
say even stirling formula for n! --psb
\_ I found a web page that said it's about 1.2*sqrt(n).
Using Stirling's formula and a Taylor series for ln,
I get that the constant in front is sqrt(2*ln(2))
which is about 1.1774. Details left to the reader -lewis
\_ URLp
\_ constants are for sissies
\_ Thanks alex, that's indeed what I meant. I blame it all on
e190! -chialea |
http://csua.com/feed/