Simulate coin tossing by die tossing

Question

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)

Answer 1

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}$