Регистрация Войти
Рейтинг:1
pioneer avatar Crypto

О некоторых тестах в NIST SP 800-22 rev 1a и функции erfc

флаг in
pioneer

Я изучаю тест случайности документации NIST SP 800-22 rev 1a.

https://csrc.nist.gov/publications/detail/sp/800-22/rev-1a/final

Пока я читал, возникло несколько вопросов, и я изложил их так. Мои вопросы:

  1. В частотном тесте в блоке 2.2, рассматривая (3) 2.2.4, есть часть, которая рассчитывается следующим образом. $$\chi^2(obs)=4M\sum_{i=1}^{N}(\pi_i - 1/2)^2$$ Я не понимаю, почему это умножается на 4 здесь.

  2. В Runs Test 2.3 p-значение рассчитывается как $$P-value = erfc(\frac{|V_n(obs)-2n\pi(1-\pi)|}{2\sqrt{2n}\pi(1-\pi)}).$$ Каково здесь значение знаменателя? я знаю это $2\пи(1-\пи)$ это среднее, но я не знаю, откуда взялся знаменатель.

  3. Есть ли причина находить p-значение через erf вместо нормального распределения в (2)?

Спасибо.

41
0 + 0
Рейтинг:0
Daniel S avatar Crypto
флаг ru
Daniel S

  1. Это тревожно. Обычный Пирсон $\чи^2$ тестовое задание было бы $$M\sum_{i=1}^n\frac{\left(\pi_i-\frac12\right)^2}{\frac12}=2M\sum_{i=1}^n\left(\pi_i- \frac12\right)^2.$$ Я подумаю еще немного, но, возможно, стоит сбросить водоносные горизонты в NIST.

  2. Предполагается, что это стандартное отклонение. Для независимых, одинаково распределенных битов статистика выполнения должна иметь биномиальное распределение. Затем центральная предельная теорема говорит нам, что бином может быть аппроксимирован нормальным распределением. Обратите внимание, однако, что знак квадратного корня должен распространяться на $\пи(1-\пи)$ фактор.

  3. Функция erf вычисляет двустороннее нормальное распределение. Нас интересуют как случаи, когда прогоны преобладают (т. е. много последовательных пар 00 и 11), так и случаи, когда их недостаточно (т. е. много пар 01 и 10). Оба показывают проблемы с распределением, но объясняются противоположными хвостами.

0 + 0
pioneer avatar
флаг in
pioneer
Спасибо за ответ. Но я не совсем понимаю второй ответ. Если я напишу выражение, как вы говорите, не должно ли $p-value$ быть $erfc(\frac{|V_n(obs)-n\pi|}{\sqrt{n\pi(1-\pi)}} )$?потому что для CLT мне нужно построить выражение $\frac{V_n-np}{\sqrt{npq}}$.
0
Ответить
Daniel S avatar
флаг ru
Daniel S
Ваша статистика будет правильной для проверки количества единиц ($\pi$ — это вероятность того, что будет выведена единица). Они подсчитывают количество 01 и 10. Они встречаются с вероятностью $(1-\pi)\pi$ и $\pi(1-\pi)$, так что мы имеем $\mathrm{Bin}(n-1,2\pi(1-\pi) )$ распределение. Глядя глубже, кажется, что происходит какое-то странное приближение.К счастью, этот документ пересматривается, так что в новой версии есть шанс внести ясность.
0
Ответить
pioneer avatar
флаг in
pioneer
Как вы упомянули, понятно, что $V_n(obs)$~$Bin(n-1, 2\pi(1-\pi))$ выполняется, потому что они подсчитывают количество 10 и 01. Однако, поскольку даже в таком случае выполняется выражение $P-value = erfc(\frac{|V_n(obs)-2n\pi(1-\pi)|}{\sqrt{n2\pi(1-\pi)( 1-2\pi(1-\pi))}}).$ выражение в документе не выполняется. Выражение в документе неправильное? (+На самом деле, это должно быть написано как $n-1$ вместо $n$, можно ли изменить его произвольно?)
0
Ответить
Daniel S avatar
флаг ru
Daniel S
Я не решаюсь заявить о неправильности, поскольку они могут использовать некоторое приближение к дисперсии, о котором я не знаю. Обратите внимание, что ваше выражение erf требует $\sqrt 2$ в знаменателе. Ошибка переключения с $n-1$ на $n$ с ростом $n$ пренебрежимо мала. Я действительно думаю, что стоит поднять этот и ваш первый запрос в NIST, если выражения все еще появляются в исправленной версии, и я попытаюсь это сделать.
0
Ответить
pioneer avatar
флаг in
pioneer
Я понимаю. В следующий раз я надеюсь, что NIST должным образом пересмотрит эти факты или опубликует документ с достаточными пояснениями по этому поводу. Большое спасибо за хороший ответ.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.