# Expected number of vertices of a given degree in a random graph

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.

• Looks correct to me. – kccu Apr 10 at 15:25

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.

• 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. – vxnture Apr 10 at 20:58