Large deviations for discrete uniform distribution

Question

(Not sure if this belongs on stack-exchange or overflow; let me know if I should switch it).

Given a sum of $n$ IID random variables $\{X_i\}_{i=1}^n$, each uniform on the integers $0,1,...,r$ for some (fixed) $r$, I would like to estimate $$ \mathbb{P}[\sum_{i=1}^n X_i = k]$$ for $k$ of order $n$. If $k$ happened to be the mean of the sum, then I know how to handle this via the Local Central Limit Theorem. But, when $k$ is far from the mean of the sum, the error term in the LCLT is larger than the first-order term.

This seems like it should be a very standard exercise in large-deviations, but I am not very familiar with that field and am having trouble finding the right tool. Could someone help point me to a theorem (and ideally an example calculation) that might help?

Answer 1

The answer to your question is contained in the following local limit theorem for large deviations, due to V. Petrov, Theorem 6:

Suppose that $X,X_1,X_2,\dots$ are iid random variables such that $X$ only take values in the set $L:=\{a+kH\colon k\in\mathbb Z\}$ for some real $a$ and some real $H>0$, and suppose that the step $H$ is maximal with this property. Let $S_n:=X_1+\dots+X_n$, $R(h):=Ee^{hX}<\infty$ for all real $h>0$, $m(h):=(\ln R)'(h)$, $\sigma(h):=\sqrt{m'(h)}>0$, and $A_0:=\lim_{h\to\infty} m(h)=\sup_{h>0} m(h)$. Then $$P(S_n=nx)=\frac H{\sigma(h_x)\sqrt{2\pi n}}\,\exp\{n\ln R(h_x)-nh_x x\}(1+O(1/n)), $$ where $x$ varies arbitrarily in any compact subinterval of the interval $(EX,A_0)$ so that $nx\in L$, and $h_x$ is the only root $h$ of the equation $m(h)=x$.

In your case, $a=0$, $H=1$, $$R(h)=\frac{e^{(r+1)h}-1}{(r+1)(e^h-1)}, $$ $EX=r/2$, and $A_0=r$.

In the particular case when $r=1$, we have $R(h)=(e^h+1)/2$, $m(h)=1/(1+e^{-h})$, $\sigma^2(h)=e^{-h}/(1+e^{-h})^2$, $h_x=\ln\frac x{1-x}$, and hence $$P(S_n=nx)=\frac1{\sqrt{2\pi nx(1-x)}}\,J(x)^n(1+O(1/n)), $$ where $x$ varies arbitrarily in any compact subinterval of the interval $(1/2,1)$ so that $nx$ is an integer, and $$J(x):=\tfrac12\,x^{-x}(1-x)^{x-1}. $$ Here is the graph of $J$:

Answer 2

As Iosif Pinelis mentioned this is quite standard in large deviations theory so let me explain a bit the idea of the theorem he quote.

Let $Y$ a random variable defined as $\mathbb{P}(Y=y)=\frac{1}{Z(\alpha)}e^{-\alpha y}$ for $y=0,\cdots,r$ with $Z(\alpha) = \sum_y e^{-\alpha y}$ and choose $\alpha$ such that $\mathbb{E}(Y)=\frac{k}{n}$. Let $(Y_i)_{i\leq n}$ $n$ independant copy of $Y$. Then $$\mathbb{P}[\sum_i Y_i =k]$$ can be estimated with the CLT. Moreover we have $$\mathbb{P}[X_1=y_1,X_2=y_2,\cdots,X_n=y_n]=\mathbb{P}[Y_1=y_1,Y_2=y_2,\cdots,Y_n=y_n]\frac{Z(\alpha)^n e^{\alpha \sum_i y_i}}{(r+1)^n}$$ and then $$\mathbb{P}[\sum_i X_i =k] = \Big(\frac{Z(\alpha) }{r+1}\Big)^n e^{\alpha k} \mathbb{P}[\sum_i Y_i =k] $$ which solve your problem.

In order to find $\alpha$ we use that $$\mathbb{E}[Y]=\frac{1}{Z(\alpha)}\sum_{y\leq r}ye^{-\alpha y}=-\frac{d}{d\alpha} \log(Z(\alpha))$$ which gives an easy equation in $\alpha$. Similarly the variance of $Y$ is calculated with the second derivative of $Z(\alpha)$

[To translate with Iosif Pinelis answer : $\alpha=h$, $Z(\alpha)=(r+1)\mathbb{E}[e^{-\alpha X}]=(r+1)R(-\alpha)$]

Answer 3

On page 329 of The Probabilistic Method (4th ed) by Alon and Spencer the following general result is proved.

For all $C>0$ and $\epsilon >0,$ there exists $\delta>0$ such that the following holds:

Let $X_i$ be arbitrary independent random variables with mean $0$, $|X_i|\leq C,$ and variance $\sigma_i^2.$ Let $X=\sum_i X_i,$ and $\sigma^2=\sum_i \sigma_i^2$. Then for $0<a\leq \delta \sigma,$ $$ \mathbb{P}[X>a\sigma]< \exp(-a^2(1-\epsilon)/2], $$ where $\delta$ must be chosen to satisfy $e^{r\delta}\leq 1+\epsilon.$

There may be better results for your specific case, but I think this result will give a nontrivial bound (at least on the right tail) by applying the bound to $X-\mathbb{E}(X)$