Chronology Current Month Current Thread Current Date [Year List] [Month List (current year)] [Date Index] [Thread Index] [Thread Prev] [Thread Next] [Date Prev] [Date Next]

# [Phys-L] scaling law for birthday puzzle

• From: John Denker <jsd@av8n.com>
• Date: Fri, 06 Jun 2014 13:25:45 -0700

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