My daughter was learning about prime numbers and she had an exercise to identify all the prime numbers less than 100.  I made a little game out of it with her by offering her 10 cents for each number correctly categorized as prime or composite within a fixed total time.

As she progressed through the numbers I noticed a pattern.  It took her less time to guess that a number was composite than it took her to guess that it was prime. And of course there is a simple reason:  you know that a number is composite once you find a proper factor, you know that a number is prime only when you are convinced that a proper factor does not exist.

But this was a timed-constrained task and waiting until she knows for sure that the number is prime is not an optimal strategy.  She should guess that the number is prime once she thinks it is sufficiently likely that she won’t find any proper factor. And how long that will take depends on the average time it takes to find a proper factor.

In particular, if the average time before she guesses prime is larger than the average time before she guesses composite then she is not optimizing.  Because if that were the case she should infer that the number is likely to be prime simply from the fact that she has spent more than the average time looking for a proper factor.  At an optimum, any such introspective inference should be arbitraged away.

About these ads