{"id":1766,"date":"2017-01-13T19:37:38","date_gmt":"2017-01-14T01:37:38","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=1766"},"modified":"2017-01-16T23:13:45","modified_gmt":"2017-01-17T05:13:45","slug":"impromptu-gambling-with-dice","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/impromptu-gambling-with-dice\/","title":{"rendered":"Impromptu gambling with dice"},"content":{"rendered":"<p>This <a href=\"https:\/\/fivethirtyeight.com\/features\/how-long-will-it-take-to-blow-out-the-birthday-candles\/\">Riddler<\/a> puzzle is an impromptu gambling game about rolling dice.<\/p>\n<blockquote><p>\nYou and I stumble across a 100-sided die in our local game shop. We know we need to have this die \u2014 there is no question about it \u2014 but we\u2019re not quite sure what to do with it. So we devise a simple game: We keep rolling our new purchase until one roll shows a number smaller than the one before. Suppose I give you a dollar every time you roll. How much money do you expect to win?<\/p>\n<p>Extra credit: What happens to the amount of money as the number of sides increases?\n<\/p><\/blockquote>\n<p>Here is my solution:<br \/>\n<a href=\"javascript:Solution('soln_impromptu_dice','toggle_impromptu_dice')\" id=\"toggle_impromptu_dice\">[Show Solution]<\/a><\/p>\n<div id=\"soln_impromptu_dice\" style=\"display: none\">\n<p>Suppose the die has $N$ sides. The key is to think about the problem recursively; the only thing that matters in determining the expected value is the number that was most recently rolled. Therefore, let&#8217;s define $f(n)$ to be the amount of money we expect to win if the last number we rolled was $n$. We&#8217;d like to solve for $f(1)$ since this is equivalent to the case where the game hasn&#8217;t started yet (any number subsequently rolled allows the game to continue). If we last rolled $n$, several cases emerge:<\/p>\n<ul>\n<li> If we roll $k \\in \\{1,2,\\dots,n-1\\}$ we win \\$1 and the game stops immediately. This will occur with probability $\\tfrac{n-1}{N}$.\n<li> If we roll $k \\in \\{n,n+1,\\dots,N\\}$, we add \\$1 to our winnings, and the game continues. We can expect to win an extra $f(k)$ as the game continues. Each number $k$ has an equal probability $\\tfrac{1}{N}$ of being rolled.\n<\/ul>\n<p>Since each number $\\{1,\\dots,N\\}$ has an equal chance to be rolled, we can write the following recursion for $f(n)$:<br \/>\n\\[<br \/>\nf(n) = \\frac{n-1}{N} + \\frac{1}{N}\\sum_{k=n}^N \\left( 1+f(k)\\right),\\qquad n=1,2,\\dots,N<br \/>\n\\]Evaluating this for $n=N$, we obtain the relation<br \/>\n\\[<br \/>\nf(N) = \\frac{N-1}{N} + \\frac{1}{N}\\left( 1+f(N)\\right)<br \/>\n\\]Solving for $f(N)$, we obtain $f(N)=\\tfrac{N}{N-1}$. This is our terminal condition: the expected winnings if we just rolled the highest possible number.<\/p>\n<p>Now rewrite the original recursion for both $n+1$ and $n$ and subtract one equation from the other, we obtain:<br \/>\n\\[<br \/>\nf(n+1)-f(n) = \\frac{1}{N}-\\frac{f(n)+1}{N}, \\qquad n = 1,2,\\dots,N-1<br \/>\n\\]Rearranging, we obtain the simple recursion:<br \/>\n\\[<br \/>\nf(n) = \\left(\\frac{N}{N-1}\\right)f(n+1),  \\qquad n = 1,2,\\dots,N-1<br \/>\n\\]Since $N$ is a constant, we can recursively evaluate this and obtain:<br \/>\n\\[<br \/>\nf(1) = \\left(\\frac{N}{N-1}\\right)^{N-1} f(N)<br \/>\n\\]Substituting the $f(N)$ we found earlier, we obtain our final answer:<\/p>\n<p style=\"text-align: center;\"><span style=\"background-color: #AFC8E6; padding: 25px 10px 25px 10px;\">$\\displaystyle<br \/>\nf(1) = \\left(\\frac{N}{N-1}\\right)^{N}<br \/>\n$<\/span><\/p>\n<p>Note that $f(1)$ is undefined if $N=1$. This makes sense; if there is only one side to the die, you&#8217;ll always roll the same thing and so the game never ends! Here is a plot of how the expected winnings change as a function of $N$:<\/p>\n<p><a href=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2017\/01\/impromptu_gambling.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2017\/01\/impromptu_gambling-1024x666.png\" alt=\"\" width=\"840\" height=\"546\" class=\"aligncenter size-large wp-image-1784\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2017\/01\/impromptu_gambling-1024x666.png 1024w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2017\/01\/impromptu_gambling-300x195.png 300w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2017\/01\/impromptu_gambling-768x499.png 768w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2017\/01\/impromptu_gambling.png 1109w\" sizes=\"auto, (max-width: 709px) 85vw, (max-width: 909px) 67vw, (max-width: 1362px) 62vw, 840px\" \/><\/a><\/p>\n<p>With a 100-sided die, we get an expected prize of $\\left(\\tfrac{100}{99}\\right)^{100} \\approx 2.7320$. As the number of sides increases, the expected prize decreases, but tends to a finite limit (the red line shown in the plot). In the limit $N\\to\\infty$, we have $f(1) \\to e \\approx 2.7183$. <\/p>\n<\/div>\n<p>For a more in-depth analysis of the distribution, read on:<br \/>\n<a href=\"javascript:Solution('soln_impromptu_dice2','toggle_impromptu_dice2')\" id=\"toggle_impromptu_dice2\">[Show Solution]<\/a><\/p>\n<div id=\"soln_impromptu_dice2\" style=\"display: none\">\n<h3>Computing the distribution<\/h3>\n<p>Let&#8217;s calculate the probability $p(N,k)$ that the game with an $N$-sided die lasts $k$ rounds. We can do this by counting carefully:<br \/>\n\\begin{align}<br \/>\np(N,k) &#038;= \\frac{\\text{#seq. of len. }k\\text{ from }\\{1,\\dots,N\\}\\text{, first decrease occurs at end}}{\\text{#sequences of length }k\\text{ from }\\{1,\\dots,N\\}}<br \/>\n\\end{align}The denominator is simply $N^k$. The numerator is a bit trickier, and we can argue as follows. Let&#8217;s define $S(N,k)$ be the number of nondecreasing sequences of length $k$ from $\\{1,\\dots,N\\}$. Then:<br \/>\n\\begin{align}<br \/>\n&#038;\\text{#seq. of len. }k\\text{ from }\\{1,\\dots,N\\}\\text{, first decrease occurs at end}\\\\<br \/>\n&#038; \\qquad = (\\text{#seq. of len. }k\\text{, first }k-1\\text{ is nondecreasing})\\\\<br \/>\n&#038;\\qquad\\qquad\\qquad-(\\text{#seq. of len. }k\\text{, entirely nondecreasing})\\\\<br \/>\n&#038; \\qquad = N S(N,k-1)-S(N,k)<br \/>\n\\end{align}So how do we count nondecreasing sequences? To calculate $S(N,k)$, imagine we have $a_1$ 1&#8217;s, $a_2$ 2&#8217;s, and so on up to $a_N$ $N$&#8217;s. Since the sequence is nondecreasing, these must occur in order. So we&#8217;re effectively looking for the number of ways of choosing $a_i \\ge 0$ for $i=1,\\dots,N$ such that $a_1+\\dots+a_N = k$. We can do this via the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Stars_and_bars_(combinatorics)\">stars and bars<\/a> method.<\/p>\n<p>The reasoning is as follows. Suppose we wanted to count the solutions to $a_1+a_2+a_3+a_4 = 5$ where each $a_i \\ge 0$. Now imagine an arrangement of 5 stars and 3 bars, such as \u2605|\u2605\u2605\u2605||\u2605. Each star is &#8220;1&#8221; and the bars are separators. This arrangement represents the solution $1 + 3 + 0 + 1 = 5$. So the total number of ways of splitting 5 stars into 4 groups is the same as the number of ways of arranging 5 stars and 3 bars. Equivalently, it&#8217;s the number of ways of picking, out of 8 slots, which 3 will have bars (or stars) in them, so ${8 \\choose 3} = 56$.<\/p>\n<p>Therefore, we conclude that $S(N,k) = {N+k-1 \\choose k}$. Substituting into our previous expression, we obtain after a bit of algebra:<br \/>\n\\begin{align}<br \/>\np(N,k) &#038;= \\frac{1}{N^k} \\left( N S(N,k-1)-S(N,k) \\right) \\\\<br \/>\n&#038;= \\frac{1}{N^k} \\left( N{N+k-2 \\choose k-1}-{N+k-1 \\choose k}\\right)\\\\<br \/>\n%&#038;= \\frac{1}{N^k} \\left( \\frac{(N+k-2)!N}{(k-1)!(N-1)!}-\\frac{(N+k-1)!}{k!(N-1)!}\\right)\\\\<br \/>\n%&#038;= \\frac{1}{N^k} \\frac{(N+k-2)!}{(k-1)!(N-1)!}\\left( N-\\frac{N+k-1}{k} \\right) \\\\<br \/>\n%&#038;= \\frac{1}{N^k} \\frac{(N+k-2)!}{(k-1)!(N-1)!}\\frac{(N-1)(k-1)}{k} \\\\<br \/>\n%&#038;= \\frac{1}{N^k} \\frac{(N+k-2)!}{k!(N-2)!}(k-1) \\\\<br \/>\n&#038;= \\frac{k-1}{N^k} {N+k-2\\choose k}<br \/>\n\\end{align}So we conclude that:<\/p>\n<p style=\"text-align: center;\"><span style=\"background-color: #AFC8E6; padding: 25px 10px 25px 10px;\">$\\displaystyle<br \/>\np(N,k) = \\frac{k-1}{N^k} {N+k-2\\choose k}<br \/>\n$<\/span><\/p>\n<p>As a sanity check, we can verify that $p(N,k)$ is a legitimate probability mass function for each $N$. In other words, the sum over $k$ is equal to $1$. We can check this using a neat telescoping sum argument:<br \/>\n\\begin{align}<br \/>\n\\sum_{k=2}^{\\infty} p(N,k)<br \/>\n&#038;= \\sum_{k=2}^{\\infty}\\frac{ N S(N,k-1)-S(N,k) }{N^k}\\\\<br \/>\n&#038;= \\sum_{k=2}^{\\infty}\\left(\\frac{S(N,k-1)}{N^{k-1}}-\\frac{S(N,k)}{N^k}\\right)\\\\<br \/>\n&#038;= \\frac{S(N,1)}{N}\\\\<br \/>\n&#038;=1<br \/>\n\\end{align}What we were after all along was the expected value, so we can compute this directly as well:<br \/>\n\\begin{align}<br \/>\n\\sum_{k=2}^{\\infty} k\\, p(N,k)<br \/>\n&#038;= \\sum_{k=2}^{\\infty}k\\frac{ N S(N,k-1)-S(N,k) }{N^k}\\\\<br \/>\n&#038;= \\sum_{k=2}^{\\infty}\\left[ \\left(\\frac{(k-1)S(N,k-1)}{N^{k-1}}-\\frac{kS(N,k)}{N^k}\\right) + \\frac{S(N,k-1)}{N^{k-1}} \\right]\\\\<br \/>\n&#038;= \\frac{S(N,1)}{N} + \\sum_{k=1}^{\\infty} \\frac{S(N,k)}{N^{k}} \\\\<br \/>\n&#038;= \\sum_{k=0}^{\\infty} \\frac{1}{N^{k}} {N+k-1 \\choose k}<br \/>\n\\end{align}This final sum is an example of a <a href=\"https:\/\/en.wikipedia.org\/wiki\/Binomial_series#Special_cases\">binomial series<\/a>. In general, we have:<br \/>\n\\[<br \/>\n(1-z)^{-N} = \\sum_{k=0}^{\\infty} {N+k-1 \\choose k} z^k\\qquad\\text{for all }|z|<1\n\\]If we let $z=\\frac{1}{N}$, we recover the solution we derived in the first part for the expected winnings in the game.\n\n\n\n<h3>Limiting distribution<\/h3>\n<p>To calculate the distribution as $N\\to\\infty$, we can make use of <a href=\"https:\/\/en.wikipedia.org\/wiki\/Stirling's_approximation\">Stirling&#8217;s approximation<\/a>, which says that $n! \\sim \\sqrt{2\\pi n}\\left(\\frac{n}{e}\\right)^n$ as $n\\to \\infty$.<br \/>\n\\begin{align}<br \/>\n\\lim_{N\\to\\infty} \\frac{k-1}{N^k} {N+k-2\\choose k}<br \/>\n&#038;= \\lim_{N\\to\\infty} \\frac{k-1}{N^k} \\frac{(N+k-2)!}{k!(N-2)!} \\\\<br \/>\n&#038;= \\lim_{N\\to\\infty} \\frac{k-1}{k!} e^{-k} \\frac{(N+k-2)^{N+k-2}}{N^k (N-2)^{N-2}} \\\\<br \/>\n&#038;= \\lim_{N\\to\\infty} \\frac{k-1}{k!} e^{-k} \\left( \\frac{N+k-2}{N} \\right)^k \\left( \\frac{N+k-2}{N-2} \\right)^{N-2}\\\\<br \/>\n&#038;= \\lim_{N\\to\\infty} \\frac{k-1}{k!} e^{-k} \\left( \\frac{N+k-2}{N-2} \\right)^{N-2}\\\\<br \/>\n&#038;= \\frac{k-1}{k!}<br \/>\n\\end{align}So the limiting distribution as $N\\to\\infty$ is given by:<\/p>\n<p style=\"text-align: center;\"><span style=\"background-color: #AFC8E6; padding: 25px 10px 25px 10px;\">$\\displaystyle<br \/>\np(\\infty,k) = \\frac{k-1}{k!}<br \/>\n$<\/span><\/p>\n<p>Again, as a sanity check, $p(\\infty,2) = \\frac{1}{2}$. This makes sense because if your die has a large number of sides, your second number will be smaller than your first about half the time. Here is an animation of how the distribution changes as we add more sides to the die.<\/p>\n<p><a href=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2017\/01\/impromptu_gambling.gif\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2017\/01\/impromptu_gambling.gif\" alt=\"\" width=\"752\" height=\"494\" class=\"aligncenter size-full wp-image-1788\" \/><\/a><\/p>\n<p>It was brought to my attention that there is already a nice write-up for this problem in <a href=\"http:\/\/www.jstor.org\/stable\/10.4169\/002557010x529798\">this article<\/a>. However, it&#8217;s behind a paywall. Here is an <a href=\"http:\/\/home.wlu.edu\/~siehlerj\/monotone.pdf\">earlier draft<\/a> of that same article that if freely available. If you&#8217;d like to see another solution method, I encourage you to check it out! Of note, the alternate solution also treats the case where the dice rolls are real numbers in $[0,1]$. This case is in fact equivalent to the case of having an $N$-sided die with $N\\to\\infty$.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>This Riddler puzzle is an impromptu gambling game about rolling dice. You and I stumble across a 100-sided die in our local game shop. We know we need to have this die \u2014 there is no question about it \u2014 but we\u2019re not quite sure what to do with it. So we devise a simple &hellip; <a href=\"https:\/\/laurentlessard.com\/bookproofs\/impromptu-gambling-with-dice\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Impromptu gambling with dice&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":1788,"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,15,2],"class_list":["post-1766","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-binomial","tag-counting","tag-probability","tag-recursion","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1766","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=1766"}],"version-history":[{"count":30,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1766\/revisions"}],"predecessor-version":[{"id":1799,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1766\/revisions\/1799"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/1788"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=1766"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=1766"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=1766"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}