# 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. – Iosif Pinelis Feb 15 '18 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. – smapers Feb 15 '18 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 ... – Guillaume Aubrun Feb 16 '18 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. – smapers Feb 16 '18 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). – Guillaume Aubrun Feb 16 '18 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$ – smapers Feb 16 '18 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. – RaphaelB4 Feb 17 '18 at 17:22