{"id":4121,"date":"2024-08-23T17:30:32","date_gmt":"2024-08-23T22:30:32","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=4121"},"modified":"2024-08-25T16:07:45","modified_gmt":"2024-08-25T21:07:45","slug":"round-round-get-a-round","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/round-round-get-a-round\/","title":{"rendered":"Round, round, get a round"},"content":{"rendered":"

This week’s Fiddler<\/a> is about rounding!<\/p>\n

\nLet $\\text{round}(x)$ be the value of $x$ rounded to the nearest integer. Suppose $x_1,\\dots,x_n$ are independent uniformly distributed random variables in $[0,1]$. Find the probability that
\n\\[
\n\\text{round}(x_1+\\cdots+x_n) = \\text{round}(x_1)+\\cdots+\\text{round}(x_n)
\n\\]\n<\/p><\/blockquote>\n

My solution:
\n[Show Solution]<\/a><\/p>\n

\n

Let’s call the probability we seek $p(n)$. The values of the $x_i$ determine what sums are even possible, so let’s consider some cases based on the possible values of $\\text{round}(x_1)+\\cdots+\\text{round}(x_n)$. Suppose that $k$ of the variables are in in the interval $[\\tfrac{1}{2},1]$ and the remaining $n-k$ variables are in $[0,\\tfrac{1}{2}]$. The probability of this occurring is $\\tfrac{1}{2^n}\\binom{n}{k}$. In this case,
\n\\[
\n\\sum_{i=1}^n \\text{round}(x_i) = k
\n\\]Note: We can ignore the issue of whether $\\tfrac{1}{2}$ rounds to $0$ or $1$ since the probability of $\\tfrac{1}{2}$ occurring is zero. Define a set of rescaled variables $y_i$ in $[0,1]$ as follows:
\n\\[
\ny_i = \\begin{cases}
\n2x_i-1 & \\text{if }i=1,\\dots,k\\\\
\n2x_i & \\text{if }i=k+1,\\dots,n
\n\\end{cases}
\n\\]Now let’s calculate the probability that the sum of the $x_i$ also rounds to $k$ and express it in terms of the $y_i$:
\n\\begin{align*}
\n\\mathrm{Prob}\\left( \\text{round}\\biggl(\\sum_{i=1}^n x_i\\biggr) = k\\right)
\n&= \\mathrm{Prob}\\left( k-\\tfrac{1}{2} \\leq \\sum_{i=1}^n x_i \\leq k+\\tfrac{1}{2} \\right) \\\\
\n&= \\mathrm{Prob}\\left( k-1 \\leq \\sum_{i=1}^n y_i \\leq k+1 \\right)
\n\\end{align*}The sum of the $y_i$, which is a sum of $n$ independent variables in $[0,1]$ follows a so-called Irwin-Hall distribution<\/a>, whose CDF is given by:
\n\\[
\nF(x) = \\text{Prob}\\bigl( y_1+\\cdots+y_n \\leq x \\bigr) = \\frac{1}{n!}\\sum_{k=0}^{\\lfloor x \\rfloor} (-1)^k \\binom{n}{k}(x-k)^n
\n\\]Therefore, the probability we seek is $F(k+1)-F(k-1)$, or:
\n\\[
\n\\frac{1}{n!}\\sum_{m=0}^{k+1} (-1)^m \\binom{n}{m}(k+1-m)^n
\n-\\frac{1}{n!}\\sum_{m=0}^{k-1} (-1)^m \\binom{n}{m}(k-1-m)^n
\n\\]Rearranging terms a bit, we obtain:
\n\\[
\n\\frac{(-1)^{n+k}}{n!} \\binom{n}{k}+
\n\\frac{1}{n!}\\sum_{m=0}^{k} (-1)^m \\binom{n}{m}\\bigl( (k+1-m)^n-(k-1-m)^n\\bigr)
\n\\]By writing out the terms carefully, we can group like $n^\\text{th}$ powers and we obtain a simpler equivalent expression:
\n\\[
\n\\frac{1}{n!}\\sum_{m=0}^k(-1)^m\\left[ \\binom{n+1}{m}-\\binom{n+1}{m-1}\\right](k+1-m)^n
\n\\]Remember this was the probability that the two roundings are the same when $k$ of the $x_i$’s round to $1$. Multiplying each such probability by its prior probability and summing, we get the total probability that the two roundings are the same:
\n\\[
\np(n) = \\frac{1}{2^n\\,n!}\\sum_{k=0}^n \\binom{n}{k}\\sum_{m=0}^k(-1)^m\\left[ \\binom{n+1}{m}-\\binom{n+1}{m-1}\\right](k+1-m)^n
\n\\]This can be further simplified by grouping $n^\\text{th}$ powers once again and observing that all odd terms cancel out. After quite a bit of algebra, we obtain the simplest expression possible, which is:<\/p>\n

$\\displaystyle
\np(n) = \\frac{1}{2^n\\, n!}\\sum _{k=0}^{\\left\\lfloor \\frac{n}{2}\\right\\rfloor } (-1)^k \\binom{n+1}{k} (n+1-2k)^n
\n$<\/span><\/p>\n

We can evaluate this for different values of $n$ and we obtain:
\n\\[
\n\\begin{array}{c|cccccccccc}
\nn & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\\\ \\hline
\np(n) & 1 & \\frac{3}{4} & \\frac{2}{3} & \\frac{115}{192} & \\frac{11}{20} & \\frac{5887}{11520} & \\frac{151}{315} & \\frac{259723}{573440} & \\frac{15619}{36288} & \\frac{381773117}{928972800}
\n\\end{array}
\n\\]<\/p>\n

The sequence $2^n \\, n!\\, p(n)$ is actually a well-known sequence. It is A261398 in OEIS<\/a> (the Online Encyclopedia of Integer Sequences), and according to OEIS it has no known closed-form formula and the one above is the simplest one available. Good enough for me!<\/p>\n

Visualization in 2D and beyond<\/h3>\n

We can visualize the probabilities for the case $n=2$ by coloring in the set of points $(x_1,x_2)$ for which the sum of the rounded values equals the rounded value of the sum. This yields:<\/p>\n

\"\"<\/p>\n

We can check the shaded region is $\\frac{3}{4}$ of the total area, as anticipated. We can do the same for $n=3$. This time, we plot the set of points $(x_1,x_2,x_3)$ and the probability is the shaded volume:<\/p>\n

\"\"<\/p>\n

Again, we can check the volume is $\\frac{2}{3}$. Unfortunately, we can’t visualize the case $n=4$, but we can try… This should be a 4D hypercube. In the same way that each slice of a 3D cube is a square, each slice of a 4D hypercube is a 3D cube. Here is an animation showing what happens as we vary $x_4 \\in [0,1]$ and we plot the cube resulting from the valid choices of $(x_1,x_2,x_3)$ as a function of $x_4$. The abrupt change occurs when $x_4=\\tfrac{1}{2}$ as this causes the sum of rounded values to jump by $1$.<\/p>\n

\"\"<\/p>\n

So now, if you can imagine, the probability we’re looking for is the “hyper-volume” of this 4D shape, which is given by integrating the volume above as we vary $x_4$, and as it turns out,
\n\\[
\np(4) = \\int_{0}^1 \\text{Volume}(x_4)\\,\\mathrm{d}x_4 = \\frac{115}{192}.
\n\\]<\/p>\n

Approximation<\/h3>\n

Recall that the solution we found above is given by
\n\\[
\np(n) = \\sum_{k=0}^n \\frac{1}{2^n}\\binom{n}{k}\\bigl( F(k+1)-F(k-1) \\bigr)
\n\\]where $F(x)$ is the CDF of the Irwin-Hall distribution. The formula we found for this is quite messy, so let’s see if we can approximate it.<\/p>\n

First, the Irwin-Hall distribution can be well-approximated<\/a> by a normal distribution. This makes sense, since summing a large number of identically distributed random variables tends to a normal distribution by the central limit theorem<\/a>. In this case, the limiting distribution has mean $\\mu=\\frac{n}{2}$ and variance $\\sigma^2=\\frac{n}{12}$. Therefore, we can approximate:
\n\\begin{align*}
\nF(k+1)-F(k-1) &\\approx 2F'(k) \\\\
\n&\\approx \\frac{2}{\\sqrt{2\\pi \\sigma^2}} \\exp\\biggl( -\\frac{(x-\\mu)^2}{2\\sigma^2} \\biggr) \\\\
\n&= \\frac{1}{\\sqrt{\\pi n\/24}}\\exp\\biggl( -\\frac{(k-\\tfrac{n}{2})^2}{n\/6} \\biggr)
\n\\end{align*}Next, the weighted binomial sum is actually a binomial distribution<\/a>, which we can also approximate using a normal distribution. In general, we have $B(n,p) \\approx \\mathcal{N}(\\mu,\\sigma^2)$, with $\\mu=np$ and $\\sigma^2=np(1-p)$. Therefore, if $g$ is any function, we can write the binomial sum as an expectation:
\n\\begin{align*}
\n\\sum_{k=0}^n \\frac{1}{2^n}\\binom{n}{k} g(k)
\n&= \\mathbb{E}_{k \\sim B(n,\\tfrac{1}{2})}\\bigl( g(k) \\bigr) \\\\
\n&\\approx \\mathbb{E}_{k \\sim \\mathcal{N}(\\tfrac{n}{2},\\tfrac{n}{4})}\\bigl( g(k) \\bigr) \\\\
\n&=\\frac{1}{\\sqrt{\\pi n\/2}} \\int_{-\\infty}^\\infty \\exp\\biggl(-\\frac{(k-\\tfrac{n}{2})^2}{n\/2} \\biggr)g(k)\\,\\mathrm{d}k
\n\\end{align*}Setting $g(k)=F(k+1)-F(k-1)$ and substituting our previous approximation, we find:
\n\\begin{align*}
\np(n) &\\approx \\frac{1}{\\sqrt{\\pi n\/2}}\\frac{1}{\\sqrt{\\pi n\/24}}\\int_{-\\infty}^\\infty \\exp\\biggl( -\\frac{(k-\\tfrac{n}{2})^2}{n\/6} \\biggr)\\exp\\biggl(-\\frac{(x-\\tfrac{n}{2})^2}{n\/2} \\biggr)\\,\\mathrm{d}k \\\\
\n&= \\frac{\\sqrt{48}}{\\pi n} \\int_{-\\infty}^\\infty \\exp\\biggl(-\\frac{(k-\\tfrac{n}{2})^2}{n\/8} \\biggr) \\,\\mathrm{d}k \\\\
\n&= \\frac{\\sqrt{48}}{\\pi n} \\sqrt{\\pi n\/8} \\\\
\n\\end{align*}Therefore, we have:<\/p>\n

$\\displaystyle
\np(n) \\approx \\sqrt{\\frac{6}{\\pi n}}
\n$<\/span><\/p>\n

To check our approximation, we can plot it together with the true values:<\/p>\n

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

Not bad! So in conclusion, we have an exact formula and an asymptotically exact approximation for the probability that
\n\\[
\n\\text{round}(x_1+\\cdots+x_n) = \\text{round}(x_1)+\\cdots+\\text{round}(x_n)
\n\\]They are given by:<\/p>\n

$\\displaystyle
\np(n) = \\frac{1}{2^n\\, n!}\\sum _{k=0}^{\\left\\lfloor \\frac{n}{2}\\right\\rfloor } (-1)^k \\binom{n+1}{k} (n+1-2k)^n
\n\\approx \\sqrt{\\frac{6}{\\pi n}}
\n$<\/span><\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

This week’s Fiddler is about rounding! Let $\\text{round}(x)$ be the value of $x$ rounded to the nearest integer. Suppose $x_1,\\dots,x_n$ are independent uniformly distributed random variables in $[0,1]$. Find the probability that \\[ \\text{round}(x_1+\\cdots+x_n) = \\text{round}(x_1)+\\cdots+\\text{round}(x_n) \\] My solution: [Show Solution] Let’s call the probability we seek $p(n)$. The values of the $x_i$ determine what … Continue reading “Round, round, get a round”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":4129,"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":[42],"tags":[9,43,8],"class_list":["post-4121","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-the-fiddler","tag-binomial","tag-fiddler","tag-probability"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/4121","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=4121"}],"version-history":[{"count":19,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/4121\/revisions"}],"predecessor-version":[{"id":4147,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/4121\/revisions\/4147"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/4129"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=4121"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=4121"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=4121"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}