Вероятности коллизий.

[kirill94]

Доброго времени суток обитателям форума!
Я хотел бы задать несколько вопросов по поводу распределений вероятностей на конечных множествах и вероятностях коллизий в некоторых экспериментах.

Простейшая задача такого вида выглядит так:
Нам дан черный ящик, в котором лежит либо случайная функция, либо случайная перестановка на некотором конечном множестве.
Мы можем подавать на вход этому ящику запросы вида $X$, ящик будет возвращать нам $f(X)$, где $f$ - либо перестановка, либо просто случайная функция.
По ответу ящика мы должны определить, реализует ли данный ящик случайную функцию либо случайную перестановку.

Формально случайная функция выбирается так:
При каждом запросе Х мы просто берем случайно равновероятно число из $\{1, ... N\}$

Случайная перестановка:
При запросе Х берем случайно равновероятно число из $\{1, .. N\} - S$, где $S$ - уже ранее выбиравшиеся точки.

Оказывается, что для такой задачи лучшей "атакой" на черный ящик будет атака "дней рождения": при количестве запросов, приближающихся к $\sqrt{N}$ для случайной функции мы с вероятностью, близкой к $\frac{1}{2}$, получим коллизию (совпадение $f(X_1) = f(X_2)$ при условии, что $X_1 \ne X_2$). Для случайной перестановки такого быть не может.

Также оказывается, что ничего "более хорошего" мы придумать не можем: для каждого мыслимого эксперимента (вероятностной машины Тьюринга А, которая выбирает $X_i$ и делает запросы к ящику) вероятность различить эти два случая ограничивается таким образом:

$$| \mathbb{P}[\text{A выдаст 1 при взаимодействии со случайной функцией}] -$$ $$- \mathbb{P}[\text{A выдаст 1 при взаимодействии со случайной перестановкой}] | \le \frac{q(q-1)}{2N},$$

где q - количество запросов к черному ящику.

Говоря неформально, мы с "нормальной" вероятностью за $q \approx \sqrt{N}$ запросов отличим случайную функцию от случайной перестановки, но это и лучшее, на что мы можем надеяться.

Это одна из самых простейших задач, для того, чтобы обрисовать примерно ситуацию. Обычно отображения устроены сложнее; например, нужно найти границы на вероятность различения суммы $d$ случайных перестановок $\pi_1(X) + ... + \pi_d(X)$ и случайной функции $f(X)$.

И часто в этих задачах ключевую роль играет количество коллизий при случайных отображениях конечных множеств (некоторые хитроумные комбинации случайных функций и перестановок).

Встречались ли вам где-нибудь подобные задачи? Как такая область может называться? Есть ли техника нахождения границ на вероятности "сложных" коллизий?