Вероятностный предсказатель Пети

[fiktor]

Есть программа Г, которая (случайно) генерирует пары $(p,k) \in [0,1]\times K$ и
программа R, получающая на вход p и выдающая 1 с вероятностью p, 0 с вероятностью 1-p.

Программист Петя принес своему боссу программу П, получающая на вход k и выдающая число $\textrm{П}(k) \in [0,1]$ и сказал, что "для любой пары (p,k), сгенерированной программой Г, p=П(k)".

Вася (который знает, что Петя соврал и, более того, знает, что для пар (p,k), генерируемых программой Г, П(k) и p независимы, но у него нет никаких доказательств) хочет устроится на работу. Поэтому он пошел к боссу и сказал
--- Петя врет, не для всех пар (p,k), сгенерированных Г выполнено равенство p=П(k).
--- Хорошо --- сказал босс, который, как известно, никогда не врет --- докажи это. Я N=4000 раз запущу программу Г (получив таким образом N пар (p,k) и запишу на листочек N получающихся из них пар (R(p), П(k))). Придумай такое событие B, что можно определить (... программа, определяющая истинность B должна на современном PC в 5 минут укладываться), верно оно или нет по набору из N записанных на листочке пар (R(p), П(k)), и доказательство того, что если Петя не врет, то вероятность B не превосходит 0.01. Если B окажется верным, ты принят. Да, кстати, можешь использовать, что матожидание чисел p, выдаваемых программой Г равно 0.5.

Вася знает (но не может доказать), что распределение чисел, выдаваемых программой П имеет примерно такой вид:


Какое событие B предьявлять боссу?
(понятно, что условие задачи с математической точки зрения определено не сильно лучше, чем задача "написать хороший архиватор", но хотелось бы какой-нибудь хороший архиватор ответ, позволяющий Васе с большой вероятностью на работу попасть)

[ha]

Мне кажется, что задача не разрешима.

Но если у вас есть предсказатель лучше, то давайте за 0 - (1-p)^2 очков, а за 1 - p^2 очков. Тогда остается показать, что оценка у вашего предсказателя больше на статистически значимую величину чем оценка предсказателя Пети.

[Хорхе]

Странная постановка задачи. Зачем генерировать эти $R(p)$? Намного легче проверить, выполняется ли $p=\Pi(k)$ для всех пар, выданных машиной $\Gamma$.

Ну да ладно. Вот как я понимаю эту задачу. Имеется выборка

$$ (a_1,p_1),(a_2,p_2),\dots, (a_n,p_n), $$

где $a_i\in\{0,1\}$, $p_i\in [0,1]$ ($p_i=\Pi(k_i)$), $a_i=0$ с вероятностью $1/2$.


Надо составить статистический критерий проверки гипотезы

$$ H_0 = \{\text{$a_i$ и $p_i$ независимы}\} $$

против альтернативы

$$ H_1 = \{P(a_i=1|p_i)=p_i\}, $$

так, чтобы вероятность ошибки первого рода (отклонить правильную $H_0$) не превосходила $\alpha$.

(В данной постановке $n=4000$, $\alpha = 0.01$.)

Я правильно понял задачу?

[PAV]

Можно предложить рассмотреть такое решение. Зададимся двумя порогами: $q_0<0.5$ и $q_1>0.5$. Разобьем выборку, которая подана на вход программе, на три части в зависимости от того, в какой из трех интервалов $[0,q_0]$, $(q_0,q_1)$ или $[q_1,1]$ попадает число $p_i$, которое выдала программа Пети. (Заметим, что при подборе этих порогов Вася может с некоторой точностью заранее определить, сколько в среднем окажется элементов в каждой группе, так как он знает это распределение).

Затем делаем так. Вторую группу не используем никак. Берем первую: если Петя не соврал, то в ней все наблюдения $R(p_i)$ должны иметь вероятность единиц $\le q_0$. То есть если предположить наихудший случай, что все вероятности равны $q_0$, то событие вида {количество единиц $>N_0$} можно сделать достаточно маловероятным, подобрав порог $N_0$ (взяв соответствующую квантиль биномиального распределения). Для последней группы это же событие будет иметь вид {число единиц $<N_1$}.

В качестве финального события B нужно взять либо пересечение, либо объединение этих двух.

Заранее нужно подобрать пороги $q_i$ и значения вероятностей, по которым определяются квантили $N_i$. Вася должен сделать это, придерживаясь ограничений, чтобы если Петя не соврал, то событие B было бы маловероятным, однако при условии независимости величин - нужно максимизировать его вероятность. Собственно же от программы Васи требуется только по заданным объемам выборок определить значения квантилей $N_i$.

-- Вс окт 11, 2009 20:40:10 --

Что-то не могу быстро сообразить, верно ли, что сама по себе последовательность значений, сгенерированных программой P, является схемой Бернулли с вероятностью единицы $0.5$ (учитывая подсказку босса, но не зная, какое на самом деле точное распределение значений, выдаваемых программой Г). Если это так, то Вася на самом деле знает точное распределение того, что будет подано на вход его программе, так что может точно рассчитать вероятность того, что произойдет нужное ему событие В, при заданных параметрах, и может его максимизировать.

-- Вс окт 11, 2009 22:14:08 --

Можно попробовать еще упростить мою схему: выбирать пороги $q_i$ симметричными относительно $0.5$ и объединять первую и третью выборки, предварительно в одной из них поменяв единицы на нули и наоборот. Тогда получим сразу одно событие - статистически значимое отклонение частоты от предполагаемой вероятности в заданную сторону.

[Хорхе]

Если постановка такая, как я написал, можно воспользоваться критерием хи-квадрат независимости.
Сперва разбиваем отрезок $[0,1]$ на $N$ частей, например, $t_j=j/N$. Считаем фактические частоты: $\nu_{i,j} = \# \{(a_m,p_m): a_m=i, p_m\in [(j-1)/N,j/N)\}$; $\nu_j = \nu_{0j}+\nu_{1j}$.

Статистика критерия

$$ \xi_N = \sum_{i=0}^1 \sum_{j=1}^N \frac{(\nu_{ij} - \nu_j/2)^2}{\nu_j/2} $$

(это не совсем стандартная формула: мы используем то, что безусловное распределение $a_i$ -- бернуллиевское с параметром $1/2$).

Тогда при нулевой гипотезе распределение $\xi_N$ -- приблизительно хи-квадрат с $N$ (вроде бы) степенями свободы (в классическом варианте это $(2-1)(N-1)$ степеней свободы, тут мы вместо эмпирической вероятности подставляем $1/2$).

При альтернативной гипотезе это выражение где-то $4n E((\Pi(k)-1/2)^2)$ (с поправочным членом порядка $\sqrt{n}$ -- если я не ошибся в прикидках), где $k$ -- случайное число, выдаваемое программой $\Gamma$.

Скажем, если мы возьмем $N=40$ и критическую область $[9,\infty)$, то вероятность ошибки второго рода приблизительно $0.0001$. Ошибка первого рода должна быть тоже очень малой, даже если $\Pi(k)$ довольно близко к постоянной $1/2$. На рисунке $E((\Pi(k)-1/2)^2)\approx 0.0036$ (похоже на график нормальной плотности $N(0.5,0.06^2)$), то есть при альтернативной гипотезе статистика критерия должна быть за $50$.

Абсолютно точно оценить ошибку первого рода я, к сожалению, не могу, но мне кажется, при этих цифрах, что она куда меньше, чем $0.01$ и даже чем $0.001$.