Re: [Phys-L] pigeon holes

[John Denker <jsd@av8n.com>]

On 06/03/2014 02:17 PM, Bernard Cleyet wrote:
> > > Not really related, but this one always reminds me of the birthday paradox,
> > > that it takes only 23 people randomly selected to have greater than 50%
> > > chance that two or more will share a common birthday.
>
> You certain?  I think related as both probabilities.   

Well..... They are both "probabilities" only in the trivial
wise-guy sense that cut-and-dried Booleans can be encoded as 
probabilities.  A discrete probability distribution encodes 
Booleans using a Kronecker delta, while a continuous probability 
distribution encodes Booleans using a Dirac delta.

Back in the non-wise-guy world, the classic use of a pigeon
hole argument says that if you put N+1 pigeons into N holes,
there is absolutely /guaranteed/ to be a collision.

The birthday construction says that you will /probably/ 
see a collision long before you get to N+1 pigeons.  Not 
guaranteed, but probably.

These two things are related in the following nontrivial
way:  You can plot the probability of having at least one
collision as a function of M (the number of pigeons) and 
N (the number of holes).  It goes from p=0 at M=1 up to 
p=1 at M=1+N.  The distribution is Boolean at the ends of
the range, but probabilistic in the interior.