Возьмём парадокс дружбы (Friendship paradox). Коротко: «в среднем у ваших друзей больше друзей, чем у вас». Почему так кажется парадоксальным — потому что интуиция неправильно учитывает способ выборки друзей. Разбор и формализация:
Формулировка (формальная). Пусть $G$ — конечный неориентированный простой граф на $n$ вершинах без изолированных вершин, степени вершин $d_1,\dots ,d_n$. Пусть $D$ — степень случайной равновероятной вершины. Пусть процедура «случайный человек, затем случайный его друг» даёт вершину $W$. Тогда распределение $W$ «смещено по размеру»:
$$\mathrm{Pr}(W=i)=\frac{d_i}{{\sum }_{j=1}^n{d}_j}.$$ Ожидаемая степень случайной вершины
$$\mathbb{E}[D]=\frac{1}{n}\sum _{i=1}^n{d}_i,$$ а ожидаемая степень случайного друга равна
$$\mathbb{E}[\mathrm{deg}(W)]=\sum _{i=1}^n\frac{d_i}{{\sum }_j{d}_j}{d}_i=\frac{{\sum }_{i=1}^n{d}_i^2}{{\sum }_{i=1}^n{d}_i}.$$ Противоречия нет: по неотрицательной дисперсии или неравенству Коши-Шварца
$$\mathbb{E}[D^2]\ge (\mathbb{E}[D]{)}^2,$$ откуда
$$\frac{\mathbb{E}[D^2]}{\mathbb{E}[D]}\ge \mathbb{E}[D],$$ то есть
$$\mathbb{E}[\mathrm{deg}(W)]\ge \mathbb{E}[D],$$ равенство достигается только если все степени равны (регулярный граф).
Интуитивное объяснение. Высокостепенные вершины (очень популярные люди) участвуют во многих «дружеских связях», поэтому при выборе «друга случайного человека» такие вершины встречаются намного чаще. Это классическая size-bias: вы с большей вероятностью натолкнётесь на человека, у которого много связей.
Пример (звезда с $n$ вершинами). Степени: центр $d_1=n-1$, остальные $d_2=\cdots =d_n=1$. Тогда
$$\mathbb{E}[D]=\frac{2(n-1)}{n}\text{(≈2 для большого n)},$$ $$\mathbb{E}[\mathrm{deg}(W)]=\frac{(n-1{)}^2+(n-1)\cdot 1^2}{2(n-1)}=\frac{n}{2},$$ то есть средний друг имеет около $n/2$ друзей — намного больше, чем средняя степень.
Замечание о «большинстве». Среднее больше не означает, что у большинства людей друзья популярнее; это утверждение о математическом ожидании. В некоторых графах и действительно более чем у половины людей средний друг статистически популярнее, но это не следует автоматически из предыдущего неравенства.
Вывод: нет мистики — парадокс возникает из-за смещения выборки (size-bias). Формальное корректное утверждение — приведённое выше равенство и неравенство для ожиданий: $\mathbb{E}[\mathrm{deg}(\text{случайного друга})]=\frac{\mathbb{E}[D^2]}{\mathbb{E}[D]}\ge \mathbb{E}[D]$.