生日悖论的模拟

引用

Programming: The Birthday Paradox

There's a parlor trick known as the Birthday Paradox where in any group of 23 or more people, chances are more than 50% that some two people have the same birthday. This is counter-intuitive to statistical lay people, but can be proven mathematically. Still, certain lay people have been known to be suspicious of math (but rather trusting of computers), so one thing we can do is gather empirical evidence -- simulate gatherings of people with randomly-assigned birthdays and test how often two people end up with the same birthday. We'd also like to vary the problem a bit to see what effect differently-sized calendars and group sizes have on the result.

Your simulation should work like this:
1. Take from the user two numbers: D, a calendar length (in days), and N, a number of trials.
2. Picks random birthdays for G=2 guests.
3. Test to see if any of the 2 guests share a birthday with another of the 2 guests. If so, the program remembers a "hit."
4. Repeat steps 2 and 3 until the requested number of trials is met.
5. Report the percentage of trials that reported hits, that is, the proportion of simulated parties where the some two guests shared a birthday.
6. Repeat steps 2, 3, 4, and 5 for parties of 3, 4, 5 ... 100 guests.
Test your program on a few calendar lengths, as small as 2 days and as large as 1000 days. If your program works correctly, you should find that the percentage of hits exceeds .5 for N=365 when G=23.

Your program should take the two variables, D and T, on the command line. Be sure to check that they are valid (both should be integers of at least 2).

In your README, answer the following questions (in addition to the usual README content):
1. How did you implement your program? What loops did you use, where, for what purpose? What data structures did you use to store your information?
2. What were your results for D=2, 10, 100, 500, and 1000? Did they match up with your expectations?
3. What happens to your results when you vary the number of trials? How many trials are "enough" for results to converge?
4. Based on your answer to #1, how long does your program take? Give Big-Oh, Omega-Oh, and, if applicable, Theta-Oh terms as a function of D, G and T.

Example Output

$ java BirthdaySim 200 1000
2 guests: [0.0050]: 5 time(s) out of 1000, two guests had the same birthday
3 guests: [0.017]: 17 time(s) out of 1000, two guests had the same birthday
4 guests: [0.024]: 24 time(s) out of 1000, two guests had the same birthday
5 guests: [0.057]: 57 time(s) out of 1000, two guests had the same birthday
6 guests: [0.06]: 60 time(s) out of 1000, two guests had the same birthday
7 guests: [0.09]: 90 time(s) out of 1000, two guests had the same birthday
8 guests: [0.134]: 134 time(s) out of 1000, two guests had the same birthday
9 guests: [0.158]: 158 time(s) out of 1000, two guests had the same birthday
10 guests: [0.213]: 213 time(s) out of 1000, two guests had the same birthday
11 guests: [0.227]: 227 time(s) out of 1000, two guests had the same birthday
12 guests: [0.291]: 291 time(s) out of 1000, two guests had the same birthday
13 guests: [0.322]: 322 time(s) out of 1000, two guests had the same birthday
14 guests: [0.352]: 352 time(s) out of 1000, two guests had the same birthday
15 guests: [0.415]: 415 time(s) out of 1000, two guests had the same birthday
16 guests: [0.454]: 454 time(s) out of 1000, two guests had the same birthday
17 guests: [0.487]: 487 time(s) out of 1000, two guests had the same birthday
18 guests: [0.532]: 532 time(s) out of 1000, two guests had the same birthday
19 guests: [0.595]: 595 time(s) out of 1000, two guests had the same birthday
20 guests: [0.609]: 609 time(s) out of 1000, two guests had the same birthday
21 guests: [0.62]: 620 time(s) out of 1000, two guests had the same birthday
22 guests: [0.664]: 664 time(s) out of 1000, two guests had the same birthday
23 guests: [0.73]: 730 time(s) out of 1000, two guests had the same birthday
24 guests: [0.775]: 775 time(s) out of 1000, two guests had the same birthday
25 guests: [0.807]: 807 time(s) out of 1000, two guests had the same birthday
26 guests: [0.831]: 831 time(s) out of 1000, two guests had the same birthday
27 guests: [0.857]: 857 time(s) out of 1000, two guests had the same birthday
28 guests: [0.855]: 855 time(s) out of 1000, two guests had the same birthday
29 guests: [0.875]: 875 time(s) out of 1000, two guests had the same birthday
30 guests: [0.893]: 893 time(s) out of 1000, two guests had the same birthday
31 guests: [0.927]: 927 time(s) out of 1000, two guests had the same birthday
32 guests: [0.93]: 930 time(s) out of 1000, two guests had the same birthday
33 guests: [0.943]: 943 time(s) out of 1000, two guests had the same birthday
34 guests: [0.963]: 963 time(s) out of 1000, two guests had the same birthday
35 guests: [0.942]: 942 time(s) out of 1000, two guests had the same birthday
36 guests: [0.962]: 962 time(s) out of 1000, two guests had the same birthday
37 guests: [0.972]: 972 time(s) out of 1000, two guests had the same birthday
38 guests: [0.978]: 978 time(s) out of 1000, two guests had the same birthday
39 guests: [0.979]: 979 time(s) out of 1000, two guests had the same birthday
40 guests: [0.982]: 982 time(s) out of 1000, two guests had the same birthday
41 guests: [0.986]: 986 time(s) out of 1000, two guests had the same birthday
42 guests: [0.988]: 988 time(s) out of 1000, two guests had the same birthday
43 guests: [0.996]: 996 time(s) out of 1000, two guests had the same birthday
44 guests: [0.997]: 997 time(s) out of 1000, two guests had the same birthday
45 guests: [0.999]: 999 time(s) out of 1000, two guests had the same birthday
46 guests: [0.995]: 995 time(s) out of 1000, two guests had the same birthday
47 guests: [0.998]: 998 time(s) out of 1000, two guests had the same birthday
48 guests: [0.997]: 997 time(s) out of 1000, two guests had the same birthday
49 guests: [0.998]: 998 time(s) out of 1000, two guests had the same birthday
50 guests: [0.999]: 999 time(s) out of 1000, two guests had the same birthday
51 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
52 guests: [0.998]: 998 time(s) out of 1000, two guests had the same birthday
53 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
54 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
55 guests: [0.999]: 999 time(s) out of 1000, two guests had the same birthday
56 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
57 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
58 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
59 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
60 guests: [0.999]: 999 time(s) out of 1000, two guests had the same birthday
61 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
62 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
63 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
64 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
65 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
66 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
67 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
68 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
69 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
70 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
71 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
72 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
73 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
74 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
75 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
76 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
77 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
78 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
79 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
80 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
81 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
82 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
83 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
84 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
85 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
86 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
87 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
88 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
89 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
90 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
91 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
92 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
93 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
94 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
95 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
96 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
97 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
98 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
99 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday
100 guests: [1.0]: 1000 time(s) out of 1000, two guests had the same birthday

BirthdaySim.java:

/*
 * BirthdaySim.java
 * ver 0.0.0.1, Jan 30, 2008
 */

public class BirthdaySim {

    ///////////////////////////////////////////////////////////////////////////
    // Static fields
    ///////////////////////////////////////////////////////////////////////////

    private static int          D;

    private static int          T;

    ///////////////////////////////////////////////////////////////////////////
    // Constants
    ///////////////////////////////////////////////////////////////////////////

    private static final int    MIN_GUESTS  = 2;
    private static final int    MAX_GUESTS  = 100;
    private static final String USAGE       =
        "Usage: java BirthdaySim daysOfCalendar numberOfTrials";

    ///////////////////////////////////////////////////////////////////////////
    // Program entry point
    ///////////////////////////////////////////////////////////////////////////

    /**
     * @param args Command line parameters.
     * Usage: java BirthdaySim daysOfCalendar numberOfTrials
     */
    public static void main( String[ ] args ) {
        try {
            processCommandLine( args );
            runTrials( D, T );
        } catch ( NumberFormatException nfe ) {
            System.err.println( "Invalid number format: " + nfe.getMessage( ) );
            usage( );
        } catch ( Exception e ) {
            System.err.println( e.getMessage( ) );
            usage( );
        }
    }

    ///////////////////////////////////////////////////////////////////////////
    // Helper methods
    ///////////////////////////////////////////////////////////////////////////

    private static void processCommandLine( String[ ] args ) throws Exception {
        if ( args.length > 2 )
            throw new Exception( "Too many arguments." );
        if ( args.length < 2 )
            throw new Exception( "Too little arguments." );

        D = Integer.parseInt( args[ 0 ] );
        T = Integer.parseInt( args[ 1 ] );
    }

    private static void usage() {
        System.out.println( USAGE );
    }

    static void runTrials( int d, int t ) {
        for ( int i = MIN_GUESTS; i <= MAX_GUESTS; ++i ) {
            Simulator sim = new Simulator( d, t, i );
            System.out.println( sim );
        }
    }
}

Simulator.java:

/*
 * Simulator.java
 * ver 0.0.0.1, Jan 30, 2008
 */

import java.util.Arrays;
import java.util.Random;

/**
 * Implementation of birthday problem.
 */
public class Simulator {

    //////////////////////////////////////////////////////////////////////////
    // Private fields
    ///////////////////////////////////////////////////////////////////////////

    private int[ ]  guest;
    private int     daysOfCalendar;
    private int     numberOfTrials;
    private int     hitCount;
    private boolean isCalculated;

    ///////////////////////////////////////////////////////////////////////////
    // Constructors
    ///////////////////////////////////////////////////////////////////////////

    public Simulator( int daysOfCalendar, int numberOfTrials, int numberOfGuests ) {
        this.guest = new int[ numberOfGuests ];
        this.daysOfCalendar = daysOfCalendar;
        this.numberOfTrials = numberOfTrials;
        this.setCalculated( false );
    }

    ///////////////////////////////////////////////////////////////////////////
    // Methods
    ///////////////////////////////////////////////////////////////////////////

    protected void initialize( ) {
        Random random = new Random( );

        // initialize guest array
        // Theta(n), where n = this.guest.length (?)
        for ( int i = 0; i < this.guest.length; ++i ) {
            this.guest[ i ] = random.nextInt( this.getDaysOfCalendar( ) );
        }
        
        // sort guest array with Java's tuned quicksort
        // implementation in standard library.
        // this is an O(n^2) and Omega(n*log(n)) algorithm,
        // where n = this.guest.length
        Arrays.sort( this.guest );
    }

    public void runTrials( ) {
        this.hitCount = 0;

        // run trials for T times
        for ( int i = 0; i < this.getNumberOfTrials( ); ++i ) {
            this.initialize( );
            this.hitCount = ( this.isHit( ) ) ? this.hitCount + 1 : this.hitCount;
        }

        this.setCalculated( true );
    }
    
    private boolean isHit( ) {
        int lastNumber = this.guest[ 0 ];
        
        // do a linear search for duplicate occurences
        // Theta(n), where n = this.guest.length (?)
        for ( int i = 1; i < this.guest.length; ++i ) {
            if ( lastNumber == this.guest[ i ] ) {
                return true;
            } else {
                lastNumber = this.guest[ i ];
            }
        }
        
        return false;
    }

    ///////////////////////////////////////////////////////////////////////////
    // Overridden methods
    ///////////////////////////////////////////////////////////////////////////

    @Override
    public String toString( ) {
        if ( !this.isCalculated( ) ) {
            this.runTrials( );
        }

        StringBuilder sb = new StringBuilder( );
        sb.append( this.getNumberOfGuests( ) );
        sb.append( " guests: [" );
        sb.append( this.getProbability( ) );
        sb.append( "]: " );
        sb.append( this.getHitCount( ) );
        sb.append( " time(s) out of " );
        sb.append( this.getNumberOfTrials( ) );
        sb.append( ", two guests had the same birthday" );

        return sb.toString( );
    }

    ///////////////////////////////////////////////////////////////////////////
    // Getter/Setter methods
    ///////////////////////////////////////////////////////////////////////////

    public int getNumberOfGuests( ) {
        return this.guest.length;
    }

    public void setNumberOfGuests( int numberOfGuests ) {
        this.guest = new int[ numberOfGuests ];
        this.setCalculated( false );
    }

    public int getDaysOfCalendar( ) {
        return this.daysOfCalendar;
    }

    public void setDaysOfCalendar( int daysOfCalendar ) {
        this.daysOfCalendar = daysOfCalendar;
        this.setCalculated( false );
    }

    public int getNumberOfTrials( ) {
        return this.numberOfTrials;
    }

    public void setNumberOfTrials( int numberOfTrials ) {
        this.numberOfTrials = numberOfTrials;
        this.setCalculated( false );
    }

    public int getHitCount( ) {
        return hitCount;
    }

    public double getProbability( ) {
        if ( !this.isCalculated( ) ) {
            this.runTrials( );
        }

        return this.hitCount / ( double ) this.numberOfTrials;
    }

    private boolean isCalculated( ) {
        return this.isCalculated;
    }

    private void setCalculated( boolean isCalculated ) {
        this.isCalculated = isCalculated;
        if ( !this.isCalculated ) {
            this.hitCount = -1;
        }
    }
    
    ///////////////////////////////////////////////////////////////////////////
    // main, for testing purpose only
    ///////////////////////////////////////////////////////////////////////////
    
    public static void main( String[ ] args ) {
        Simulator sim = new Simulator( 200, 1000, 23 );
        System.out.println( sim );
    }
}