11
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Iosif Pinelis Feb 15 '18 at 17:13
  • $\begingroup$ 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. $\endgroup$ – smapers Feb 15 '18 at 17:18
  • $\begingroup$ 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 ... $\endgroup$ – Guillaume Aubrun Feb 16 '18 at 8:46
  • $\begingroup$ 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. $\endgroup$ – smapers Feb 16 '18 at 10:04
  • $\begingroup$ 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). $\endgroup$ – Guillaume Aubrun Feb 16 '18 at 12:23
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$ $\endgroup$ – smapers Feb 16 '18 at 16:33
  • $\begingroup$ 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. $\endgroup$ – RaphaelB4 Feb 17 '18 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.