浏览 1764 次
|
锁定老帖子 主题：生日悖论的模拟
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2008-02-03
引用 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 );
}
}
声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
