Silly MT Dew contest question.

[Nottom]

I was looking at the most recent Mt. Dew promotion and it goes something like this:
Each bottle cap has an NFL team name printed on it.
If you get 2 of the same team, you can redeem them for a team hat.

My question is: (Assuming an even distibution of caps)
On average, how many Mt.Dews will someone have to buy before they get a matching pair? How long before you get 2 caps for "your" team?

[thylacine]

n teams, k caps. Prob that you don't have a pair is the same as

n "days" in a "year", k people, what is prob that no two have the same birthday.

It's the birthday problem.

[Nottom]

I don't know how to do that either ....

[thylacine]

I'm too lazy. Someone else do it. Just multiply prob of non-match each cap.

[Gamblor]

This is slightly different than the birthday problem.

Brute Force method:

He's not asking chances of having a match in X caps, he's asking average number of caps it will take.

So let's solve this.

Assume an infinite amount of every team.
i.e. 1000000 Raiders, 1000000 Dolphins, 1000000 Chiefs, etc. etc.

There are 32 NFL teams.

First cap gives you any random team.
Your chances of matching the first team on your second cap are 1/32.
Assume you miss: you now have two teams, and your chance of matching on your next cap is 2/32.

Following this reasoning, the most it will take to get a match is 33, because if you've gone 32 caps without a match, then you will have covered all 32 teams, and thus the 33rd will automatically match a team. The least is two, for obvious reasons...

P(match=2) = 1/32
P(match=3) = 2/32
P(match=4) = 3/32
etc. etc.
P(match=33) = 32/32 = 1

Weighted Average:
[(2)(1/32) + 3 (2/32) + 4(3/32)...33(32/32)]/32

Average number of caps: 11.6875....

You may live without that hat, but I don't know if your sperm can live with it.

[BruceZ]

P(match=2) = 1/32
P(match=3) = 2/32
P(match=4) = 3/32
etc. etc.
P(match=33) = 32/32 = 1

Weighted Average:
[(2)(1/32) + 3 (2/32) + 4(3/32)...33(32/32)]/32

Average number of caps: 11.6875....


This is incorrect. The probabilities you have listed are for making it on the nth try assuming you missed it on the first n-1 tries. You would have to multiply each of these by the probability that you actually did miss it on each of the previous tries. The probability of missing it on previous tries gets smaller with each try, like this:

2*(1/32) + 3*(1-1/32)*2/32 + 4*[1-(1/32 + (1-1/32)]*3/32 + ...

This gets messy real fast, but there is a better way. The proability of making it on the (n+1)st try is:

P(32,n)/32^n * n/32

Where P(32,n) is permutations of 32 things taken n at at time = 32*31*30*...*(32-n+1). This is the number of ways to choose n teams without a match out of 32^n total ways to choose n teams. Then on the (n+1)st try, the probability of matching is n/32. When we sum this from n=1 to 32 we get 1 as we should. Now we take the weighted average like this:

sum{n=1 to 32} [ (n+1)*P(32,n)/32^n * n/32 ] = 7.77.

This was evaluated in Excel, and this is the average number of tries to produce a match.

Normally the birthday problem asks how many we have to choose before the chance of a match is better than 50%. For that, we just find where 1 - P(32,n)/32^n > 50%. That occurs for n=7. This is the median, whereas 7.77 is the mean.

A third question that might be asked is what try is most likely to produce the match? Remember with the dice the answer was the first one. Here, we find where P(32,n)/32^n * n/32 is maximum. That occurs for n=6, but that means it occurs on the 7th try since we have 6 misses. The probability that it occurs on the 7th try is 11.4%, and this is the maximum probability. 7 is called the "mode".

So now we have the mean=7.77, median = 7, and mode = 7.

[Gamblor]

'sfunny, it looked easier than i know it should have been

Same mistake everyone makes when calculating draws...

Weird how i can calculate a draw by taking 1-(Chance of missing on turn+river) but i can't answer a piece of s*** question.

[Nottom]

OK so now how many hundreds of Mt Dews will I have to buy on average if I really want a cheesy Panthers hat?

[BruceZ]

OK so now how many hundreds of Mt Dews will I have to buy on average if I really want a cheesy Panthers hat?

64 bottles on average. You can see this logically as we did in a similar problem recently, or you can evaluate the average mathematically. The logical method says that if a large number of people open caps until they get 2 Panthers, then 1/32 of all the caps must be Panthers, so the average person opens 64 caps. You can also evaluate:

sum{n=2 to infinity} [ n*(n-1)*(1/32)^2*(31/32)^(n-2) ]

I actually did this, and it was a real adventure. It required applying the geometric series trick 3 different times. This is a summed binomial distribution multiplied by n to get the expected value. (1/32)^2 is for the 2 Panthers, (31/32)^(n-2) is for the n-2 non-Panthers, and there are n-1 ways to choose the place for the first Panther, the last Panther is on the end. In the end this evaluates to exactly 64. Duh.

If you actually buy 64 bottles, your probability is only 60% that you will get Panthers. Here are all the cumulative probabilities of getting Panthers by a certain number of bottles:

<font class="small">Code:</font><hr /><pre>
#caps probability of particular team match
2 0.1%
3 0.3%
4 0.6%
5 0.9%
6 1.3%
7 1.8%
8 2.4%
9 3.0%
10 3.7%
11 4.5%
12 5.2%
13 6.1%
14 6.9%
15 7.8%
16 8.8%
17 9.7%
18 10.7%
19 11.8%
20 12.8%
21 13.9%
22 15.0%
23 16.1%
24 17.2%
25 18.3%
26 19.5%
27 20.6%
28 21.8%
29 22.9%
30 24.1%
31 25.3%
32 26.4%
33 27.6%
34 28.8%
35 29.9%
36 31.1%
37 32.2%
38 33.4%
39 34.5%
40 35.7%
41 36.8%
42 37.9%
43 39.0%
44 40.2%
45 41.3%
46 42.3%
47 43.4%
48 44.5%
49 45.5%
50 46.6%
51 47.6%
52 48.6%
53 49.6%
54 50.6%
55 51.6%
56 52.6%
57 53.5%
58 54.5%
59 55.4%
60 56.3%
61 57.2%
62 58.1%
63 59.0%
64 59.8%
65 60.7%
66 61.5%
67 62.3%
68 63.1%
69 63.9%
70 64.7%
71 65.5%
72 66.2%
73 67.0%
74 67.7%
75 68.4%
76 69.1%
77 69.8%
78 70.4%
79 71.1%
80 71.8%
81 72.4%
82 73.0%
83 73.6%
84 74.2%
85 74.8%
86 75.4%
87 76.0%
88 76.5%
89 77.1%
90 77.6%
91 78.1%
92 78.6%
93 79.1%
94 79.6%
95 80.1%
96 80.6%
97 81.0%
98 81.5%
99 81.9%
100 82.3%
101 82.8%
102 83.2%
103 83.6%
104 84.0%
105 84.4%
106 84.7%
107 85.1%
108 85.5%
109 85.8%
110 86.2%
111 86.5%
112 86.8%
113 87.1%
114 87.5%
115 87.8%
116 88.1%
117 88.4%
118 88.7%
119 88.9%
120 89.2%
121 89.5%
122 89.7%
123 90.0%
124 90.2%
125 90.5%
126 90.7%
127 91.0%
128 91.2%
129 91.4%
130 91.6%
131 91.8%
132 92.0%
133 92.2%
134 92.4%
135 92.6%
136 92.8%
137 93.0%
138 93.2%
139 93.4%
140 93.5%
141 93.7%
142 93.9%
143 94.0%
144 94.2%
145 94.3%
146 94.5%
147 94.6%
148 94.7%
149 94.9%
150 95.0%
151 95.1%
152 95.3%
153 95.4%
154 95.5%
155 95.6%
156 95.7%
157 95.9%
158 96.0%
159 96.1%
160 96.2%
161 96.3%
162 96.4%
163 96.5%
164 96.6%
165 96.6%
166 96.7%
167 96.8%
168 96.9%
169 97.0%
170 97.1%
171 97.1%
172 97.2%
173 97.3%
174 97.4%
175 97.4%
176 97.5%
177 97.6%
178 97.6%
179 97.7%
180 97.8%
181 97.8%
182 97.9%
183 97.9%
184 98.0%
185 98.0%
186 98.1%
187 98.1%
188 98.2%
189 98.2%
190 98.3%
191 98.3%
192 98.4%
193 98.4%
194 98.5%
195 98.5%
196 98.5%
197 98.6%
198 98.6%
199 98.7%
200 98.7%
201 98.7%
202 98.8%
203 98.8%
204 98.8%
205 98.9%
206 98.9%
207 98.9%
208 99.0%
209 99.0%
210 99.0%
211 99.0%
212 99.1%
213 99.1%
214 99.1%
215 99.1%
216 99.2%
217 99.2%
218 99.2%
219 99.2%
220 99.3%
221 99.3%
222 99.3%
223 99.3%
224 99.3%
225 99.3%
226 99.4%
227 99.4%
228 99.4%
229 99.4%
230 99.4%
231 99.4%
232 99.5%
233 99.5%
234 99.5%
235 99.5%
236 99.5%
237 99.5%
238 99.5%
239 99.6%
240 99.6%
241 99.6%
242 99.6%
243 99.6%
244 99.6%
245 99.6%
246 99.6%
247 99.6%
248 99.7%
249 99.7%
250 99.7%
251 99.7%
252 99.7%
253 99.7%
254 99.7%
255 99.7%
256 99.7%
257 99.7%
258 99.7%
259 99.7%
260 99.8%
261 99.8%
262 99.8%
263 99.8%
264 99.8%
265 99.8%
266 99.8%
267 99.8%
268 99.8%
269 99.8%
270 99.8%
271 99.8%
272 99.8%
273 99.8%
274 99.8%
275 99.8%
276 99.8%
277 99.8%
278 99.9%
279 99.9%
280 99.9%
281 99.9%
282 99.9%
283 99.9%
284 99.9%
285 99.9%
286 99.9%
287 99.9%
288 99.9%
289 99.9%
290 99.9%
291 99.9%
292 99.9%
293 99.9%
294 99.9%
295 99.9%
296 99.9%
297 99.9%
298 99.9%
299 99.9%
300 99.9%
</pre><hr />

Here are the cumulative probabilities for getting any team:

<font class="small">Code:</font><hr /><pre>
# caps probability of any match
1 0.0%
2 3.1%
3 9.2%
4 17.7%
5 28.0%
6 39.2%
7 50.6%
8 61.4%
9 71.1%
10 79.2%
11 85.7%
12 90.6%
13 94.1%
14 96.5%
15 98.0%
16 99.0%
17 99.5%
18 99.8%
19 99.9%
20 100.0%
21 100.0%
22 100.0%
23 100.0%
24 100.0%
25 100.0%
26 100.0%
27 100.0%
28 100.0%
29 100.0%
30 100.0%
31 100.0%
32 100.0%
33 100.0%
</pre><hr />

We now completely understand the all important Mountain Dew problem. I have some neat graphs too, but I can't put them on here. Should we alert the Nobel committee?

[thylacine]

Use "generating functions" to find

sum{n=0 to infinity} [ n*(n-1)*(1/32)^2*(31/32)^(n-2) ]

(Note n=0,1 terms are zero). Start with geometric series

(1-x)^{-1}=sum{n=0 to infinity} [x^n]

Then differentiate both sides twice with respect to x. Then subsitute x=31/32. Then multiply by (1/32)^2.

BINGO! There's your answer!

[RollaJ]

[ QUOTE ]
OK so now how many hundreds of Mt Dews will I have to buy on average if I really want a cheesy Panthers hat?

[/ QUOTE ]

On average you will need 2 caps. Whatever cap you get, go to that specific city at CraigsList (http://www.craigslist.org/) and offer the one you want up for trade for a panther one, do this twice and you get a hat for 2 caps and two stamps

,,,, easier than all that math /images/graemlins/grin.gif

[Copernicus]

You must be attending Johnny Hearts Leisure U.

[BruceZ]

Yeah, that trick works nicely in this case. I've used that before in other applications, but it usually requires a little extra fiddling. Not here though.

I thought you were going to say moment generating functions, as in psi(t) = E(e^tX), and then E(X) = psi'(0). That can be used to find the mean of a binomial distribution when it is a function of k with constant n, but here k is fixed and we have variable n, so it doesn't seem to be helpful.

[RollaJ]

I majored in economics, this seemed like the right answer to me