1
$\begingroup$

How many vertices of degree exactly $\lfloor n/2 \rfloor$ does the random graph $G(n,1/2)$ contain?

My calculations show that asymptotically this number is around $n^{1/2}$ but I feel like I have made a mistake somewhere.

Let $n = 2m+1$ (for easier notation). $$\mathbb{P}(deg(v)=m) = {2m \choose m} (1/2)^{m}(1/2)^{m}$$ since we choose the $m$ neighbours of $v$ from the remaining $2m$ vertices. If the random variable $X$ counts the number of vertices of degree exactly $m$, $$\mathbb{E}X = (2m+1){2m \choose m}(1/2)^{2m}$$ Using the bound $m^{1/2}{2m \choose m} \geq 2^{2m-1}$ (for large enough $m$), $$\mathbb{E}X \geq 2m^{1/2}2^{2m-1}(1/2)^{2m} = m^{1/2}$$

Is this correct? $m^{1/2}$ seems like too large a number but I am unable to find a mistake.

$\endgroup$
  • $\begingroup$ Looks correct to me. $\endgroup$ – kccu Apr 10 at 15:25
0
$\begingroup$

Around $n^{1/2}$ is exactly what we expect.

Your calculation is fine: for a sharper estimate, we can use Stirling's approximation. This gives us $$ \Pr[\deg(v) = m] = \binom{2m}{m} 2^{-2m} = \frac{(2m)!}{(m!)^2 2^{2m}} \sim \frac{\sqrt{4\pi m}\left(\frac{2m}{e}\right)^{2m}}{\left[\sqrt{2\pi m}\left(\frac{m}{e}\right)^m \right]^2 2^{2m}} = \frac{1}{\sqrt{\pi m}}. $$ So the expected number of vertices of degree $m = \frac{n-1}{2}$ is $\frac{2m+1}{\sqrt{\pi m}} \sim \frac{n}{\sqrt \pi}$.

A similar estimate with a slightly messier proof holds when $n$ is even and $m = \frac n2$ or $m = \frac{n}{2}-1$.


General intuition is that the symmetric binomial distribution $\text{Binomial}(n, \frac12)$ assigns significant probability only to the $O(\sqrt n)$ points around the mean $\frac n2$. Formally, for any $\epsilon > 0$, there is a $C$ such that the probability of leaving the interval $(\frac n2 - C \sqrt n, \frac n2 + C\sqrt n)$ is less than $\epsilon$. The same thing should hold for asymmetric binomial distributions where the probability $p$ is not too small or too large.

We can see this in a bunch of ways. For example, it follows from Chebyshev's inequality, because the standard deviation of the symmetric binomial distribution is $\frac12\sqrt n$, and the probability of going more than $k$ standard deviations from the mean is at most $\frac1{k^2}$.

The relationship between $C$ and $\epsilon$ that Chebyshev gives is not too sharp. Hoeffding's inequality or the normal approximation make more precise predictions.

Anyway, if the binomial random variable is in the interval $(\frac n2 - C \sqrt n, \frac n2 + C\sqrt n)$ with probability close to $1$, and $\frac n2$ is the likeliest value in that interval, its probability should be at least $\frac1{2C\sqrt n}$, which is why the $n^{1/2}$ in your observation appears.

$\endgroup$
  • $\begingroup$ This is incredibly helpful, thank you! I was thrown off by the condition that the degrees be exactly $n/2$, but with Chebyshev it makes much more sense. $\endgroup$ – vxnture Apr 10 at 20:58

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.