[Phys-L] scaling law for birthday puzzle

[John Denker <jsd@av8n.com>]

Scaling laws have been central to physics since Day One (1638) 
and remain tremendously important.  They tend to get little 
coverage in typical courses nowadays, which seems crazy, since
they are easier to learn, easier to teach, more powerful, and
more age-appropriate than a lot of the stuff that is covered.

It pays to always be on the lookout for scaling relationships.
  http://www.av8n.com/physics/scaling.htm

I mention this because on 06/03/2014 06:17 PM, I wrote:

>  You can plot the probability of having at least one
> collision as a function of N (the number of pigeons) and 
> H (the number of holes).  It goes from p=0 at N=1 up to 
> p=1 at N=1+H.  The distribution is Boolean at the ends of
> the range, but probabilistic in the interior.

I should have pointed out that there is a nice scaling law
here.  For any given probability of collision, the number of 
items you can have (N) scales like the square root of the 
number of slots (H).

In more detail, to a good approximation:
    P_collision(N,H) ≈ N(N−1)/2H
                     ≈ N^2/2H

That is to say, you can plot the whole probability-of-collision
curve, for (almost) all N and H, as a function of the single 
variable N(N−1)/2H.  This is an example of universality.

This is somewhat more esoteric than the simple scaling laws we 
use to introduce the subject, such as surface-to-volume ratios,
but it has plenty of real-world applications, including computer
science (e.g. compiler design) and cryptography.  The idea that
the number of items scales like the square root of the number
of slots is definitely a nontrivial result.  Non-experts tend to
guess that N should scale in proportion to H.  That's what simple
notions of dimensional analysis would suggest, but it's nowhere
near correct.

For details, see
  http://www.av8n.com/physics/scaling.htm#main-birthday