B.9 Examples for Chapter 12 – Introduction to Cryptography with Coding Theory, 3rd Edition

B.9 Examples for Chapter 12

Example 36

Suppose there are 23 people in a room. What is the probability that at least two have the same birthday?

SOLUTION

The probability that no two have the same birthday is i=122(1i/365) (note that the product stops at i=22,  not i=23). Subtracting from 1 gives the probability that at least two have the same birthday:

> 1-mul(1.-i/365, i=1..22)

                                .5072972344

Note that we used 1. in the product instead of 1 without the decimal point. If we had omitted the decimal point, the product would have been evaluated as a rational number (try it, you’ll see).

Example 37

Suppose a lazy phone company employee assigns telephone numbers by choosing random seven-digit numbers. In a town with 10,000 phones, what is the probability that two people receive the same number?

> 1-mul(1.-i/10aˆ7, i=1..9999)
                                .9932699133

Note that the number of phones is about three times the square root of the number of possibilities. This means that we expect the probability to be high, which it is. From Section 12.1, we have the estimate that if there are around 2(ln2)1073723 phones, there should be a 50% chance of a match. Let’s see how accurate this is:

> 1-mul(1.-i/10aˆ7, i=1..3722)

                                 .4998945441