0
$\begingroup$

We have that for a real valued random variable $X$,

$$ P(X=0) \leq \frac{\text{Var}(X)}{\left(\mathbb{E}(X)\right)^2} $$ known as Chebyshev's inequality. Consider a random variable $X \in \{0,1,2,\dots\}$, for example counting subgraphs in a random graph. Sometimes, in this setting, the raw moments $\mathbb{E}(X^{n})$ can grow very quickly, since there is significant dependence between the objects being counted.

I am looking to show that $P(X=0) \to 0$ as $\mathbb{E}(X) \to \infty$ using the above bound, but cannot draw any conclusions, because the above variance grows too quickly compared with the square of the mean. Is there a route one can take to try to use more information about the random variable to conclude what is happening to $P(X=0)$? Are there any examples of this?

One idea is to use oscillating sums of factorial moments $E_{r}(X)=\mathbb{E}((X)_r)$ (see Random Graphs, B. Bollobas, Corollary 1.12), where for even $t$

$$ P(X=0) \leq \sum_{r=0}^{t}(-1)^{r}\frac{E_{r}(X)}{r!}. $$ This idea can be difficult to work without good bounds on all moments since one needs to upper bound even moments, and lower bound odd moments, to upper bound the oscillating sum above. Significant work may be required attempting to find a sufficient lower bound on $E_{r}(X)$ given an upper bound, without the bound going to infinity with $\mathbb{E}(X)$.

$\endgroup$
4
  • 1
    $\begingroup$ There is a lot of work on tail bounds for subgraph counts that might interest you. For example, "An Exponential Bound for the Probability of a Specified Subgraph in a Random Graph" by Svante, Tomasz, and Andrzej shows that $P(X=0)$ decays exponentially in the expected number of subgraphs isomorphic to the least likely subgraph in your target graph. $\endgroup$
    – Kevin
    Commented Aug 7, 2022 at 1:27
  • $\begingroup$ What is the context? What information do you have about the variable? Why do you have (eg) information about the moments but not about the point masses? $\endgroup$
    – user44143
    Commented Aug 7, 2022 at 3:31
  • 1
    $\begingroup$ For context, $X$ is the number of $k$-paths which run between two vertices $x,y$ at some Euclidean distance $|x-y|$ in a random geometric graph. Its easy to look at expected values of counts of pairs of paths, or triples of paths (these are the raw moments), but point masses are more difficult to obtain. $\endgroup$
    – apg
    Commented Aug 7, 2022 at 11:20
  • $\begingroup$ @Kevin I will look at that, thank you. $\endgroup$
    – apg
    Commented Aug 7, 2022 at 11:21

0

You must log in to answer this question.

Browse other questions tagged .