on average a random friend of mine has more friends than I do

Question

Let $G=([n], E)$ be a finite graph with degree sequence $d=(d_v)_{v\in [n]}$. Assume $d_v\ge 1\;\forall v\in [n]$. Let $X_n$ be the degree of a vertex drawn uniformly at random from $[n]$, and $Y_n$ be the degree of a uniformly drawn neighbour of this vertex. Then

$$\mathbb E[Y_n]\ge \mathbb E[X_n],$$ the inequality being strict unless all degrees are equal.

I was trying to understand the proof from This book where the proof goes like this:

The joint law of $(X_n, Y_n)$ is $$\mathbb P [X_n= k, Y_n=l]=\frac{1}{n}\sum_{(u,v)\in E'} \mathbb 1_{\{d_u=k, d_v=l\}}\frac{1}{d_u}$$, Where the sum is over all directed edges $E'$; i.e., we now consider $(u,v)$ to be a different edge than $(v,u)$, and we notice that, given that $u$ is chosen as the uniform vertex, the probability that its neighbour is chosen is $\frac{1}{d_u}$.

Could anyone explain the indicator function used on the right side of the equality? Also, I did not understand how to find the quantity $\mathbb E[X_n]$ and $\mathbb E[Y_n]$; thanks for any help in understanding more intuitively.

Answer 1

A standard casework / conditioning exercise.

Let $X$ be the first chosen vertex and let $Y$ be the neighbour of $X$ that's chosen. Then the key observation is that $X$ and $Y$ must be adjacent and hence must be the two end points of some edge, thus by enumerating over all cases where one has a degree $k$ vertex and a degree $\ell$ vertex adjacent one obtains

$\mathbf{P} \{ \text{deg} (X) = k , \text{deg} (Y) = \ell \} = \sum_{(x,y) \in E'} \mathbf{P} \{ X = x \wedge Y = y\} \mathbf{1}_{\{\text{deg}(x) = k ; \text{deg}(y) = \ell\}}$

$=\sum_{(x,y) \in E'} \mathbf{P} \{ Y = y | X = x \} \mathbf{P} \{ X = x \} \mathbf{1}_{\{\text{deg}(x) = k ; \text{deg}(y) = \ell\}}$

$= \sum_{(x,y) \in E'} \underbrace{\mathbf{1}_{\{\text{deg}(x) = k ; \text{deg}(y) = \ell\}}}_{\text{since } x \text{ deg}(x)= k; \text{ deg}( y) \text{=} \ell} ~~~ \underbrace{\frac{1}{n}}_{\text{as } X \text{ is chosen uniformly}} ~~~\underbrace{\frac{1}{\text{deg(x)}}}_{\text{as } Y \text{ is chosen uniformly from among the neighbours of } x}$

Answer 2

For interest sake, and to address the question of how one might calculate the expectations, and perhaps as motivation for why this is avoided in the general case, I provide a direct proof for a specific case, where the first $n-1$ vertices have the same degree $d$ and vertex $n$ has degree $d'\neq d$.

Denote by $F_i$ the largest subset of $[n]$ such that there is an edge from vertex $i$ to every element in $F_i$ (so $F_i$ is the neighbourhood of $i$). Then

$\mathbb{E}[X_n] = \frac{(n-1)d + d'}{n}$

And

$ \mathbb{E}[Y_n] = \frac{1}{n} \sum_{i\in [n]}\sum_{j\in F_i}\frac{d_j}{d_i} $

In this specific case we can simplify the expression for $\mathbb{E}[Y_n]$

$\mathbb{E}[Y_n] = \frac{1}{n} \left(\sum_{i\in [n-1]} \sum_{j \in F_i}\frac{d_j}{d_i} + \sum_{j\in F_n}\frac{d_j}{d'}\right)$

$ = \frac{1}{n} \left(\sum_{i\in [n-1]} \sum_{j \in F_i}\frac{d_j}{d_i} + \sum_{j\in F_n}\frac{d}{d'}\right)$

$ = \frac{1}{n} \left(\sum_{i\in [n-1]} \sum_{j \in F_i}\frac{d_j}{d_i} +\frac{d\cdot d'}{d'}\right)$

Since all of the vertices in the neighborhood of vertex $n$ have degree $d$, and there are exactly $d'$ of them. Now to compute the left hand sum, note that exactly $d'$ of the vertices in $[n-1]$ have vertex $n$ i their neighbour, for these vertices the average degree in their neighbourhood is $\frac{(d-1)d + d'}{d}$ and for the remaining $n-d'-1$ vertices, their average neighbourhood degree is just $d$. So the left hand sum gets replaced with these expressions and we get

$ = \frac{1}{n}\left(d'\cdot\frac{(d-1)d + d'}{d}+ (n-d'-1)d +d\right)$

Comparing this to the expression for $\mathbb{E}[X_n]$ we see they both share a common factor $\frac{1}{n}$ Which we can get rid of for the comparison, as well as a common term $n\cdot d$. We are then left comparing

$$ -d+d' $$ with $$ -d'\cdot d + \frac{d'(d-1)d + d'^2}{d} $$

The second expression simplifies a bit to

$ - d' + \frac{d'^2}{d} $

So according to the theorem, we should get

$$ -d + d' \leq - d' + \frac{d'^2}{d} $$

Or $$ 2d'd \leq d^2 + d'^2 $$

Or $$ 0 \leq (d-d')^2 $$

Which is indeed true for any natural numbers $d$ and $d'$ . And this equality is of course strict when $d=d'$. As you can see however, this argument is probably too complex to generalise, but I think its interesting to see how the algebra works out.