Suppose $n$ $s$-sided (and fair) dice and are rolled, and consider the most likely value their total will take. Is there a simple / easy to state upper-bound on the probability that this total is rolled?
I know you can bound this accurately using generating functions, but to use in the proof I'm working on requires summing over this probability for a range of (large) $n$ values, which gets too complicated. I imagine it can also be approximated it using some distribution, but it's for a crypto proof so I really need an upper bound. I'm crudely upper bounding this with $1/s$ at the moment for all $n$. This follows by induction on n. Letting $X_i$ denote the distribution of the $i$th dice roll
For $n = 1, Prob[X_1 = z] = 1/s$ for all $z \in [1, s]$, so the base case holds.
Assume true for $n=k$, so $max_{z \in [k, ks]} Prob[\sum_{i = 1}^k {X_i} = z] \leq 1/s$.
Then for $n = k+1$, and each $z \in [k+1, (k+1)s]$:
$Prob[\sum_{i = 1}^{k+1} {X_i}=z$]
$ = \sum_{h \in [k, ks]} Prob[X_{k+1} = z - \sum_{i = 1}^k X_i | \sum_{i = 1}^k X_i = h]Prob[\sum_{i = 1}^k X_i = h]$
$\leq \sum_{h \in [z - s, z-1]}1/s^2 = 1/s$,
where the final inequality follows since by the induction hypothesis $Prob[\sum_{i = 1}^k X_i = h]\leq 1/s$ and $Prob[X_{k+1} = z - h] = 1/s$ if $h \in[z - s, z-1]$ and $0$ otherwise.
I was wondering if there is any tighter (for large $n$) but still simple upper bound?
A good approximation for large $n$ is to note (rescaled) convergence in distribution to a normal distribution where the variance of the sum is $n\frac{s^2-1}{12}$ and so the probability of a value near the expectation of $n\frac{s+1}{2}$ will be about $\frac{1}{2\pi \sigma^2}=\sqrt{\frac{6}{\pi n(s^2-1)}}$.
If you want to simplify this and remove the $-1$, then the worst case will be when $s=2$ in which case $s^2-1 = \frac34 s^2$ making the approximation $\sqrt{\frac{8}{\pi}}\frac1{s\sqrt n}$. Since $\sqrt{\frac{8}{\pi}} \approx 1.596$, a further simplification on the conservative side is $\dfrac{1.6}{s \sqrt n}$
For $s=2$ this is an very good upper bound as $n$ increases for the true value of $\frac{n \choose \lfloor n/2 \rfloor}{2^n}$: for example with $s=2$ and $n=100$ it gives $0.08$ when the true probability of the mode is about $0.079589$. For larger $s$ it is only a small multiplicative amount too high: for example with $s=6$ and $n=36$ it gives about $0.044444$ for the probability of the mode when the true value is about $0.038761$.