\n
We\u2019ll use the following notation:
\n\\begin{align}
\nf_k &= \\mathbf{Prob}(X=k) & &\\text{(probability mass function, pmf)} \\\\
\nF_k &= \\mathbf{Prob}(X\\leq k) & &\\text{(cumulative mass function, cmf)} \\\\
\n\\bar F_k &= \\mathbf{Prob}(X\\geq k) & &\\text{(complementary cmf)}
\n\\end{align}where $X$ is the outcome of a single roll of a fair $n$-sided die. Since it\u2019s a fair die, these are:
\n\\[
\nf_k=\\frac{1}{n}, \\qquad F_k=\\frac{k}{n}, \\qquad \\bar F_k=\\frac{n-k+1}{n}.
\n\\]Let\u2019s tackle the more complicated cases one by one. For the other events of interest, we\u2019ll use similar notation but with superscripts \u201cA\u201d (advantage), \u201cD\u201d (disadvantage), \u201cAD\u201d (advantage of disadvantage), and \u201cDA\u201d (disadvantage of advantage). So, for example, $f^\\textrm{DA}_k$ is the pmf for rolling with disadvantage of advantage.<\/p>\n
Rolling with advantage<\/h3>\n
Here, we roll the die twice and take the largest value. We can leverage the following property of the maximum function: $\\max(x,y) \\le k$ if and only if $x\\le k$ and $y\\le k$. If $X_1$ and $X_2$ are independent rolls of an $n$-sided die, we have:
\n\\begin{align}
\nF^{\\mathrm{A}}_k &= \\mathbf{Prob}(\\max(X_1,X_2) \\le k) \\\\
\n&= \\mathbf{Prob}(X_1\\le k,X_2\\le k) \\\\
\n&= \\mathbf{Prob}(X_1\\le k)\\,\\mathbf{Prob}(X_2\\le k) \\\\
\n&= F_k^2 \\\\
\n&= \\left(\\frac{k}{n}\\right)^2
\n\\end{align}Finally, we can use the fact that $f^{\\mathrm{A}}_k = F^{\\mathrm{A}}_k-F^{\\mathrm{A}}_{k-1}$ to compute the pmf:
\n\\[
\nf^{\\mathrm{A}}_k = \\frac{2k-1}{n^2}
\n\\]<\/p>\n
Rolling with disadvantage<\/h3>\n
Here, we use a similar approach, but with the complementary cmf instead:
\n\\begin{align}
\n\\bar F^{\\mathrm{D}}_k &= \\mathbf{Prob}(\\min(X_1,X_2) \\ge k) \\\\
\n&= \\mathbf{Prob}(X_1\\ge k,X_2\\ge k) \\\\
\n&= \\mathbf{Prob}(X_1\\ge k)\\mathbf{Prob}(X_2\\ge k) \\\\
\n&= \\bar F_k^2 \\\\
\n&= \\left(\\frac{n-k+1}{n}\\right)^2
\n\\end{align}Finally, we can use the fact that $f^{\\mathrm{D}}_k = \\bar F^{\\mathrm{D}}_k-\\bar F^{\\mathrm{D}}_{k+1}$ to compute the pmf:
\n\\[
\nf^{\\mathrm{D}}_k = \\frac{2n-2k+1}{n^2}
\n\\]<\/p>\n
Rolling with advantage of disadvantage<\/h3>\n
This case can be computed by iterating the strategies used in the previous two cases. Specifically:
\n\\begin{align}
\nF^{\\mathrm{AD}}_k &= \\left( F^{\\mathrm{D}}_k \\right)^2 \\\\
\n&= \\left( 1-\\bar F^{\\mathrm{D}}_{k+1} \\right)^2 \\\\
\n&= \\left( 1-\\left(\\frac{n-k}{n}\\right)^2 \\right)^2 \\\\
\n&= \\frac{k^2(2n-k)^2}{n^4}
\n\\end{align}As before, we can compute the pmf using $f^{\\mathrm{AD}}_k = F^{\\mathrm{AD}}_k-F^{\\mathrm{AD}}_{k-1}$:
\n\\[
\nf^{\\mathrm{AD}}_k = \\frac{(2 k-2 n-1) \\left(2 k^2-4 k n-2 k+2 n+1\\right)}{n^4}
\n\\]<\/p>\n
Rolling with disadvantage of advantage<\/h3>\n
This case can also be computed by iterating the previous cases. Specifically:
\n\\begin{align}
\n\\bar F^{\\mathrm{DA}}_k &= \\left( \\bar F^{\\mathrm{A}}_k \\right)^2 \\\\
\n&= \\left( 1-F^{\\mathrm{A}}_{k-1} \\right)^2 \\\\
\n&= \\left( 1-\\left(\\frac{k-1}{n}\\right)^2 \\right)^2 \\\\
\n&= \\frac{(k-n-1)^2 (k+n-1)^2}{n^4}
\n\\end{align}As before, we can compute the pmf using $f^{\\mathrm{DA}}_k = \\bar F^{\\mathrm{DA}}_k-\\bar F^{\\mathrm{DA}}_{k+1}$:
\n\\[
\nf^{\\mathrm{DA}}_k = \\frac{(1-2 k) \\left(2 k^2-2 k-2 n^2+1\\right)}{n^4}
\n\\]<\/p>\n
Continuous limit<\/h3>\n
We can also compute the continuous limit as $n$ tends to infinity. To make sense of this, we\u2019ll imagine that \u201crolling an $n$-sided die\u201d is replaced by \u201cpicking a uniformly chosen random number in $[0,1]$\u201d. So the probability mass functions are replaced by probability densities. The derivations are essentially identical to those above, except the densities for the base case are:
\n\\[
\nf(z)=1, \\qquad F(z)=z, \\qquad \\bar F_k=1-z.
\n\\]\n<\/p><\/div>\n
And here are the results:
\n [Show Solution]<\/a><\/p>\n
\n
Table of results<\/h3>\n
Here is a table containing the probability mass function (pmf), cumulative distribution (cmf), and complimentary cumulative distribution (ccmf) for the five combinations of advantage and disadvantaged dice rolls.
\n\\[
\n\\begin{array}{c|c|c|c}
\n\\text{case} & \\text{pmf }f_k & \\text{cmf }F_k & \\text{ccmf }\\bar F_k \\\\ \\hline
\n\\text{A}+\\text{D} & \\frac{1}{n} & \\frac{k}{n} & \\frac{n-k+1}{n} \\\\
\n\\text{A} & \\frac{2k-1}{n^2} & \\frac{k^2}{n^2} & \\frac{(n+k-1)(n-k+1)}{n^2} \\\\
\n\\text{D} & \\frac{2n-2k+1}{n^2} & \\frac{k(2n-k)}{n^2} & \\frac{(n-k+1)^2}{n^2} \\\\
\n\\text{A of D} & \\frac{(2 k-2 n-1) \\left(2 k^2-4 k n-2 k+2 n+1\\right)}{n^4} & \\frac{k^2(2n-k)^2}{n^4} & \\frac{(n-k+1)^2 \\left(n^2-k^2+2kn+2k-2 n-1\\right)}{n^4}\\\\
\n\\text{D of A} & \\frac{(2k-1) \\left(2n^2-2k^2+2k-1\\right)}{n^4} & \\frac{k^2 \\left(2 n^2-k^2\\right)}{n^4} & \\frac{(n+k-1)^2 (n-k+1)^2}{n^4} \\\\
\n\\end{array}
\n\\]And here is a table for the continuous case, containing the probability density function (pdf), cumulative distribution (cdf), and complimentary distribution (ccdf).
\n\\[
\n\\begin{array}{c|c|c|c}
\n\\text{case} & \\text{pdf }f(z) & \\text{cdf }F(z) & \\text{ccdf }\\bar F(z) \\\\ \\hline
\n\\text{A}+\\text{D} & 1 & z & 1-z \\\\
\n\\text{A} & 2z & z^2 & 1-z^2 \\\\
\n\\text{D} & 2-2z & z(2-z) & (1-z)^2 \\\\
\n\\text{A of D} & 4z(1-z)(2-z) & z^2(2-z)^2 & (1-z)^2(1+2z-z^2)\\\\
\n\\text{D of A} & 4z(1-z^2) & z^2(2-z^2) & (1-z^2)^2 \\\\
\n\\end{array}
\n\\]<\/p>\n
Expected value<\/h3>\n
We can compute expected values as a function of $n$ by evaluating $\\sum_{k=1}^n k\\,f_k$ for each of the cases. We can also evaluate the continuous limit by computing $\\int_0^1 z\\,f(z)\\,\\mathrm{d}z$ for each case. I rearranged the columns so that they are sorted from largest to smallest.
\n\\[
\n\\begin{array}{c|c}
\n\\text{case} & \\text{Expectation} & \\text{Continuous limit} \\\\ \\hline
\n\\text{A} & \\frac{(n+1) (4 n-1)}{6 n} & \\frac{2}{3} \\\\
\n\\text{D of A} & \\frac{(n+1) \\left(16 n^3-n^2+n-1\\right)}{30 n^3} & \\frac{8}{15} \\\\
\n\\text{A}+\\text{D} & \\frac{n+1}{2} & \\frac{1}{2} \\\\
\n\\text{A of D} & \\frac{(n+1) (2 n+1) \\left(7 n^2-3 n+1\\right)}{30 n^3} & \\frac{7}{15} \\\\
\n\\text{D} & \\frac{(n+1) (2 n+1)}{6 n} & \\frac{1}{3} \\\\
\n\\end{array}
\n\\]Indeed, if we take the Expectation column $E$, which takes on values in $\\{1,\\dots,n\\}$, compute $\\frac{E-1}{n-1}$ in order to normalize the range of possible outcomes to $[0,1]$, then let $n\\to\\infty$, we recover the \u201cContinuous limit\u201d column. Here is a plot of this phenomenon in action.<\/p>\n
$\"\"$ <\/a><\/p>\n
Ultimately, we conclude that \u201cdisadvantage of advantage\u201d is better than \u201cadvantage of disadvantage\u201d. This idea that the \u201cminimums of maximums\u201d is always larger than the \u201cmaximum of minimums\u201d is actually a much more general notion that applies to arbitrary functions. The result is known as the max-min inequality<\/a> and it states that for any<\/em> function $f:Z\\times W \\to \\mathbb{R}$, we have:
\n\\[
\n\\inf_{w\\in W}\\sup_{z\\in Z}f(z,w) \\geq \\sup_{z\\in Z}\\inf_{w\\in W}f(z,w)
\n\\]<\/p>\n
Rolling $k$ or better<\/h3>\n
If the task is to roll $k$ or better, then we are seeking the probability that our outcome $X$ satisfies $X \\ge k$. This is precisely the complimentary cumulative distribution function! Plotting these values for $n=6$, we obtain:<\/p>\n
$\"\"$ <\/a><\/p>\n
As anticipated, when $k=1$, all probabilities are $1$. The \u201cadvantage\u201d roll is always best, while \u201cdisadvantage\u201d is always worst. \u201cdisadvantage of advantage is second best for $k=1,2,3,4$, but for $k=5,6$ it\u2019s best to roll a single die. We observe a similar result when $n=20$:<\/p>\n
$\"\"$ <\/a><\/p>\n
This time, \u201cdisadvantage of advantage\u201d is second best for $1\\le k \\le 13$ and rolling a single die is best for $14 \\le k \\le 20$. In general, we can compute where the transition occurs as a function of $n$ by seeing which value of $k$ leads to $\\bar F^{\\text{DA}}_k = \\bar F_k$. This leads to the equation:
\n\\[
\n\\frac{(n+k-1)^2 (n-k+1)^2}{n^4} = \\frac{n-k+1}{n}
\n\\]Solving this equation for $k$ and discarding extraneous solutions, we find the threshold occurs at:
\n\\[
\nk_0 = 1 + \\left( \\frac{\\sqrt{5}-1}{2} \\right) n
\n\\]So if $1\\leq k < k0$, we have $\\bar F^{\\text{DA}}_k \\gt \\bar F_k$ and if $k_0 \\lt k \\leq n$, we have $\\bar F^{\\text{DA}}_k \\lt \\bar F_k$. Ok, so what happens in the limit? We can plot the continuous complimentary cdfs and obtain:<\/p>\n
$\"\"$ <\/a><\/p>\n
The pattern is the same, and we can solve for the cross-over point as before, by setting $\\bar F^{\\text{DA}}(z) = \\bar F(z)$. This time, the equation is $(1-z^2)^2=1-z$. Solving for $z$, we obtain
\n\\[
\nz_0 = \\frac{\\sqrt{5}-1}{2}
\n\\]This is not surprising, as we could have simply normalized the discrete result as we did for expectations and take the limit $n\\to\\infty$ to obtain the same result. This number is the inverse of the Golden Ratio<\/a>, neat!\n<\/p><\/div>\n
<\/p>\n<\/body>","protected":false},"excerpt":{"rendered":"
This week\u2019s Riddler Classic is a probability problem about the game Dungeons & Dragons. Here it goes: When you roll a die \u201cwith advantage,\u201d you roll the die twice and keep the higher result. Rolling \u201cwith disadvantage\u201d is similar, except you keep the lower result instead. The rules further specify that when a player rolls … Continue reading “Dungeons & Dragons”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":2832,"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":[8,2],"class_list":["post-2826","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-probability","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2826","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=2826"}],"version-history":[{"count":6,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2826\/revisions"}],"predecessor-version":[{"id":2838,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2826\/revisions\/2838"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/2832"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=2826"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=2826"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=2826"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}