What is the probability you have 100 encounters and only see 1 distinct state?

Each member will choose a specific subtopic to focus on and conduct an in-depth study, write 3-4 pages about the subtopic they selected, and present it in class. Each member of the group must be submitting a short report, approximately 3-4 pages per student

You must type your paper as a Word/ pdf document as much as possible; only complicated figures can be hand-drawn, unless otherwise specified. NO scan of hand-written text will be accepted.
Honor Code:

You are responsible for your work. Cite all sources you used in your write-up. Plagiarism leads immediately to a non-passing grade.

In the United States, suppose that when you come across a state quarter it is equally likely to be any of the 50 states. We’ll call coming across a state quarter an encounter. The goal of the first part of this project is to answer, “How many encounters until you get all 50 states?” Please carefully explain the answer to each of these questions. A lot could be written about the last part. You are not expected to get the exact answer like with the others. Do the best you can.

a. What is the probability you have 100 encounters and only see 1 distinct state?

b. Suppose you have collected 20 state quarters. What is the probability you still have only seen 20 state quarters after you have 100 more encounters?

c. Let Xk be the number of encounters it takes to go from having seen k distinct state quarters to k+1.
What is the probability Xk=100?

d. What is the probability Xk=m for general m?
This will be useful information for answering the next few questions. A geometric random variable with success parameter p represents the number of trials, X, it takes until a success occurs. We assume that each trial is independent and has the same success probability, p. The standard example is the number of flips of a fair coin until a heads is obtained is a geometric with success parameter 1/2. For general p we have a formula P(X=k)=(1−p)k−1p. This says that there are k−1 failures, then the kth try is a success. Another useful formula is that the average (or expected value) of X has the formula EX=1/p.

e. Explain why Xk is a geometric random variable.

f. What is the average number of state quarters needed to go from k distinct states to k+1 states?
A related problem is known as the spread of a rumor. A village has 50 people in it. On day 1, a single villager learns a rumor. Each day whoever knows the rumor either keeps it to themselves (with probability 1/50), or tells one randomly selected villager (any specific villager has probability 1/50 of being told). As the days go on, more and more people know the rumor.

i. Explain why the average number of days for the village to know the rumor is no larger than the number of encounters it takes to see all 50 state quarters.

j. Provide a convincing argument that the average time for the village to know the rumor is less than 1/2 times your answer in (h).

Last Completed Projects