1
$\begingroup$

I'm heading out to a bachelor party, and we are going to be creating a tournament of our favorite songs by a certain band. It will be a sweet 16 style bracket tournament. Hopefully by the end of it all, we will have consensus on what their best song is, and then my friends and I will have nothing to talk about from here on out.

To seed the tourney, each person is choosing their favorite 5 songs, and the bracket will be populated by how frequently songs show up in everyone's lists.

The band has a catalog of about 200 songs. There are 13 of us. My question is, with everyone choosing 5 songs, what is the probability of at least 16 songs being represented twice? How many songs should each person choose to raise the probability to over 50%.

What I've tried.

I'm an not a mathematician. I got a C in stats in college.

If everyone chose one song, I think the probability would be 6.5%. (1/200) * 13.

Maybe that's not right... How do I account for everyone choosing 5 songs? those 5 songs would be sure to be different, so I'm a bit lost.

Thanks!

$\endgroup$
2
  • 1
    $\begingroup$ One cannot give an answer without making some highly implausible assumptions. For instance, it would not be real-life sensible to assume that all songs are equally likely. $\endgroup$ Jun 22, 2014 at 15:30
  • $\begingroup$ That's a great point, but for this I'm fine assuming that all songs are equal. $\endgroup$
    – Jeff Ryan
    Jun 22, 2014 at 15:31

1 Answer 1

0
$\begingroup$

I decided to take apart the relevant information for people who want to try this problem:

  • $200$ songs
  • $13$ people, everyone able to choose $5$ (distinct) songs

What is the probability that at least 16 songs will be represented twice?

======

The Implausible Assumption Approach:

Suppose that $200$ is a suitable number to imply that the occurrence of one song being represented twice is independent from other songs being represented twice. Also, assume that $13$ is a suitable number to imply that one person's choice of a song is independent from another person's of a song. (The second assumption is not at all realistic.)

The probability that a (single) song is represented (exactly) twice is the probability that exactly two people choose the song, or $$\dfrac{13!}{2!\text{ }11!}\left(\dfrac{1}{200}\right)^{2}\left(\dfrac{199}{200}\right)^{11} \approx 0.002 \text{.}$$ Furthermore, if $X$ is the number of songs represented exactly twice, we wish to find $$\mathbb{P}\left(X \geq 16\right) = \sum\limits_{k=16}^{200}{200 \choose k}(0.002)^{k}(0.998)^{200-k}\approx7.83\times10^{-21}\text{,}$$ a very small number (for your purposes, pretty much $0$).

What I would do:

I would do some sort of Monte Carlo estimation of the probability. (I am by no means an expert on Monte Carlo.)

I ran the following code via Python:

from itertools import groupby
import random

geq_16_counter = 0
for j in range(--insert # of trials -- + 1):
     songlst = []
     for i in range(14):
         songlst = songlst + random.sample(range(201), 5)
     songlst = sorted(songlst)
     songlst_freq = [len(list(group)) for key, group in groupby(songlst)]
     if songlst_freq.count(2) >= 16:
         geq_16_counter += 1
print geq_16_counter

What is this code doing? It looks at some number of 13 people (the "trials"), generates a unique number from 1 to 200 of size 5 for each person, throws all of these numbers into a list, and creates another list consisting of how frequently each song (numbers 1 to 200, that is) occurs. If the number of 2s is greater than or equal to 16, it adds one to a counter which counts how often the $\geq 16$ condition occurs. (There is a good chance my code is wrong somewhere... I'm a beginner at Python.)

Setting the number of groups of 13 people equal to 100 tended to give a number of 0. When increased to 1000, I saw numbers mostly from 1 through 5. At 10000, I saw numbers mostly in the 11-16 range. At 100000, I saw numbers in the 125-127 range.

This is by no means a good way to estimate the probability with a few iterations of the program, but my estimate would be $$\dfrac{126}{100000} \approx 1.26\%\text{.}$$ I am currently running $1000000$ trials to see what I get and will post that up as well.

Edit: 1,000,000 trials gave me 1295, or

$$\dfrac{1295}{1000000} \approx 0.0013 = 0.13\%\text{.}$$ So it looks like the probability drops quite a bit.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .