**Problem / Observation:**

The friendship paradox is the phenomenon first observed by the sociologist Scott L. Feld in 1991 that most people have fewer friends than their friends have, on average. Prove it mathematically.

Update (23 Oct 2014):

**Solution:**Posted by Mike Earnest and Taz in comments!

If the friendship graph is (V,E), the average number of friends people have is

ReplyDelete(1/|V|) Sum_{v in V} deg v = 2|E| / |V|

The average of the average number of friends people's friends have is

(1/|V|) Sum_{v in V} [ (1/deg v) Sum_{w in v's friends} deg w ]

= (1/|V|) Sum_{v,w in V, v friends with w} (deg w)/(deg v) (*)

Consider the summation in (*). For each edge, with endpoints v and w, there are two terms, (deg v)/(deg w) and (deg w)/(deg v). Since a/b + b/a is always at least 2 (to prove this, start with (a - b)^2 >= 0), this implies that (*) is at least (1 / |V|)*2 |E|, completing the proof.

Thanks Mike. This solution is so better than any explanation I have read elsewhere. Thanks.

Delete:D Thanks!

DeleteThe number of friends people have would not be a normal distribution rather it would be left skewed. So majority of people will have only a few friends while only a small number of people will have lots of friends.

ReplyDeleteThanks to this second group (people with lots of friends) are more likely to number in your friends list. When they are actually part of your friends list, they would significantly skew the average number of friends that your friends have. Hence, on average, your friends will have more friends than you.

Thanks Taz.

Delete