2
$\begingroup$

I am confused with how to manipulating with big O notation ,here is a problem from section 2.4(Exercise 2.4.3) high dimensional probability by Roman Vershynin

Consider a random graph $G \sim G(n,p)$ with expected degree $d=O(1)$.show that with high probability , all vertices of $G$ have degrees $$O (\frac{\log n}{\log \log n})$$

I want use Chernoff bound below to bound the degree of vertices:

$$Pr\left[| X-\mu|\geq \delta \mu \right] \leq 2e^ {-c\mu\delta ^2}$$

where c is a constant $\DeclareMathOperator*{\E}{\mathbb{E}} \delta \in [0,1), \mu = \E {X}$ and X is binomial random variable.

how should I do that ?

$\endgroup$
  • $\begingroup$ Welcome to math.SE! You can get properly sized parentheses that adjust to their content by preceding them with \left and \right. You can get proper formatting for operators like $\log$ by using \log. For operators that don't have a command of their own, you can use \operatorname{name}. Please see this tutorial and reference on how to typeset math on this site. $\endgroup$ – joriki Sep 8 '18 at 22:05
3
$\begingroup$

The degree distribution of a node is $\text{Binomial}(n-1, p)$. Here, the mean is constant, so it is a very skewed binomial distribution (approximately Poisson), and the usual Chernoff bound does not do well in such cases. You can try it, but it will not work.

Instead, we can bound the probability that a node has degree at least $k$ by $\binom{n-1}{k}p^k$: the union bound, over all sets of $d$ nodes, that all nodes in the set are adjacent to the given node. So if $X_{\ge k}$ denotes the number of nodes with degree at least $k$, we have $$ \mathbb E[X_{\ge k}] \le n \binom{n-1}{k}p^k \le n \left(\frac{(n-1)e}{k}\right)^k p^k = n \left(\frac{de}{k}\right)^k $$ and now some asymptotic analysis is enough to show that setting $k = \frac{2\log n}{\log \log n}$, say, will make $\mathbb E[X_{\ge k}] = o(1)$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.