{"id":2620,"date":"2019-04-05T17:34:24","date_gmt":"2019-04-05T22:34:24","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=2620"},"modified":"2019-04-06T01:28:18","modified_gmt":"2019-04-06T06:28:18","slug":"gift-card-puzzle","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/gift-card-puzzle\/","title":{"rendered":"Gift card puzzle"},"content":{"rendered":"

Here is a puzzle from the Riddler<\/a> about gift cards:<\/p>\n

\nYou’ve won two gift cards, each loaded with 50 free drinks from your favorite coffee shop. The cards look identical, and because you’re not one for record-keeping, you randomly pick one of the cards to pay with each time you get a drink. One day, the clerk tells you that he can’t accept the card you presented to him because it doesn’t have any drink credits left on it.<\/p>\n

What is the probability that the other card still has free drinks on it? How many free drinks can you expect are still available?<\/p><\/blockquote>\n

Here is my solution:
\n[Show Solution]<\/a><\/p>\n

\n

Let’s suppose each card starts with $n$ drinks. There are three ways the sequence of buying drinks can end:<\/p>\n

    \n
  1. The first card gets maxed out and the second card has $k$ drinks remaining with $k\\ge 1$. This means we purchased a total of $2n-k$ drinks and $n$ of them ended up on the first card. Then, we tried to purchase one additional drink on the first card and the buying stopped. The probability of this occurring is: $(\\tfrac{1}{2})^{2n-k+1}\\binom{2n-k}{n}$.\n
  2. both cards get maxed out and then we try to buy one more drink on either card. This means we purchased a total of $2n$ drinks and $n$ of them ended up on the first card. The probability of this occurring is $(\\tfrac{1}{2})^{2n}\\binom{2n}{n}$.\n
  3. The second card gets maxed out and the first card has $k$ drinks remaining with $k\\ge 1$. This is exactly analogous to the first case, and the probability of this occurring is again: $(\\tfrac{1}{2})^{2n-k+1}\\binom{2n-k}{n}$.\n<\/ol>\n

    Putting all of this together, we end up with a tidy formula for $p(n,k)$, the probability that when the game ends, the other card has exactly $k$ drinks remaining on it:<\/p>\n

    $\\displaystyle
    \np(n,k) = \\frac{1}{2^{2n-k}} \\binom{2n-k}{n}
    \n$<\/span><\/p>\n

    To double-check that this is a valid probability mass function, we should have $\\sum_{k=0}^n p(n,k) = 1$. This is indeed the case, but it’s rather challenging to verify. Here is a link to the WolframAlpha computation<\/a>. Here is plot of the probability mass function for $n=50$.<\/p>\n

    \"\"<\/a><\/p>\n

    We can now answer the first question: the probability that the other card still has drinks on it is one minus the probability that there are no drinks left, i.e. $1-p(n,0)$. This evaluates to:<\/p>\n

    $\\displaystyle
    \n\\mathrm{Prob}\\Bigl(\\begin{smallmatrix}\\text{there are drinks left}\\\\\\text{on the other card}\\end{smallmatrix}\\Bigr)
    \n= 1-\\frac{1}{4^n} \\binom{2n}{n} \\approx 1-\\frac{1}{\\sqrt{\\pi n}}
    \n$<\/span><\/p>\n

    This makes sense; the only way there can be no drinks left is if we purchased $2n$ drinks, and we were lucky to use each card exactly $n$ times. We would expect this probability to get smaller as $n$ gets larger. The approximation I used above comes from Stirling-like approximations for binomial coefficients (see here<\/a>). When $n=50$ as in the problem statement, the probability evaluates to $92.04\\%$. Here is a plot showing how the probability of there being drinks on the other card slowly tends to $1$ as $n$ gets larger:<\/p>\n

    \"\"<\/a><\/p>\n

    Now let’s address the second question: what is the expected number of drinks on the other card? We will compute the expected value directly from the probability mass function: $E_n = \\sum_{k=0}^n k\\, p(n,k)$. We find:<\/p>\n

    $\\displaystyle
    \n\\mathbb{E}\\Bigl(\\begin{smallmatrix}\\text{number of drinks left}\\\\\\text{on the other card}\\end{smallmatrix}\\Bigr)
    \n= \\frac{2n+1}{4^n}\\binom{2n}{n}-1 \\approx \\frac{2n+1}{\\sqrt{\\pi n}}-1
    \n$<\/span><\/p>\n

    Again, the derivation is challenging so I omitted it, but here is the WolframAlpha link<\/a>. Here is a plot of this function as it changes with $n$ along with the approximation (which is quite good!)<\/p>\n

    \"\"<\/a><\/p>\n

    When $n=50$ as in the problem statement, the expected number of drinks remaining on the other card is $7.0385$. This corresponds to the expected value of the probability distribution plotted in the first image.\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"

    Here is a puzzle from the Riddler about gift cards: You’ve won two gift cards, each loaded with 50 free drinks from your favorite coffee shop. The cards look identical, and because you’re not one for record-keeping, you randomly pick one of the cards to pay with each time you get a drink. One day, … Continue reading “Gift card puzzle”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":2625,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[9,6,8,2],"class_list":["post-2620","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-binomial","tag-counting","tag-probability","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2620","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=2620"}],"version-history":[{"count":5,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2620\/revisions"}],"predecessor-version":[{"id":2629,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2620\/revisions\/2629"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/2625"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=2620"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=2620"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=2620"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}