Re: Lockless file readingu

[William Lee Irwin III]

On Fri, Aug 29, 2003 at 06:00:11AM -0400, jlnance@xxxxxxxxxxxxxx wrote:
> Be careful.  I remember discussing in probability class the liklyhood that
> two people in a room with N people have the same birthday.  N does not have
> to be anywhere close to 365 for your probability of a collision to be greater
> than 50%.  I forget what the exact number is but its less than 30.  The
> image problem sounds similar, depending on exactly how you phrase it.

This is very simple to see. Consider the probability of not having a
collision instead of having a collision. Each choice eliminates a
choice, so the probability of not colliding while taking a sample after
taking N samples from a uniform distribution over K values is (K-N)/K.
You end up getting 1 - K!/((K-N)! * K**N).

Given one possible value for each day of the year, K == 365.

So you want 1 - 365!/((365 - N)! * 365**N) > 1/2.

The first few probabilities of collision (calculated afresh) are:

0  0.0
1  0.0
2  2.739726027397249e-3
3  8.204165884781345e-3
4  1.6355912466550326e-2
5  2.713557369979358e-2
6  4.0462483649111536e-2
7  5.6235703095975365e-2
8  7.433529235166902e-2
9  9.462383388916673e-2
10 0.11694817771107757
11 0.14114137832173312
12 0.16702478883806438
13 0.19441027523242949
14 0.223102512004973
15 0.25290131976368646
16 0.2836040052528499
17 0.31500766529656066
18 0.34691141787178936
19 0.37911852603153673
20 0.41143838358058005
21 0.4436883351652058
22 0.4756953076625501
23 0.5072972343239854
24 0.5383442579145288
25 0.5686997039694639
26 0.598240820135939
27 0.626859282263242
28 0.6544614723423994
29 0.680968537477777
30 0.7063162427192686
31 0.7304546337286438
32 0.7533475278503207
33 0.774971854175772
34 0.7953168646201543
35 0.8143832388747152
36 0.8321821063798795
37 0.8487340082163846
38 0.8640678210821209
39 0.878219664366722
40 0.891231809817949
41 0.9031516114817354
42 0.9140304715618692
43 0.9239228556561199
44 0.9328853685514263
45 0.940975899465775
46 0.9482528433672547
47 0.9547744028332994
48 0.9605979728794224
49 0.9657796093226765
50 0.9703735795779884

N = 23 should do fine for your purposes.


-- wli
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/