Reference no: EM132211234

Question :

Write a program in Python 3 to generate a table giving information related to the birthday problem. Assume that the number of days is 366, but let it be a variable so that you could use the program on other planets, for checking resistance to birthday attacks, or if I have already won several bets so that on the next bet we could reduce the number of days. Similarly, leave the maximum number of students (in this case 70) as a variable.

I will describe each column of the table separately. You might want to write your program so that it runs for one column before adding another column. In addition to the following, attach a printout of your program.

(a) The first column should give the number of people in the room (in- cluding me) and should go from 1 to 70. Have an appropriate header for the column.

(b) The second column should give the probability of me losing the bet (that is, all k people have different birthdays). So if there is only one person, all birthdays would be different with probability one. If there were two, all would be different with probability probability 365/366. If there were three, all would be different with probability 365(364)/3662 . This should also suggest a way to recursively, compute these prob- abilities.

Let P(k) be the probability that k people have different birthdays assuming n = 1 days, all days are equally likely, and one person's birthday does not influence the birthday of others. (Later, we will call this independence.) For this program, n = 366. Check the following formula to see if the following statements are correct, but I think we know that P (0) = 1.0 and P (k) = P (k - 1) * (n - k + 1)/n for k = 1. Please do the computations in floating point.

(c) Explain the logic behind the equation P(k) = P(k-1)*(n-k+1)/n, or the corrected equation if that equation is wrong.

(d) How big should the class be before I should start making the birthday bet? and what is the probability of me winning?

(e) We computed the probability based on a model. Is the actual proba- bility of me winning bigger or smaller than what we computed from our model? Explain.

(f) If there are 65 students in class, what is the probability of me winning. (If it's really close to one, it's probably better to express it as 1- something really small.

On page 116 of our text, Professor Hajek writes "When we deal with probabilities that are close to one it is usually more convenient to represent them as one minus something, for example writing 18.5106 instead of 0.9999915. When we deal with probabilities that are close to one it is usually more convenient to represent them as one minus something, for example writing 18.5106 instead of 0.9999915." Also, if you double check your answers by comparing with results on-line, you might need to change 366 to 365.).

(g) Are you more likely to win the jackpot in the lottery with one ticket or win the birthday bet against me assuming there are 70 of us in the room?

(h) (Optional) Add another column where you also compute the proba- bility of me losing, but compute it in a different way. In the recursive equation for P(k) keep track of the numerator and the denominator separately where both the numerator and the denominator are in- tegers. Thus, you have the exact value of P(k) as a fraction.

Now convert the fraction to a floating point number, and print it. (I gather that Python 3 automatically does converts integers to floating point when doing division so 1/3 will be something like .333, but Python 2 would say 1/3 is 0.) So the only error introduced should be the con- version from the fraction to the closest floating point number. This should be extremely accurate. I am interested in two things: first, you might have trouble with integers overflowing at some point. Does that happen?

If so, how many people can there be before you this happens? (One of the things that I learned was the pleasant surprise that Python can handle large integers without overflowing. I thought Python would have trouble with 36670.)

(i) (Optional) Since we are able to compute the probability two ways, we can check to see if there is there much of a difference? Generally, multiplying and dividing floating point numbers is fairly safe, but ad- dition and subtraction can be perilous. Since we are just multiplying and dividing floating point numbers in the first method, I'm guessing that the two methods should produce answers that are really close to each other.

The error should be the approximation minus the cor- rect answer. If x is the correct answer and y is the approximation, then y - x is the error. Use the second method above as the correct answer, and the first method as the approximation. Add a column giving the errors. Are the errors small? What is the worst error? (If you look on-line about errors, be careful since some authors use the absolute value of y - x.)

(j) (Optional) When dealing with small probabilities, the relative error is more important than the error.

There's a big difference in an error of .001 when the true probability is .5 and when it's .00000005. For x > 0, the relative error of approximating x by y is (y - x)/x. Add a column giving the relative errors. Are the relative errors small?

What is the worst relative error? (Again, if you're looking on-line, be careful about slight differences in the definition of relative error. One advantage of allowing the error to be positive or negative is that you can see if the approximation is above or below the true value.)