# Mixture of Discrete Binomial Distributions

Let $B\left(p,N\right)$ be a Binomial distribution with parameters $p$ and $N$. We define a Mixture of Discrete Binomial Distributions by $\left\{ \left(B\left(p_{i},N\right),\alpha_{i}\right)\right\} _{i=1}^{N+1}$, for a fixed $N\in\mathbb{N}$.

Input: $\left\{ \left(B\left(p_{i},N\right),\alpha_{i}\right)\right\} _{i=1}^{N+1}$ such that

• $p_{i}\in\left(0,1\right)$ and $p_{i}\neq p_{j}$ for every $i\neq j \in [1:N+1]$,

• $\sum_{i=1}^{N+1}\alpha_{i}=1$ and $\alpha_{i}\in\left(0,1\right)$ for every $i \in [1:N+1]$.

Output: $\left\{ \gamma_{N,p,\alpha}\left(j\right)\right\} _{j=0}^{N}$ such that $$\gamma_{N,p,\alpha}\left(j\right)=\sum_{i=1}^{N+1}\alpha_{i}\cdot{N \choose j}p_{i}^{N-j}\left(1-p_{i}\right)^{j}.$$

Question 1: For a fixed $N\in\mathbb{N}$, what family of functions can be approximated (*) by the Mixture of Discrete Binomial Distributions $$\mathcal{S}_{N}=\left\{ \gamma_{N,p,\alpha}\in\left(0,1\right)^{N+1}\,|\,\left\langle 1,\alpha\right\rangle =1,\:\alpha,p\in\left(0,1\right)^{N+1}\:\text{and}\: p_{i}\neq p_{j}\:\forall i\neq j\right\}$$

(*) Let $\left[k:N-k\right]\subset\left[0:N\right]$. The desired approximation is in terms of the $L_\infty$ norm $$\left\Vert \left(\gamma_{N,p,\alpha}\right)_{k:N-k}-\left(e^{-x}\right)_{k:N-k}\right\Vert _{\infty}\leq\epsilon.$$

Example: The Uniform Distribution belongs to $\mathcal{S}_N$, and it corresponds to the case when $\alpha=\frac{1}{N+1}\mathbb{1}$ and $p_{i}=\frac{i}{N+2}$.

Question 2: Does $\mathcal{S}_N$ approximate the exponential family of functions $\{e^{-cx} | c>0\}$?

The representational power of mixture of discrete Binomial distributions is analyzed by Gorav Jindal and Pavel Kolev (c.f. http://arxiv.org/pdf/1507.07497v1.pdf) and it is summarized in the following statement.

Theorem. Let $N\in\mathbb{N}$ be a number, $\epsilon\in(0,1)$ parameter, $I=[0,1]$ interval and $w(x)$ probability density function that is four times differentiable. Suppose the real numbers $\delta,\mu,\eta\in(0,1)$ satisfy:

1) $\max_{x\in I}|w^{\prime\prime}(x)|\leq\frac{8}{3}\delta\cdot N^{2+\eta}$,$\qquad$ 2) $\max_{x\in I}|w^{\prime}(x)|\leq\frac{2}{3}\delta\cdot N^{1+\eta}$,$\qquad$

3) $\max_{x\in I}|w(x)|\leq\frac{2}{3}\delta\cdot N^{\eta}$,

4) $\max_{x\in I}|b_{1}(x)|\leq\frac{1}{2}\mu\cdot N$,$\qquad$5) $\max_{x\in I}|b_{2}(x)|\leq\frac{1}{2}\mu\cdot N^{2}$,

where the functions $b_1,b_2$ are defined by

$b_{1}(x)=\frac{1}{w(x)}[-w(x)+(1-2x)w^{\prime}(x)+\frac{1}{2}x(1-x)w^{\prime\prime}(x)]$ and $b_{2}(x)=\frac{1}{w(x)}[w(x)-3(1-2x)w^{\prime}(x)+(1-6x+6x^{2})w^{\prime\prime}(x)+\frac{5}{6}x(1-x)(1-2x)w^{\prime\prime\prime}(x)+\frac{1}{8}x^{2}(1-x)^{2}w^{\prime\mathrm{v}}(x)].$

Then for any $T\geq\Omega(N^{1+\eta}\sqrt{\delta/\epsilon})$ and all $k\in[3:N-3]$ it holds that $$\left|(1+\eta_{k})\frac{w(k/N)}{N}-\frac{1}{T}\sum_{j=1}^{T}F_{k}\left(\frac{j}{T+1}\right)\right|\leq\frac{\epsilon}{N},\quad\text{where}\quad\eta_{k}\in[-\mu,\mu],$$ where the function $F_{k}(x)\triangleq w(x)\cdot B_{N,k}(x)$ and $B_{N,k}(x)={N \choose k}x^{k}(1-x)^{N-k}$ is Binomial coefficient.