Bounding the tail of sum of discrete distributions (via sub-gaussianity)

I have the following problem: we have a sequence of random variables $$Z_1, ..., Z_n$$ which are summed up; let's denote $$X$$ to be their sum. We observe a number $$\epsilon$$ that is sampled from $$X$$ and we wish to somehow describe/bound the probability $$P(X \geq \epsilon)$$; that is, we want to compute the extremeness (quantile) of $$\epsilon$$. We are interested only in the right tail of $$X$$.

Each of $$Z_i$$ is a discrete distribution with probabilities $$p_i=[p_1,...p_k], k \in N$$ and corresponding values given as $$x=[x_1,...,x_k]=[-\log(p_1),...-\log(p_k)]$$ (we assume p > 0). The values of $$p_i$$ (which also give us the $$x_i$$) are known. The distributions $$Z_1,...Z_n$$ are independent (but not necessary identically distributed).

Since we know all $$p_i$$, we can compute the means and variances of $$Z_i$$. (The mean of $$Z_i$$ happens to be the entropy of $$Z_i$$, by the way how we defined the values $$x_i$$.) By summing the means and variances of $$Z_i$$, we get the mean $$\mu$$ and variance $$\sigma^2$$ of $$X$$.

To bound the tail probability of $$X$$, we can use Chebyshev inequality: we have $$P(X \geq \epsilon) \leq \frac{\sigma^2}{(\epsilon - \mu)^2}$$. However, the bound is very loose and I am looking for a better one.
Also, in the limit for $$n \to \infty$$, the $$X$$ will be normally distributed by CLT; however, I will mostly deal with $$n$$ between 10-30, where the normal approximation is not so good.

For these reasons, I am trying to utilize the subgaussianity of $$Z_i$$. We say that random variable $$Z$$ is b-subgaussian, if $$\mathbb{E}\left[ \exp\lambda (Z - \mathbb{E}[Z])\right] \leq \exp \left( \frac{\lambda^2b^2}{2} \right) \quad \forall \lambda \in \mathbb{R}$$ The subgaussianity is preserved through summation (if $$Z_1$$ is $$b_1$$-subgaussian and $$Z_2$$ is $$b_2$$-subgaussian, then $$Z_1 + Z_2$$ is $$\sqrt{b_1^2 + b_2^2}$$ subgaussian.) Therefore, if we compute $$b_i,...b_n$$ such that $$Z_1,...,Z_n$$ are $$b_i,...b_n$$-subgaussian, we can obtain $$b$$ such that $$X$$ is b-subgaussian. The subgaussian property gives us a much stronger bound on the tail of $$X$$ compared to the Chebyshev inequality: if $$X$$ is $$b-$$subgaussian, then $$P(X \geq \epsilon) \leq \exp \left( \frac{-(\epsilon-\mu)^2}{2b^2}\right)$$ That is, lower values of $$b$$ are better (give us tighter bound).
Any distribution with values bounded by interval $$[c,d]$$ is $$b-$$subgaussian for $$b \geq \frac{(d-c)^2}{4}$$ by Hoeffding's lemma. However, this bound is again too lose for my usecase.

That is, I would like to ask:

• Is there some algorithm, that given the discrete probability distribution $$p=[p_1,...p_k]$$ and corresponding values $$x$$ (in my case, I have $$x=-log(p)$$) computes $$b$$ such that the distribution is $$b-$$subgaussian for reasonably low $$b$$?
• Alternatively, is there some algorithm, that given my values of $$p$$ and $$x$$ and given some $$b$$ decides whether the distribution is $$b-$$subgaussian? (I can then use it to find the lowest $$b$$ by binary search).
• After all, I try to bound the tail probability of $$X$$ - maybe the subgaussianity approach is not a good idea? Are there any better / reasonable ways how to obtain a tight bound?

P.S. Another way how to estimate the probability in the tail is by Monte-Carlo sampling from $$X$$ (which I can, since I know all $$Z_i$$). However, this will be computationally too expensive for me. In my use case, I know all possible values of $$Z$$ in advance (there may be about 100 possible values of vectors $$p$$, and I know them in advance) and I can precompute even computationally expensive stuff. Then, I am given the actual sequence of $$Z$$s (the sequence will be about 10-30 of $$Z$$s selected from the possible values of $$Z$$ that were given in advance), and I need to compute the bound on the tail of $$X$$ as fast as possible.

References:

I got the introduction to subgaussianity from Lattimore, Tor, and Csaba Szepesvári. Bandit algorithms (2020), chapter 5. The book is available here.

Another resourse I went through is this lecture notes (it mention the usage Hoeffidng's lemma).

edit: this material states an equivalent condition for subgaussianity, that can be checked algorithmically (Theorem 2.1, page 6 of the .pdf). I am currently trying to understand the proof and somehow construct an algorithm that decide if distribution is $$\sigma$$-gaussian for given $$\sigma$$.

• How will you use this bound? That seems more relevant than all the sub-Gaussian stuff. Aug 31 '21 at 7:21
• It's intended to be a part of some anomaly detection pipeline. We are detecting anomalies in some sequential data; the quantile of the numer $\epsilon$ tells us how much anomalous is given observation. I.e. the quantile is basicly the final result / our point of interest. (And since we can't compute the quantile exactly, we are trying to at least provide bound on it, hence the tail probability bound.) Aug 31 '21 at 10:02
• I am downvoting this for the combination of poor notation (the $p_i$ should be replaced by $p_{ij}$, to show how they relate to the variables $X_i$), unjustified focus on sub-gaussianity, and lack of information about the distributions of the $X_i$ (the post does not even provide an example showing a typical number of and minimum value of the $p_{ij}$). Sep 1 '21 at 6:42
• @MattF. I agree with your note that the values of $p_i$ should be double indexed. However, the later two objections seem quite absurd to me: I didn't state any examples of $Z_i$ since at this point, I don't have much of the relevant data yet and I am just preparing the pipeline. The same holds for the properties of $p_{ij}$: there are no constraint on their values beside the stated positivity. Regarding the focus on subgaussianity - why is that an issue? The Chebyshev inequality and subgaussianity were simply the only two options how to bound a tail of a distribution I was aware of. Sep 1 '21 at 13:14
• “I wanted X (a bound) and the only way I knew to get it was Y (subgaussianity), so I asked about Y” is a classic XY problem, “which leads to enormous amounts of wasted time and energy, both on the part of people asking for help, and on the part of those providing help.” See: meta.stackexchange.com/questions/66377/what-is-the-xy-problem Sep 2 '21 at 2:16

This answer aims at your first question: how to obtain a reasonably low value of $$b$$ given $$p$$. Ideally, this actually provides the best value of $$b$$.

Denote $$\mathbb{E}[Z] = H(Z)$$. On the left side of the inequality for b-subgaussian definition, we have

\begin{align} \mathbb{E}\left[e^{\lambda(Z-H(Z))}\right] &= e^{-\lambda H(Z)}\left(\sum_{i=1}^k p_ie^{-\lambda \log(p_i)} \right)\\ &= e^{-\lambda H(Z)}\left(\sum_{i=1}^k p_i^{1-\lambda} \right)\\ &= e^{-\lambda H(Z)}\phi(\lambda) \quad, \end{align}

where $$\phi(\lambda) = \sum_{i=1}^k p_i^{1-\lambda}$$. Now notice that

$$e^{-\lambda H(Z)}\phi(\lambda) \leq e^{\frac{\lambda^2b^2}{2}}, \,\forall \lambda \, \in \, \mathbb{R} \iff -\lambda H(Z) + \log(\phi(\lambda)) \leq \frac{\lambda^2b^2}{2}, \, \forall \lambda \, \in \, \mathbb{R} \quad.$$

For $$\lambda = 0$$, the equation is trivially satisfied. For $$\lambda \neq 0$$, define

$$f(\lambda) = \frac{-\lambda H(Z) + \log(\phi(\lambda))}{\lambda^2} \quad.$$ Note $$f$$ is smooth, $$\underset{\lambda \rightarrow +\infty}{\lim} f(\lambda) = \underset{\lambda \rightarrow -\infty}{\lim} f(\lambda) = 0$$. Moreover, you can actually show that (use L'Hôpital twice) $$\underset{\lambda \rightarrow 0}{\lim} f(\lambda)$$ exists and is well defined. Therefore, this function is bounded above. Let $$M = \underset{\lambda \, \in \, \mathbb{R}}{\sup} f(\lambda) > 0$$, the best $$b$$ is then

$$b = \sqrt{2M}$$.

Given $$p$$, $$H(Z)$$ is a constant, and then just use numerical methods to obtain $$M$$.

Below is an image of $$f$$ generated using R for $$p = (0.1, 0.2, 0.3, 0.4)$$ from $$-100$$ to $$100$$ in steps of $$0.001$$ (skipping 0). • Hi, thanks a lot for the answer; it's almost exactly what I was looking for. The only part I am struggling with is how to get the supremum (resp. maximum) of $f(\lambda)$. We can definitely use some numerical method to maximize $f(\lambda)$. However, a maximum found by a numerical solver will be in general a local maximum; for a subgaussianity to hold, we need to find a global maximum of $f(\lambda)$. From the plot you posted, it seems that there will be only one maximum, which is good. Is there some easy way to prove it? (I am trying differentiating $f(\lambda)$ which is kinda messy). Aug 30 '21 at 11:57
• Indeed, your observation on the possibility of more than one critical points is valid. I tested a bunch of p's and they all had only one global maximum, but it was just tests. I will try to provide a rigorous proof (or counter-example) when I get some free time. Aug 31 '21 at 20:55
• Btw I awarded the bounty (since your analysis is very useful and shed a lots of light on the problem), but not marked the answer as accepted (since I belief the problem is not solved unless we can guarantee that a local maximum found by numerical method will be also a global one), I hope that it's ok. Sep 1 '21 at 8:10
• I was not able to prove that the maximum is unique. However, the simulations seems to suggest so. Oct 16 '21 at 15:23