# Simulate coin tossing by die tossing

On the one hand we toss $n$ times a fair coin, and we sum the outcomes (+1 for heads, -1 for tails). Let $f:\mathbb{N}\to\mathbb{R}$ describe the probability distribution of the outcome.

On the other hand we toss $m$ times a fair die with $2k$ sides, and we sum the outcomes (to avoid parity issues, assume outcomes in $\{\pm 1,\pm 3,\dots,\pm (2k-3),\pm (2k-1)\}$). Let $g:\mathbb{N}\to\mathbb{R}$ describe the probability distribution of the outcome.

What can we say about the total variation distance between both experiments (i.e., 1-distance between $f$ and $g$), as a function of $n$, $m$ and $k$?

BACKGROUND: I am interested in this question since simulations indicate that throwing $m$ times a die of $O(\sqrt{n/m})$ sides allows for $f$ and $g$ to get $1/\sqrt{m}$-close in TV distance (for $n\gg m$). I.e., we could approximate (up to constant distance) an $n$-fold coin toss experiment by a constant number of tosses of a $O(\sqrt{n})$ sided die.

It is easy to find $m$ and $k$ such that $f$ and $g$ converge weakly. And the Berry-Esseen theorem shows that the cumulative probability distributions converge pointwise as $O(1/\sqrt{m})$, if we choose $\tau\in O(\sqrt{n/m})$. This is however not sufficient to prove anything about the TV distance.

I have also tried to work with local limit theorems, which show that the probability distributions converge pointwise as $O(1/m)$ if $\tau\in O(\sqrt{n/m})$. But seeing that the support of the distributions will be $\gg \sqrt{m}$, this also seems insufficient to bound TV distance.

Any other ideas?

(This question is a duplicate from a question on math.stackexchange: link)

• I think in this case the ratio $g/f$ will have, at most, a certain number (say $M$, not depending on $n,m,k$) of intervals of monotonicity and hence $g-f$ will have about the same number of intervals of constant sign. Thus, the TV distance will be bounded by about $Md_{Ko}$, where $d_{Ko}$ is the corresponding Kolmogorov distance. Feb 15, 2018 at 17:13
• Hi, thanks for the comment. Indeed, if $g-f$ has a constant number of sign changes (independent of $n,m,k$), then one could also apply the Berry-Esseen theorem on the cumulative probability distributions to bound the TV distance. Unfortunately, I have not succeeded in proving this, and have no particular idea on how to prove this. I did run simulations that do indicate that the number of sign changes is fixed. Feb 15, 2018 at 17:18
• There is something I don't understand: cumulative sums for $n$ coins and for $m$ $k$-sided dice will be approximately Gaussian, respectively $N(n/2,n/4)$ and $N(m(k-1)/2,m(k^2-1)/12)$. There is no way to match both expectation and variance unless $k=2$, so what you ask seems hopeless ... Feb 16, 2018 at 8:46
• Hi Guillaume, thank you for the comment, you are correct. I have modified the setting such that the mean of both experiments is zero, allowing enough freedom to choose the variance of both limit Gaussians to be equal. Feb 16, 2018 at 10:04
• There is something called Tusnady's lemma (see e.g. a paper with that name by Massart) which says extremely precise estimate on how well sums of Bernoulli are approximately Gaussian. This might be relevant (assuming you have a similar lemma for dice, which might be painful to prove). Feb 16, 2018 at 12:23

I think the best way is to use the $L^2$ norm, because then exact calculation can be made in the Fourier space. $$\|f^{\otimes n}-g^{\otimes m} \|^2_{L^2(\mathbb{Z})}=\|\hat{f}^n-\hat{g}^m \|^2_{L^2([0,2\pi])}$$ For a fair coin $\hat{f}(v)=\frac{e^{iv}+e^{-iv}}{2}=\cos(v)$.
For a fair dice $\hat{g}(v)=\frac{\sum_{s=-k}^{k-1} e^{i (2s+1)v}}{2k}=\frac{\sin(2kv)}{2k\sin(v)}$
We will compare only function with similar variance. We assume $n=\frac{m((2k)^2-1)}{3}$ We note then $\hat{f_k}=\hat{f}^{((2k)^2-1)/3}$. We have to calculate then : $$I_m =\int_0^{\pi }|\hat{f_k}(v)^m-\hat{g}(v)^m|^2 dv$$ Because both function are strictly smaller than $1$ on $[\epsilon,\pi -\epsilon]$ the integral on this set will be exponentially small. We can do then a Taylor expansion around 0. Because $f_k$ and $g$ have same variance there exists $a_4$ and $b_4$ such that $$f_k(v)=(1-\frac{1}{2 \sigma^2})(1+a_4v^4+o(v^4))$$ and $$g(v)=(1-\frac{1}{2 \sigma^2})(1+b_4v^4+o(v^4))$$ $$I_m =\int_{-\epsilon}^{\epsilon }|1-\frac{v^2}{2 \sigma^2}|^m |(1+a_4 v^4)^m-(1+b_4 v^4)^m|^2 dv$$ and therefore for large $m$. $$I_m \approx \int_\mathbb{R}e^{-m\frac{v^2}{\sigma^2}} |m(a_4-b_4) v^4|^2 dv \approx m^{-\frac{5}{2}}$$ And one can conclude with $\|h\|_{L^1}\leq \|h\|_{L^2} \sqrt{m}$
• Hi Raphael, thank you for the answer. I think that this approach might work in the regime where $k$ is fixed, and $m$ (and $n$) increasing. However, I do not think that it suffices in the regime where $n$ is increasing but $m$ is left constant (and so $k~\sqrt{n}$) (see background). Some reasons for this might be: (i) the size of the support of $h=f^{\ast n}-g^{\ast m}$ would be $2n\gg m$, so I think that the bound on L_1 as a function of L_2 would not work (ii) one would have to show that the coefficients of the Taylor expansions of $f_k$ and $g$ do not grow too badly with $n$ and $m$ Feb 16, 2018 at 16:33
• Hi smapers. I didn't see the background. Maybe for $m$ fixed, the limite of $k*I_m$ can be calculated analytically as $f_k$ converge to the gaussian and $g$ to the cardinal sine function. Feb 17, 2018 at 17:22