6
$\begingroup$

For $1\leq i\leq n$ let $X_i$ be independent random variables, and let each $X_i$ be the uniform distribution on the set ${0,1,2,\dots,m}$ so that $X_i$ is like an $m+1$ sided die. Let $$Y=\frac{1}{n}\sum_{i=1}^n \frac{1}{m} X_i,$$ so that $\mathbb{E}(Y)=\frac{1}{2}$. I am interested in the tails of this distribution, that is the size of $$\Pr\left( Y \geq k\right)$$ where $\frac{1}{2}< k\leq 1$ is a constant.

In the case where $m=1$, we are looking at the binomial distribution, and $$\Pr\left( Y \geq k\right)= \frac{1}{2^n}\sum_{i=0}^{(1-k) n} \binom{n}{i}$$ and we can bound this above by $(1-k)n \binom{n}{(1-k)n}$ and below by $\binom{n}{(1-k)n}$ which yields $$\Pr\left( Y \geq k\right)\approx \frac{1}{2^n} e^{n H(k)}$$ where $H(x)=-\left(x\log x+(1-x)\log (1-x)\right)$ is the entropy function. (I use approx liberally)

What kind of similar bounds do we have on the tails of this distribution when $m\geq 2$? I am looking to use the explicit multinomial properties to get something stronger than what you would get using Chernoff of Hoeffding.

  • 0
    Something is missing in your m=1 formula. The right hand side is an integer >1. The formula has to involve the parameter p=P(Xi=1)2012-06-15
  • 0
    @MichaelChernick: I have edited. There should of been a factor of $2^{-n}$ in front. Since $p=1-p$, get exactly $2^{-n}$ in each factor.2012-06-15
  • 0
    I think that maybe a Tex symbol is causing the 1/2$^n$ term to not appear in your edited question. Never mind. I see it is there now.2012-06-15
  • 0
    Chernoff yields the exact rate of the exponential convergence to zero. What do you call *stronger* than that?2012-06-15
  • 0
    @Did: Could you elaborate on what you mean by this? This could be exactly what I am looking for. (Also, I may not be using the correct version of Chernoff's inequality)2012-06-15
  • 0
    See Edit. $ $ $ $2012-06-23
  • 0
    @did: Thanks, that answers things.2012-10-13

2 Answers 2

3

Consider some i.i.d. random variables $\xi$ and $(\xi_n)_{n\geqslant1}$ with mean $\mathrm E(\xi)=0$ and finite exponential moment $\mathrm E(\mathrm e^{t|\xi|})$ for every $t$. Then, for every $x\gt0$, there exists $I(x)\gt0$ such that, when $n\to\infty$, $$ \mathrm P(\xi_1+\cdots+\xi_n\geqslant nx)=\mathrm e^{-nI(x)+o(n)}. $$ Furthermore, optimizing Chernoff exponential upper bound yields the exact value of the exponent $I(x)$. Namely, recall that, for every nonnegative $t$, $$ \mathrm P(\xi_1+\cdots+\xi_n\geqslant nx)\leqslant\left(\mathrm e^{-tx}\mathrm E(\mathrm e^{t\xi})\right)^n=\mathrm e^{-nI(t,x)}, $$ where $$ I(t,x)=tx-\log\mathrm E(\mathrm e^{t\xi}), $$ and it happens that $$ I(x)=\sup\limits_{t\geqslant0}I(t,x). $$ Note that $\mathrm E(\xi)=0$ hence $\mathrm E(\mathrm e^{t\xi})=1+o(t)$ when $t\to0$ and $I(t,x)=tx+o(t)$. In particular, $I(t,x)\gt0$ for $t\gt0$ small enough, hence $I(x)\gt0$ and the upper bound above is not trivial.

As stated above, this upper bound also provides the exact behaviour, in the exponential scale, of the probability of the large deviations event considered, that is, $$ \lim\limits_{n\to\infty}\frac1n\log\mathrm P(\xi_1+\cdots+\xi_n\geqslant nx)=-I(x). $$ In your setting, one considers $\xi=\frac1mX-\frac12$ and $x=k-\frac12$ hence $0\lt x\lt\frac12$. Note finally that, in general, $I(x)=I(t_x,x)$ where $t_x$ solves the equation $\partial_tI(t,x)=0$, that is, $$ x\mathrm E(\mathrm e^{t\xi})=\mathrm E(\xi\mathrm e^{t\xi}). $$

  • 0
    How can I evaluate $I(x)$ explicitly in my case?2012-06-30
  • 0
    You know the distribution of $\xi=\frac1mX-\frac12$ with $X$ uniform on $\{0,1,\ldots,m\}$ hence you know $\mathrm E(\mathrm e^{t\xi})$ and $\mathrm E(\mathrm e^{t\xi})$ and $I(t,x)$ hence you know $I(x)$.2012-06-30
  • 0
    In what I did above in the question with binomial coefficients, when $m=1$, I found that $I(x)=\log 2 - H(x)$ where $H$ is the entropy function. How can I evaluate the expectations above and find $I(x)$ when $m$ is different? I conjecture that it is like $\log(m+1) -H(x)$ with the same entropy function $H$, but I am not sure.2012-06-30
  • 0
    There is no reason to believe $I(x)$ has this form when $m\geqslant2$ and in fact, tedious computations show that it has not when $m=2$.2012-06-30
  • 0
    Eric: Thanks for the bounty.2013-09-11
3

The variance of $X_i$ is $\frac{m(m+2)}{12}$ so of $Y$ is $\frac{m+2}{12mn}$. The central limit theorem leads to a normal approximation for moderate to high $n$

$$\Pr\left( Y \geq k\right) \approx 1 - \Phi\left((2k-1){\sqrt{\frac{3mn}{m+2}}}\right)$$

Stein's method and other similar methods can help calculate the rates of convergence