Your Friends Have More Friends

  • Medium
  • Probability puzzles
  • Tests: Spotting a sample that weights itself

The puzzle

In almost any social network, the average person has fewer friends than their friends do, on average.

This sounds impossible - it cannot be true of everybody. Explain how it can be true of most people.

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

When you list "my friends", how likely is a popular person to appear on your list?

Hint 2

Try a tiny network: one person connected to three others who know nobody else.

Show the answer Hide the answer

It is a sampling effect. Popular people appear on many friend-lists and unpopular ones on few, so the pool of "somebody's friend" is weighted towards the popular.

How to get there

Take a star: person A is friends with B, C and D, who know nobody else. The friend counts are 3, 1, 1, 1, averaging 1.5.

Now average over friends instead. A's friends have 1, 1, 1 - average 1. But B, C and D each have one friend, A, with 3. So the average friend-count-of-a-friend across the four people is (1 + 3 + 3 + 3)/4 = 2.5, well above 1.5.

Nothing is contradictory: the two averages are over different things. The first picks people; the second picks friendships, and a person with k friends is counted k times. The same bias explains why your gym looks busier than its average attendance and why classes seem larger than the average class size - you are sampled in proportion to the thing you are measuring.

The technique worth keeping

Ask what your sample is actually drawn from. Sampling by relationship rather than by person weights each person by their number of relationships, and that weighting shifts the average upwards whenever the counts vary.