Birthday Paradox in q

The Birthday Paradox can be illustrated in q as follows (bp_q):

/ Birthday Paradox in q
/ by <thesweeheng@gmail.com>

p:{[d;n]1-prd(d-til n)%d}                              / collision probability
s:{[d;n]avg{y>count distinct y?x}[d]each 100000#n}     / collision simulation
t:{[d;ns]flip`n`sim_p`p!({x};s[d]each;p[d]each)@\:ns}

\c 34 80
show select n,sim_p,p,diff:abs sim_p-p from t[365;2+til 30]

The output for one particular run is:

n  sim_p   p           diff
-----------------------------------
2  0.00279 0.002739726 5.027397e-05
3  0.0084  0.008204166 0.0001958341
4  0.01586 0.01635591  0.0004959125
5  0.0269  0.02713557  0.0002355737
6  0.04053 0.04046248  6.751635e-05
7  0.05718 0.0562357   0.0009442969
8  0.07439 0.07433529  5.470765e-05
9  0.09488 0.09462383  0.0002561661
10 0.11555 0.1169482   0.001398178
11 0.14079 0.1411414   0.0003513783
12 0.16684 0.1670248   0.0001847888
13 0.19379 0.1944103   0.0006202752
14 0.22458 0.2231025   0.001477488
15 0.25089 0.2529013   0.00201132
16 0.28645 0.283604    0.002845995
17 0.31553 0.3150077   0.0005223347
18 0.34367 0.3469114   0.003241418
19 0.37767 0.3791185   0.001448526
20 0.41336 0.4114384   0.001921616
21 0.44386 0.4436883   0.0001716648
22 0.47655 0.4756953   0.0008546923
23 0.50813 0.5072972   0.0008327657
24 0.53765 0.5383443   0.0006942579
25 0.56733 0.5686997   0.001369704
26 0.59646 0.5982408   0.00178082
27 0.62797 0.6268593   0.001110718
28 0.65472 0.6544615   0.0002585277
29 0.67958 0.6809685   0.001388537
30 0.70505 0.7063162   0.001266243
31 0.73318 0.7304546   0.002725366

The n column indicates the number of persons; the sim_p column contains the probability computed from running 100,000 simulations; the p column contains the theoretical probability and the diff column indicates the absolute difference between sim_p and p.

Advertisements
Posted in k&q. Tags: . Leave a Comment »

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: