Provoking A Math Jax Bug

   
Recent changes
Table of contents
Links to this page
FRONT PAGE / INDEX

At least, trying to provoke a Math Jax bug. Not sure what actually causes it to happen, so I'll have to play about and see what happens.

This is relevant when we talk about avoiding hash collisions in computing systems, so it makes sense to talk about huge numbers of possible "birthdays" and huge numbers of "people." We can ask, when we have a huge hash space, how many keys can we choose before there's a 1% chance of a collision? (for some value of 1%).

In case you don't know about hashes and hash spaces, a "hash function" is a way of taking a sort of "fingerprint" of an object. The result is the hash of the object, and a hash is usually designed to be a random-looking collection of bits. Hashes used to be of size 32 or 64 bits, because that fitted nicely into computer storage units, but these days hashes tend to be much larger.

Hashes usually have the property that changing the object ever so slightly changes the hash pretty much apparently at random. Cryptographic hashes also have the property that it's really, really hard to deduce anything about the original object, even if you know exactly how the hash is computing.

So what happens as we deal with larger numbers, and with different probabilities? So let's see how we get to the answer of 23 people given 365 possible birthdays, and then generalise from there.

$$\left(\frac{365-1}{365}\right)\times\left(\frac{365-2}{365}\right)\times\ldots\times\left(\frac{365-9}{365}\right)$$

To do the analysis we turn this around and ask - what is the probability that we have no collisions? For just one person the answer is 1 - there is no chance of sharing a birthday, so there is a 100% chance of no shared birthday.

With two people, the second person must avoid the birthday of the first person. Assuming 365 days in the year this is then 364/365, being the number of days allowed, divided by the number of days from which we must choose.

Now add another person. To avoid a coincidence we must, in addition to the first coincidence dodged, now avoid two existing days. That has a chance of (365-2)/365. And so on, and these accumulate. So the chance of 10 people avoiding each other's birthdays is:


We see something like this: $\left(1-\frac{k}{N}\right)^{-N}$


That's a snip from another page that may or may not have had the problem, so I'm starting with that.


Contents

There were no headings
in the main text so there
is no table of contents.
 

Links on this page

 
Site hosted by Colin and Rachel Wright:
  • Maths, Design, Juggling, Computing,
  • Embroidery, Proof-reading,
  • and other clever stuff.

Suggest a change ( <-- What does this mean?) / Send me email
Front Page / All pages by date / Site overview / Top of page

Universally Browser Friendly     Quotation from
Tim Berners-Lee
    Valid HTML 3.2!