th<\/sup>; that is, the probability of completing \\(\\delta – 1\\) unproductive purchases, then a successful one. Now the probability of hitting a sequence of \\(\\delta – 1\\) unproductive purchases is exactly \\((k\/n)^{\\delta-1}\\); hence $$
\n\t\\P{T_{k+1} = T_{k} + \\delta} = \\left(\\frac{k}{n}\\right)^{\\delta-1}\\left(1 – \\frac{k}{n}\\right)
\n$$<\/p>\nSumming over positive values of \\(\\delta\\) yields $$
\n\t\\begin{align*}
\n\t\t\\E{\\Delta_k} &= \\sum_{\\delta = 1}^\\infty \\P{T_k = T_{k-1} + \\delta} \u00b7 \\delta = \\sum_{\\delta = 1}^\\infty (k\/n)^{\\delta-1} \u00b7 (1 – k\/n) \u00b7 \\delta\\\\
\n\t\t\t\t\t &= (1 – k\/n) \\sum_{\\delta = 1}^\\infty \\delta (k\/n)^{\\delta-1} = (1 – k\/n) \\frac{1}{(1 – k\/n)^2}\\\\
\n\t\t\t\t\t &= \\frac{1}{1 – k\/n} = \\frac{n}{n-k}
\n\t\\end{align*}
\n$$<\/p>\n
And summing over \\(k\\) yields $$
\n\t\\begin{align*}
\n\t\t\\E{T_n} &= \\sum_{k=0}^{n-1} \\E{\\Delta_k} = \\sum_{k=0}^{n-1} \\frac{n}{n-k} = n \\sum_{k=1}^{n} \\frac{1}{k}\\\\
\n\t\t\t\t&= n \\left(1 + \\frac12 + \\frac13 + \\ldots + \\frac1{n}\\right)
\n\t\\end{align*}
\n$$<\/p>\n
Which, for large \\(n\\), is \\(n \\left(\\log(n) + \\gamma + \\frac1{2n} + o\\left(\\frac1n\\right)\\right)\\) (where \\(\\gamma \\approx 0.57722\\) denotes the Euler\u2013Mascheroni constant).<\/p>\n
Note that, as expected, \\(\\E{\\Delta_k}\\) quickly increases as \\(k\\) grows larger: the more prizes have already been found, the harder it is to get a new one, to the point that finding the last prize requires \\(n\\) purchases on average.<\/p>\n
Numerical simulations<\/h3>\n
The experimental data above was simulated using the following code:<\/p>\n
\r\n\trepeat = 1000*1000\r\n\ttime_to = defaultdict(Counter)\r\n\t\r\n\tfor _ in range(repeat):\r\n\t\tpurchased = 0\r\n\t\tcollected_prizes = set()\r\n\t\t\r\n\t\twhile len(collected_prizes) < n: # Until all prizes have been found\r\n\t\t\tpurchased += 1 # Purchase one more box\r\n\t\t\tprize = random.randint(1, n) # Open it\r\n\t\t\tif prize not in collected_prizes: # Is it a new prize ?\r\n\t\t\t\ttime_to[len(collected_prizes) + 1][purchased] += 1 # Yes, count it !\r\n\t\t\t\tcollected_prizes.add(prize)\t# And add it to list of already found prizes\r\n<\/pre>\nConclusion<\/h2>\n
One might want to find some intuitive way to comprehend the formula derived above, \\(\\E{T_n} = n\\left(1 + 1\/2 + \\ldots + 1\/n\\right)\\). A relatively easy way to get such an intuition is to summarize the calculation above, realizing that each new packet bought after finding the \\(k\\)th<\/sup> prize brings an extra prize with probability \\((n-k)\/n\\) ; since each purchase is independent, it takes on average \\(n \/ (n-k)\\) purchases to find a new prize; then summing over \\(k\\) yields the final formula.<\/p>\nHave you ever completed a full set of cereal box prizes? How long did it take?<\/p>\n","protected":false},"excerpt":{"rendered":"
Children’s cereal manufacturers often attract the attention of young clients by including small prizes and toys in every box; sometimes all prizes are identical, but most often individual prizes are part of a collection, and kids are encouraged to collect them and try to complete a full collection. How long does it take ?<\/p>\n","protected":false},"author":1,"featured_media":823,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[33,57,32,17,8,14],"tags":[108,107,63],"_links":{"self":[{"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/posts\/764"}],"collection":[{"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/comments?post=764"}],"version-history":[{"count":5,"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/posts\/764\/revisions"}],"predecessor-version":[{"id":827,"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/posts\/764\/revisions\/827"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/media\/823"}],"wp:attachment":[{"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/media?parent=764"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/categories?post=764"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/tags?post=764"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"Chocapic](\"http:\/\/pit-claudel.fr\/clement\/blog\/images\/chocapic.jpg\")
Children’s cereal manufacturers often attract the attention of young clients by including small prizes and toys in every box; sometimes all prizes are identical, but most often individual prizes are part of a collection, and kids are encouraged to collect them and try to complete a full collection. How long does it take ?<\/p>\n![\"Theoretical](\"http:\/\/pit-claudel.fr\/clement\/blog\/images\/cereals-time-to-completion.png\")
<\/a><\/p>\n