随机算法关于生日悖论的求值

2019-02-26

probabilistic

In probability theory, the birthday problem, or birthday paradox This not a paradox in the sense of leading to a logical contradiction, but is called a paradox because the mathematical truth contradicts naive intuition: most people estimate that the chance is much lower than 50%. pertains to the probalility that in a set of randomly chosen people some pair of them will have the same birthday. In a group of at least 23 randomly chosen people, there is more than 50% probalility that some pair of them will both have been born on the same day. For 57 or more people, the probability is more than 99%, and it reachese 100% when the number of people reaches 366 (by the pigeon hole principle, ignoring leap yeas). The mathematics behind this problem lead to a well-known cryptographic attack call the birthday attack.

Using simulation, estimate the number of independent people required in a groups before we can expect a better than even chance that at least 2 independent people in a group share a common birthday. Furthermore: Simulate and thus estimate when we can expect a better than even chance that at least 3, 4 & 5 independent people of the group share a common birthday. For simplicity assume that all of the people are alive…

Calculating the probalility

数学概率推导方法，

1
2
3
4
5
6
7
8
9
fn probe(n: i32) {
    let mut probe: f64 = 0.;
    let mut k = 0;
    while k < n {
        k += 1;
        probe = 1.0 - ((1.0 - probe) * ((365 - (k - 1)) as f64) / (365 as f64));
        println!("Number of people: {}, \tProb. of same birthday: {}", k, probe);
    }
}

Birthday Attack

生日悖论可以描述为：在N个人中，想使至少由两个人生日相同的概率大于50%，问N的最小值是多少？答案是23人。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
use rand::prelude::*;

const DAYS_IN_YEAR: usize = 365;

fn equal_birthdays(n_sharers: usize, group_size: usize, n_repetitions: usize) -> f64 {
    let mut rng = rand::thread_rng();
    let mut eq = 0;
    for _ in 0..n_repetitions {
        let mut group = vec![0; DAYS_IN_YEAR];
        for _ in 0..group_size {
            let idx = rng.gen_range(0, group.len());
            group[idx] = group[idx] + 1;
        }
        for k in group.iter() {
            if *k >= n_sharers {
                eq = eq + 1;
            }
        }
    }
    (eq as f64 * 100.0) / n_repetitions as f64
}


fn main() {
    let mut group_est = 2;
    for sharers in 2..6 {
        // Coarse.
        let mut group_size = group_est + 1;
        while equal_birthdays(sharers, group_size, 100) < 50.0 {
            group_size = group_size + 1;
        }
        // Finer.
        let inf = ((group_size - (group_size - group_est)) as f64 / 4.0) as usize;
        for gs in inf..(group_size + 999) {
            let eq = equal_birthdays(sharers, group_size, 250);
            if eq > 50.0 {
                group_size = gs;
                break;
            }
        }
        for gs in (group_size - 1)..(group_size + 999) {
            let eq = equal_birthdays(sharers, gs, 50_000);
            if eq > 50.0 {
                group_est = gs;
                println!("{} independent people in a group of {} share a common birthday. {}", sharers, gs, eq);
                break;
            }
        }
    }
}