Look at the friendship network below:
Let $X$ be randomly chosen person and $Z$ be a randomly chosen friend of $X$. Now $f(i)$ represents the number of friends of person $i$. To show,
$E[ f( Z )] \ge E[ f( X )]$
My Approach:
I can create a table:
Looking at the table, for the case $X=1$ and $Z=3$, I have
$E[f( Z )] = 1 + 2 + 2 = 5?$, and $E[ f( X )] = 3$
So,
$E[ {f( Z )}] \ge E[ {f( X )} ]$. Correct?
If yes, How do I prove it mathematically, avoiding explaining each case?
Your calculation of expectations is essentially wrong.
Finding expectations of $f(X)$ and/or $f(Z)$ is not a matter of going case by case. It is - on the contrary - a matter of looking at all cases together. For e.g. the expectation of the first we find:
$$\mathbb Ef(X)=\sum_{i=1}^4P(X=i)f (i)=\frac14\sum_{i=1}^4 i=\frac 14(3+2+1+2)=2$$
On a similar way you can find the expectation of $f(Z)$.
The probabilities $P(Z=i)$ are a bit more difficult to find. We can do this on base of:$$P(Z=i)=\sum_{j=1}^4P(Z=i\mid X=j)P(X=j)=\frac14\sum_{j=1}^4P(Z=i\mid X=j)$$ Example: $$P(Z=1)=\frac14\sum_{j=1}^4P(Z=1\mid X=j)=\frac14\left(0+\frac12+1+\frac12\right)=\frac12$$So we end up with: $$\mathbb Ef(Z)=\sum_{i=1}^4P(Z=i)f (i)=\frac12\cdot3+\frac5{24}\cdot2+\frac1{12}\cdot1+\frac5{24}\cdot2=\frac{29}{12}$$
I would go here for something like this:
$\begin{array}{ccc} \text{Event} & |\text{probability of event}| & \text{value of }f\left(Z\right)-f\left(X\right)\\ \left\{ X=1,Z\in\left\{ 2,4\right\} \right\} & \frac{1}{6} & -1\\ \left\{ X=1,Z=3\right\} & \frac{1}{12} & -2\\ \left\{ \left\{ X,Z\right\} =\left\{ 2,4\right\} \right\} & \frac{1}{4} & 0\\ \left\{ X\in\left\{ 2,4\right\} ,Z=1\right\} & \frac{1}{4} & 1\\ \left\{ X=3,Z=1\right\} & \frac{1}{4} & 2 \end{array}$
leading to: $$\mathbb E[f(Z)]-\mathbb E[f(X)]=\mathbb{E}\left[f\left(Z\right)-f\left(X\right)\right]=\frac{1}{6}\cdot\left(-1\right)+\frac{1}{12}\cdot\left(-2\right)+\frac{1}{4}\cdot0+\frac{1}{4}\cdot1+\frac{1}{4}\cdot2=$$$$\frac{5}{12}>0$$
I have the strong feeling that there must be a more elegant solution that can be applied in a more general setting, but uptil now I couldn't find it.
The fact that in all cases $Z$ already has $X$ as friend points in that direction. Of course also $X$ has $Z$ as friend but that is just because everyone has at least one friend.
Edit: I found this answer. It confirms my "strong feeling".
