If $\Bbb E[Z_n]\xrightarrow[n\rightarrow\infty]{} 0$ then can we say $Z_n=0$ with high probability?

64 Views Asked by At

This is in the context of subgraph containment problem. Say I managed to prove that a certain subgraph $H$ (like a triangle or a small cycle) of an Erdos-Renyi graph $G$ on $n$ verticies with edge probability $p$ ($G\sim\text{ER}(n,p)$) satisfies $$\Bbb E[\text{# times }H\text{ appears in }G ]=1/n$$ which goes to zero ($p$ being specified in the question as some function of $n$).

Is this enough to say that "$G$ does not contain $H$ with high probability"?

1

There are 1 best solutions below

1
On

Yes it is, almost. I have seen it written that way. The best way to put it is that the probability that $H$ appears goes to 0 as $n$ increases. Or the $Z_n$s go to 0 with high probability, with $Z_n$ as you defined. Note the following claim:

Claim 1: Let $Y$ be a random variable that takes on nonegative integral values. Then $\Bbb{E}[Y] \ge \Bbb{P}[Y > 0]$.

This claim is easy to show. So if you are given a series $\{Y_n\}$ of rvs where $Y_n$s are a sequence of r.v.s as in the hypothesis of Claim 1 where $\Bbb{E}[Y_n] \le n^{-1}$ it follows that the $Y_n$s go to 0 with high probability as well.

As $\#\{$times $H$ appears in $G\}$ is a random variable that takes nonegative integers, it follows from Claim 1 that

$$\frac{1}{n} \ge \Bbb E[\text{# times }H\text{ appears in }G ] \ge \Bbb P[\text{# times }H\text{ appears in }G ]$$