7
$\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?

$\endgroup$
5
  • $\begingroup$ You are not going to like my answer but here goes : The problem lies at "...The argument sounded reasonable, but ...". IMO, it is difficult to verify Probability answers since a) You usually have only one way of approaching the answer (If there are multiple, problem solved) b) You can't conduct experiments or go backwards (Like, if I were to find the inverse of a matrix, I can multiply the answer with the original matrix and check that I get the identity matrix). I suggest, strengthen your reasoning (a proof based course like Real Analysis might help). $\endgroup$
    – Inquest
    May 17, 2012 at 13:15
  • 2
    $\begingroup$ I do not know of a general procedure. In combinatorial problems, one can compute carefully some "small" cases, as a check against an error in the "general" analysis. It also helps to have tackled enough problems to have made most of the common errors! $\endgroup$
    – André Nicolas
    May 17, 2012 at 13:17
  • $\begingroup$ It's not clear if you really meant $ (7 / 8) * (6 / 7) * (5 /6 )$ or if you meant to continue the product for 7 terms, but note that in your expression the 7s and 6es cancel from the numerator and denominator, leaving just $\frac58$. If you meant to continue the product down to $…(2/3)(1/2)$ then the cancellation goes even farther and leaves you with just $\frac18$. $\endgroup$
    – MJD
    May 17, 2012 at 14:05
  • $\begingroup$ yea sry i'll edit it. the proposed solution was suggesting 1/n as the final answer $\endgroup$
    – Bonnie Yu
    May 18, 2012 at 3:30
  • $\begingroup$ Related Q&A. $\endgroup$
    – BruceET
    Jun 10, 2021 at 20:07

1 Answer 1

Reset to default
7
$\begingroup$

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$.)

$\endgroup$
12
  • 1
    $\begingroup$ Mark's suggestion is what I was about to suggest. Simulate the experiment and count the outcomes. As the number of simulations gets large yuor result will get close to the correct answer. If you had the wrong answer you would soon see that the simulation is giving a different answer. Many years ago when the Monty Hall problem was first discussed that is exact the way I showed my colleague that switching wins 2/3 of the time and not 1/2. No logical probability argument worked. So you should be happy to know that computers solve the problem in a way mathematics can't. $\endgroup$
    – Michael R. Chernick
    May 17, 2012 at 14:35
  • $\begingroup$ Computer simulations provide only a partial solution. It might be hard to write a program to distinguish between an event that occurs $2119\over5760$ of the time and one that occurs $\frac1e$ of the time. You would have to deploy more sophisticated statistical knowledge to know how many trials to run, and the number would be very large. Your program, even if correct, might fall afoul of biases in the language's built-in random number generator. But simulations work for getting ballpark estimates and for detecting large errors. $\endgroup$
    – MJD
    May 17, 2012 at 14:41
  • $\begingroup$ @MarkDominus, in addition to biases in (pseudo)random number generators, biases can also be inadvertently be introduced by programmers. For example, in Monte Carlo optimization settings, a naive random direction vector formed by independently generated scalar elements (whether uniform, Gaussian, etc) increasingly biases towards the hypercube's diagonals as the dimension increases. Knuth shows how to generate a uniform distribution on a hypersphere. $\endgroup$
    – alancalvitti
    May 17, 2012 at 14:52
  • $\begingroup$ @MichaelChernick, Rosenhouse's Monty Hall Problem has a passage about how Erdos got angry when presented with the optimal strategy, saying he could not understand "why" he had to switch. It's ironic that there's now statistical evidence that pigeons solve MHP by learning from experience. $\endgroup$
    – alancalvitti
    May 17, 2012 at 14:57
  • $\begingroup$ Sure! But that sort of error can occur in mathematical arguments as well, and is a hazard of any method to calculate the probability of an event. So I thought it would be superfluous to mention it. $\endgroup$
    – MJD
    May 17, 2012 at 14:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .