In the course of a research project about discrete probability distributions, my coauthors and I keep seeing some quantity appear, and I would like to understand whether it has been studied or has a characterization in the literature (I couldn't find any besides the 3 references below).

Let $p$ be a discrete probability distribution over some discrete set $\mathcal{X}$, seen as a vector $(p_i)_{i\in\mathcal{X}}$. The quantity is then $$ s(p) := \frac{\lVert p\rVert_3^3 - \lVert p\rVert_2^4}{\lVert p\rVert_2^3} \tag{$\dagger$} $$ (one could also consider $ t(p) := \frac{\lVert p\rVert_3^3 - \lVert p\rVert_2^4}{\lVert p\rVert_2^4} $ if it's more convenient, both are equivalent for my purposes.) Note that the lack of homogeneity is just apparent, as we enforce $\lVert p\rVert_1=1$ (it's a probability distribution).

This quantity intuitively captures "how non-uniform" $p$ is: for instance, $s(p)=0$ iff $p$ is uniform on its support, and [1,2] give a (loose) connection between $t(p)$ and the total variation distance of $p$ to the closest uniform distribution. The numerator also appears in the analysis of the empirical estimator for the collision probability of a distribution [3].

We also have the view that, looking at the random variable $Y=p(X)$ for $X\sim p$, $$ \mathbb{E}[Y] = \lVert p\rVert_2^2, \qquad \operatorname{Var}[Y] = \lVert p\rVert_3^3 - \lVert p\rVert_2^4 $$ which maybe may be useful? For instance, by Chebyshev's inequality, $$ \mathbb{P}\{ |p(i) - \lVert p\rVert_2^2 |> \alpha\lVert p\rVert_2^2 \} \leq \frac{t(p)}{\alpha^2} $$ thus giving a lower bound on the total mass (under $p$) of elements whose probability is within a factor $\alpha$ of $\lVert p\rVert_2^2$.

Do the quantities $s(p)$ (or $t(p)$) appear in the literature, and are either of them known to characterize (in some quantitative sense) how "non-uniform" a probability vector is?

[1] Batu, Tuğkan; Canonne, Clément L. Generalized uniformity testing. 58th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2017, 880--889, IEEE Computer Soc..

[2] Diakonikolas, Ilias, Daniel M. Kane, and Alistair Stewart. Sharp bounds for generalized uniformity testing. In Advances in Neural Information Processing Systems, pp. 6201-6210. 2018.

[3] Diakonikolas, Ilias; Gouleakis, Themis; Peebles, John; Price, Eric. Collision-based testers are optimal for uniformity and closeness. Chic. J. Theoret. Comput. Sci. 2019.

  • $\begingroup$ Why the downvote? Is there something wrong with my question, and if so, how can I improve it? $\endgroup$ – Clement C. Jun 12 '20 at 19:20
  • $\begingroup$ isn't the $L_2$ norm $||p||_2^2$ the typical way to measure nonuniformity of a distribution? $\endgroup$ – Carlo Beenakker Jun 22 '20 at 13:24
  • $\begingroup$ @CarloBeenakker It is definitely one way. But it has some issues as well, and doesn't quite cut it: for instance, when the support size $k$ is large enough you can have two distributions with same $\ell_2$ norm, but one with all elements within a multiplicative factor say $2$ of $1/k$, and the other where a single (or a constant number of elements) with probabity $\approx 1/\sqrt{k}$ and all the others probability $\approx 1/k$. $\endgroup$ – Clement C. Jun 22 '20 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.