All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Paradoxes
Friendship paradox (Posted on 2014-10-31) Difficulty: 3 of 5
Most people have fewer friends than
their friends have, on average.

Prove it.

No Solution Yet Submitted by Ady TZIDON    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
n = 4 | Comment 2 of 4 |
Just to test my guess, let n = 4.
Then there are 4*3/2 = 6 different possible friendships.
The total possible configurations of friendships and non-friendships are 2^6 = 64.
Of these 23 involve one or more parties having no friends (trust me on this), and will be ignored.
What about the remaining 41 configurations?

Let p = probability of a friendship between any two people be 1/2.  Then all configurations are equally likely.

Of the 41 configurations:
  7 of them have no people whose friends have more friends than they do (again, trust me on this).
 18 have 1/2 of the people with friends who on average have more friends than they.  (For instance, if 5 of the 6 possible friendships exist, which can occur in 6 different ways)
 16 have 3/4 of the people with friends who on average have more friends than they. (For instance, if there are 3 mutual friends, one of whom is also friends to the fourth person, which can happen in 12 different ways)
 Altogether, the probability of having friends who on average have more friends than you =
   (18*1/2 + 16*3/4)/41 = 21/41 which is ever so slightly over 1/2.
 So, for n = 4, the proposition is true if p = 1/2.  There is  some slightly larger p for which the proposition is not true.
 This is an improvement over the n = 3 case, for which the proposition is true only if p < 1/2.
 This reinforces the first of my two earlier guesses:
 (1) As n increases, I expect that the threshold value of p increases, so the statement is more and more likely to be true.
 And I still stand by my 2nd guess:
 (2) As n increases, it makes sense that the actual value of p will decrease, so the statement is also more likely to be true.

  Posted by Steve Herman on 2014-11-01 16:58:47
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information