Ожидаемое количество пар столкновений
Я пытался решить эту проблему часами, но не могу понять, как прийти к решению.
Пусть H - универсальное семейство хеш-функций из U = {0, 1, .,,, u - 1} в таблицу размером m. Пусть S ⊆ U - множество m элементов, которые мы хотим хэшировать. Докажите, что если мы случайно выберем h из H, ожидаемое количество пар (x, y) в S, которые сталкиваются, составляет ≤ (m−1)/2.
Мой первый метод состоял в том, чтобы придумать пример для m=2, такой, что возможные результаты для спаривания
0 0
1 0
0 1
1 1
но я не могу понять, как ожидаемое количество пар, которые сталкиваются, может быть дробным (если только это не означает, что вероятность выбора столкновения равна 1/2, но это не имеет смысла, так как количество карт увеличивается, я не думаю), Кто-нибудь может уточнить это?