Round, Round, Get a Round, I Get a Round

Pick two real numbers uniformly and independently from the interval $[0,1]$. You can round each to the nearest integer and then add, or add first and then round the sum. What is the probability the two procedures give the same answer?

The Fiddler, Zach Wissner-Gross, August 23, 2024(original post)

Solution

The two procedures can only disagree because rounding discards a little of each number, and the question is whether the discarded pieces, added together, are enough to push the sum across a half-integer boundary. So follow the discarded piece. For $x$ uniform on $[0,1]$, let its rounding error be $f = x - \operatorname{round}(x)$. When $x<\tfrac12$ the nearest integer is $0$ and $f=x\in[0,\tfrac12)$; when $x\ge\tfrac12$ it is $1$ and $f=x-1\in[-\tfrac12,0)$. Each half of $[0,1]$ maps uniformly onto one half of $[-\tfrac12,\tfrac12)$, so $f$ is itself uniform on $[-\tfrac12,\tfrac12)$.

Write $a=\operatorname{round}(x)$ and $b=\operatorname{round}(y)$, both integers. Then $x+y = a+b+(f_x+f_y)$, and since $a+b$ is an integer, $\operatorname{round}(x+y)=a+b+\operatorname{round}(f_x+f_y)$. Rounding first and adding gives $a+b$; so the two agree exactly when $\operatorname{round}(f_x+f_y)=0$, that is when the combined error satisfies $$f_x+f_y\in\left[-\tfrac12,\tfrac12\right).$$ With $f_x,f_y$ independent and uniform on $[-\tfrac12,\tfrac12)$, their sum has a triangular density $p(s)=1-|s|$ on $[-1,1]$, peaking at $s=0$. The probability it lands in the central band $[-\tfrac12,\tfrac12]$ is one minus the two tails, and each tail is $$\int_{1/2}^{1}(1-s)\,\mathrm ds=\tfrac18,$$ so the answer is $1-2\cdot\tfrac18$: $$\boxed{\tfrac34=75\%.}$$

The computation

A closed form this short invites a direct check. Drawing ten million pairs and comparing the two procedures outright agrees with $\tfrac34$ to three decimals.

import numpy as np
rng = np.random.default_rng(0); n = 10_000_000
x, y = rng.random(n), rng.random(n)
print((np.rint(x) + np.rint(y) == np.rint(x + y)).mean())   # ~0.75

Extra Credit

Now pick $N$ numbers uniformly from $[0,1]$. What is the probability that rounding each and adding equals rounding the sum?

Solution

The reduction survives unchanged. With $a_i=\operatorname{round}(x_i)$ integers and errors $f_i=x_i-a_i$ each uniform on $[-\tfrac12,\tfrac12)$, $$\operatorname{round}(x_1+\dots+x_N)=a_1+\dots+a_N+\operatorname{round}(f_1+\dots+f_N),$$ so the two procedures agree exactly when the total error $f_1+\dots+f_N$ lies in $[-\tfrac12,\tfrac12)$. Shift each error by $\tfrac12$ to make it a standard uniform, $g_i=f_i+\tfrac12\sim U[0,1]$; then $g_1+\dots+g_N$ follows the Irwin–Hall distribution, the law of a sum of $N$ independent uniforms, whose cumulative distribution function is $$F_N(t)=\frac1{N!}\sum_{k=0}^{\lfloor t\rfloor}(-1)^k\binom Nk (t-k)^N.$$ The condition $f_1+\dots+f_N\in[-\tfrac12,\tfrac12)$ becomes $g_1+\dots+g_N\in\bigl[\tfrac{N-1}2,\tfrac{N+1}2\bigr)$, so the probability is the central slab of that distribution, $$\boxed{P_N=F_N\!\left(\tfrac{N+1}2\right)-F_N\!\left(\tfrac{N-1}2\right).}$$ This gives $P_2=\tfrac34$, $P_3=\tfrac23$, $P_4=\tfrac{115}{192}$, $P_5=\tfrac{11}{20}$, $P_6=\tfrac{5887}{11520}$, and the value falls slowly towards $0$: more numbers mean more accumulated error, and the chance it all stays within half a unit shrinks.

The computation

Rather than evaluate the formula just derived, run the experiment itself for each $N$: draw $N$ uniforms, round each and sum, sum and round, and compare. The measured frequencies match $P_2=\tfrac34,\,P_3=\tfrac23,\,P_4=\tfrac{115}{192},\,P_5=\tfrac{11}{20},\,P_6=\tfrac{5887}{11520}$ to sampling precision, an independent check on the Irwin–Hall slab.

import numpy as np
rng = np.random.default_rng(0); n = 5_000_000
for N in range(2, 7):
    X = rng.random((n, N))
    agree = (np.rint(X).sum(1) == np.rint(X.sum(1))).mean()
    print(N, round(agree, 4))    # ~0.75, 0.6667, 0.599, 0.55, 0.511