6
$\begingroup$

In CS, there's a systematic way to check if your code is buggy or not as you write code. Is there a way to check the correctness of your answer to a probability question without using a textbook?

For example, my friend proposed a solution to a probability question that seemed right.

Question: Suppose that each of N men at a party throws his hat into the center of the room. The hats are first mixed up, and then each man randomly selects a hat. What is the probability that none of the men selects his own hat?

Proposed Solution: if we suppose there are 8 men, then the suggestionw as (7 / 8) * (6 / 7) * (5 /6 )... * (1/2) * 1

which for the n case simplifies to 1/n

The argument sounded reasonable, but the answer was wrong which I found out from the textbook. I had to think about it a bit before I realized he had undercounted. Is there a more systematic way to check answers for probability questions?

  • 0
    yea sry i'll edit it. the proposed solution was suggesting 1/n as the final answer2012-05-18

1 Answers 1

6

One thing that is sometimes helpful is to write a computer program to run a lot of random trials and see if the number produced by the computer is way off the number you expect. For example:

 # This is a Perl program  my $hats = shift || 8; my $trials = shift || 10000;  my $derangements = 0; TRIAL: for (1..$trials) {   my @perm = ("dummy", permute(1..$hats));   for $hat (1..$hats) {     if ($perm[$hat] == $hat) { next TRIAL }   }   $derangements++; }  print "In $trials trials, there were $derangements cases in which nobody got their own hat.\n"; printf "That's %5.2f%%.\n", $derangements * 100 / $trials;  sub permute {   my @items = @_;   # Fischer-Yates algorithm   for my $n (reverse 0 .. $#items) {     my $m = int rand($n + 1);     @items[$n,$m] = @items[$m,$n] if $m != n;   }   return @items; } 

This prints:

 In 10000 trials, there were 3683 cases in which nobody got their own hat. That's 36.83%. 

This is far enough from your suggested value of \frac78\frac67\ldots\frac12 = \frac18 = 12.5\% that we can be sure that that is wrong or that the program has a severe error.

(In fact, 36.83% is close to the theoretically correct value, which happens to be 2119\over 5760$.)

  • 0
    On rereading this, I wish I had mentioned that the hardest part of the program to write is the `permute` function. The Fischer-Yates algorithm is simple, and simple to implement, if you know how, but if not, it's easy to make a mistake and get a severly biased permutation generator.2013-11-29