Problem 96

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

Family reunion tester

Due: April 29
Points: 4

You are going to a randomized algorithms convention in a hotel. In that same hotel, there is also another convention, some sort of family reunion (but you don't know the name of the family that is re-uniting).

Assume the following as known facts:

  • In the family reunion, at least 70% of the people share the same last name.
  • In the randomized algorithms convention, at most 5% of the people have the same last name, for any given last name.

So you walk into a room and want to know whether you are in the family reunion, or at the randomized algorithms conference. Your algorithm is to ask two random people what there last names are. If they're the same, you assume you're in the family reunion room. If the two names are different, you assume you are in the randomized algorithms room.

Now you have four probabilities to calculate, to fill out a 2x2 table. Each row represents which of the two possibilities for the actual room you are in, and each column represents which of the two possibilites for the room your algorithm says you are in. So each row and each column should sum up to 100%. Two squares correspond to getting the correct answer, and the other two squares correspond to getting the wrong answer.

Using your table above, and assuming that you have a 50-50 chance of actually walking into either room, what is the overall probability that your algorithm gives the correct answer?