Question

5. Random pigeonholing

100 pigeons p1,…,p100 fly into 500 labelled holes h1,…,h500. Each pigeon picks a hole uniformly at random and independently from the choices of the other pigeons.

1. What is the probability that at least one hole contains at least 2 pigeons.
   Hint: The answer is approximately 0.9999758457295991
2. What is the probability that at least one hole contains at least 3 pigeons.
   Hint: The answer is approximately 0.4361298523736379.

Answer 1

probability that at least one hole contains at least 2 pigeons

= 1 - probability that one hole contains maximum 1 pigeon

= 1 - 500P100 /500^100

= 1 - 500!/(100!) / (500^100)

= 1 - (500*499*...401)/(500^100)

=

0.9999758457295990

401	0.802
402	0.804
403	0.806
404	0.808
405	0.81
406	0.812
407	0.814
408	0.816
409	0.818
410	0.82
411	0.822
412	0.824
413	0.826
414	0.828
415	0.83
416	0.832
417	0.834
418	0.836
419	0.838
420	0.84
421	0.842
422	0.844
423	0.846
424	0.848
425	0.85
426	0.852
427	0.854
428	0.856
429	0.858
430	0.86
431	0.862
432	0.864
433	0.866
434	0.868
435	0.87
436	0.872
437	0.874
438	0.876
439	0.878
440	0.88
441	0.882
442	0.884
443	0.886
444	0.888
445	0.89
446	0.892
447	0.894
448	0.896
449	0.898
450	0.9
451	0.902
452	0.904
453	0.906
454	0.908
455	0.91
456	0.912
457	0.914
458	0.916
459	0.918
460	0.92
461	0.922
462	0.924
463	0.926
464	0.928
465	0.93
466	0.932
467	0.934
468	0.936
469	0.938
470	0.94
471	0.942
472	0.944
473	0.946
474	0.948
475	0.95
476	0.952
477	0.954
478	0.956
479	0.958
480	0.96
481	0.962
482	0.964
483	0.966
484	0.968
485	0.97
486	0.972
487	0.974
488	0.976
489	0.978
490	0.98
491	0.982
492	0.984
493	0.986
494	0.988
495	0.99
496	0.992
497	0.994
498	0.996
499	0.998
500	1
product	2.41543E-05
p	0.9999758457295990