Чи pi хороший генератор випадкових чисел?

Частиною того, що я роблю, це вивчення типової поведінки великих комбінаторних структур, дивлячись на псевдовипадкові випадки. Але багато продаваних генераторів псевдослучайних чисел відомі недоліки, що заважає мені читати цифри (або біти) $ \ pi $.

Мій колега каже, що він "десь читав", що цифри $ \ pi $ не створюють гарного генератора випадкових чисел. Можливо, він згадує статтю "Дослідження про випадковість цифр $ \ pi $" Шу-Чжу Ту та Єфрема Фішбаха. Хто-небудь знає цю статтю? Деяка преса отримала (див., Наприклад, http://news.uns.purdue.edu /html4ever/2005/050426.Fischbach.pi.html ) зроблено, що це звучить як $ \ pi $, не було таким гарним джерелом випадковості, але абстрактним для самої статті (див. http://adsabs.harvard.edu/abs/2005IJMPC..16..281T ) пропонує протилежне.

Хто-небудь знає про проблеми з використанням $ \ pi $ таким чином? Звичайно, якщо ви використовуєте цифри $ \ pi $, ви повинні бути обережні, щоб не повторно використовувати цифри, які ви вже використовували в інших місцях експерименту.

Я відчуваю, що ви повинні використовувати цифри $ \ pi $ для моделювання Монте-Карло. Якщо ви використовуєте комерційний RNG, і це призводить до публікації помилкових висновків, ви втратили час і вводять в оману колег. Якщо ви використовуєте $ \ pi $ і це призводить до публікації помилкових висновків, ви все ще витратили час і ввели в оману своїх колег, але ви також знайшли шаблон у цифрах $ \ pi $!

42
Я сумніваюся в цьому. Особисто я набагато щасливіше вірю в опублікований доказ (що я не можу знайти помилку), ніж вихід деякого роду RNG, побудований вручну в реальному світі.
додано Автор DavidEBest, джерело
додано Автор Deepak Shenoy, джерело
Чи є фактичні приклади, коли комерційні RNG призвели до помилкових висновків у опублікованому документі?
додано Автор Assaf Lavie, джерело
Існують випадки, коли генератори псевдовипадкових чисел можуть призводити до неправильних результатів моделювання (наприклад, див. «Чутливість балістичного осадження генераторам псевдовипадкових чисел» Д. Соузи, Бар-Яма та Кардара (Physical Review E 57 (1998), 5044- 5052), mae.ucdavis.edu/dsouza/Pubs/bdrng.final_pre.pdf ) Це не дуже хороші PRNG-файли, звичайно, не криптографічні, але багато симуляцій використовують, щоб будь-який гнучкий PRNG, що відбувається, не реалізується у своїй улюбленій мові програмування, це може бути справжньою проблемою.
додано Автор brasofilo, джерело

11 Відповіді

Строго кажучи, існують деякі відомі шаблони в цифрах $ \ pi $. Є деякі відомі результати щодо того, наскільки добре $ \ pi $ можна аппроксиміровать за допомогою раціональних значень, що передбачає (наприклад), що ми a priori знаємо, що наступні $ n $ як ще нерозподілені цифри $ \ pi $ не може бути всім нулем (для деякого явного значення $ n $, що я ліньки для обчислення прямо зараз). На практиці, однак, ці "моделі" настільки слабкі, що вони не вплинуть на будь-які експерименти Монте-Карло.

Основним обмеженням використання цифр $ \ pi $ може бути обчислювальна швидкість. Залежно від того, скільки випадкових цифр вам потрібно, обчислення свіжих цифр $ \ pi $ може стати обчислювальним вузьким місцем. Чим далі ви йдете, тим важче обчислити більше цифр $ \ pi $.

Якщо ви стурбовані якістю випадкових цифр, які ви отримуєте, ви можете використовувати генератори випадкових чисел криптографічні . Наприклад, знайти шаблон у генераторі випадкових чисел Blum-Blum-Shub, ймовірно, дасть новий алгоритм для факторингу великих цілих чисел! Криптографічні генератори випадкових чисел працюватимуть повільніше, ніж "комерційні" генератори випадкових чисел, про які ви говорите, але ви, безумовно, можете знайти те, що буде генерувати цифри швидше, ніж алгоритми обчислення $ \ pi $.

43
додано
Я нещодавно перевірив літературу, і це виглядає так, як я трохи помиляюся про "явне значення $ n $". Саліхов довів, що міра ірраціональності $ \ pi $ менше $ 8 $, що передбачає, наприклад, що існує $ n_0 $ такий, що для всіх $ n> n_0 $ $ n $ th через $ 8n $ -й біт $ \ pi $ не може бути абсолютно нульовим, але, наскільки я міг сказати, не існує ефективної верхньої межі розміру $ n_0 $.
додано Автор Joel Brown, джерело

У технічному сенсі ні. Хорошим генератором псевдослучайних чисел буде той, який ви можете підключити до будь-якого рандомізованого алгоритму, і очікуєте побачити таку саму поведінку, яку ви отримаєте від фактичного генератора випадкових чисел. Один із способів вилучення технічного визначення полягає в тому, що генератор псевдовипадкових чисел не може бути відрізнений від справді випадкового (з імовірністю, обмеженим від 1/2) будь-яким поліноміальним тестом часу.

Але цифри π чітко можна відрізнити від випадкового поліномиального тесту часу, а саме тесту, який обчислює цифри π і порівнює їх з вашою нібито випадковою послідовністю.

З тієї ж причини жодна цілком детермінована послідовність не може бути гарною випадковою послідовністю. Замість того, щоб відповідати цьому визначенню, потрібно використовувати генератор псевдослучайних чисел, який приймає деякий число n справді випадкових бітів як вихідне насіння і генерує з них довшу послідовність (поліноми в n) псевдовипадкових бітів, які не можна відрізнити від випадкового алгоритм поліномиального часу.

19
додано
Так, вся ця ентропія повинна бути десь звідки! З іншого боку, це було великою проблемою з декодування ENIGMA.
додано Автор Edward Nunn, джерело

Також актуальна формула Бейлі-Борвейна-Плуффа

\ frac {2} (8i + 4) - \ frac {4} {8i + 1} - \ frac {2} {8i + 4} - \ frac {1} (8i + 5) - \ frac (1) (8i + 6) \ right), $$

що вказує на певну передбачуваність в базі-16 цифр $ \ pi $.

18
додано
але +1 все одно, тому що я думаю, що ця формула дійсно здорово.
додано Автор DavidEBest, джерело
див. коментар Стіва.
додано Автор DavidEBest, джерело
Я погоджуюся, що це класна формула (і корисна для завантаження), але як це вказує на "передбачуваність", крім того, що обчислювальна складність обчислення однієї цифри або рядка цифр, що використовують її, досить низька?
додано Автор Edward Nunn, джерело
@ Віктор: Чи не так називається "передбачуваність"?
додано Автор JanC, джерело
Я бажаю, щоб люди не розмістили голі посилання. Я рідко слідую за ними.
додано Автор JanC, джерело

Я думаю, це залежить від вашої заявки.

Я б сказав, no , якщо ви використовуєте випадкові числа для створення криптографічних ключів, то ви негайно відкриваєте себе атакам, тому що зловмисник, можливо, може імітувати генератор випадкових чисел, і таким чином ви додаєте одну слабку посилання в ланцюг.

7
додано
Я згоден. Якщо ви хочете зробити експеримент Монте-Карло, $ \ pi $ може працювати, хоча це, ймовірно, буде повільніше, ніж, скажімо, Мерсен-Твістер. Якщо ви хочете зробити крипто, це дуже погана ідея.
додано Автор Mateusz Piotrowski, джерело

Відомо, що $ \ pi $ не рівноцінно розподіляється . Я не знаю, що це говорить (якщо щось) про "випадковість" його цифр, але це може означати використання золотого співвідношення або константи Ейлера-Машерроні на $ \ pi $.

6
додано
mmm Я задаюсь питанням, чи існує зв'язок між алгоритмом easy> алгоритму spigot та доброчесним рівнем розподілу ?
додано Автор DavidEBest, джерело
... або $ \ ln 2: $ для нього є простий алгоритм
додано Автор Edward Nunn, джерело
Чи існують жорсткі кількісні результати, які говорять, що $ \ pi $ equidistributes "повільно"? або просто цифри?
додано Автор John Pardon, джерело

Будь ласка, зауважте, що аналіз Ту та Фішбаха було оскаржено - я не знаю, що ці проблеми є дійсними. Дивись нижче

Спростування претензій, таких як "Пі менше випадкових, ніж ми думали". Джордж Марсалья Заслужений професор Державний університет штату Флорида

http://interstat.statjournals.net/YEAR/2006/articles/0601001.pdf

4
додано
  1. Given all digits of a sequence S till a certain length say n ie di ( i = 1 to n) ; if the probability of any next block of digits B in next m digits ( m -> infinity ) can be ascertained as < 1/(b^w) where b is the base and w is the string length of the block , through an algorithm which is guaranteed to halt then S is NOT a random sequence.

  2. Just being a normal number is not "sufficient" say the sequence 1234..101102103..10001001 is a normal sequence yet not random.

  3. Based on above since using the spigot formula for Pi I can predict its digits, it is not random.

  4. Direction of analysis is also important. Suppose there is a civilization where constant Pi has not been discovered yet ( let alone its formula), here a only a reverse analysis would be possible and the probability of one chancing upon the spigot formula while analysing the digits of Pi cannot be ruled out though its remote. Other wise the equidistribution of digits would lead such a civilisation to take Pi sequence as random

4
додано

Очевидна проблема полягає в тому, що хороший генератор псевдослучайних чисел генерує іншу послідовність кожного разу, коли ви запускаєте її, тоді як цифри pi ніколи не спостерігаються, щоб змінюватися.

3
додано
Все-таки ...
додано Автор Herms, джерело
Тому, коли ви запустите симуляцію наступного разу, просто знайдіть там, де ви зупинилися.
додано Автор Kate Gregory, джерело
Без випадкового посіву неможливо відповісти на питання, чи є цифри $ \ pi $ випадковими. Для постійного насіння цифри $ \ pi $ виглядають постійними .
додано Автор Jonathan Ross, джерело

Криптографічні PRNG є золотим стандартом, оскільки, якщо у вас є практичний спосіб виявити найменшу не випадковість у виведенні, це вважається перервою проти генератора та значним результатом дослідження (у криптоаналізі), якщо PRNG вважається чимось хорошим ( скажімо, якщо це було засновано на AES, Advanced Encryption Standard, розумним способом). Легко робити їх детерміністичними: для будь-якого ключа K просто візьміть зашифровки E (0), E (1), E (2), ... де E - це функція шифрування.

Останні комп'ютери x86 мають апаратну інструкцію для шифрування AES, тому це дуже швидко. Це не здивує мене, якщо AES, використовуючи інструкції з обладнання, швидше, ніж Mersenne Twister, реалізований у програмному забезпеченні.

У першому виданні "Чисельні рецепти" було обговорено використання DES (попередника AES) як RNG, хоча вони вийшли з пізніших видань.

3
додано

Чому б не побудувати випадкові числа з не послідовними цифрами pi? Наприклад, цифри, що розрізняються на 10 цифр, в розрізі.

І ви можете придбати або отримати величезний словник з цифр pi, який повинен бути достатньо, а також деякі розумні кодування про те, як ви здобудете свої цифри.

3
додано
Як ваші пропозиції поліпшать властивості випадковості чи практичність цифрової послідовності?
додано Автор ricree, джерело

Фактично, pi не було доведено, що це нормальне число, і це, безумовно, є мінімальною вимогою для його використання як "випадкових чисел".

2
додано
Дирихле лише говорить, що цифри 1, 3, 7, і 9 будуть відбуватися нескінченно часто. Щоб отримати нормальність, вам слід подумати про первинні прогалини. Нормальність або аномалію, мабуть, випливає з гіпотези Харді-Літтлвуда k-tuple ( mathworld.wolfram.com/k -TupleConjecture.html ).
додано Автор Robert Höglund, джерело
Хіба будь-яка конкретна кількість виявилася нормальною?
додано Автор jt., джерело
Спробуючи побудувати менш передбачуваний нормальний номер, чи корисні номери, які використовують лише підмножину цифр? Чи теорема Дірихле говорить про те, що число, розширення якого складається з останніх цифр послідовних простих знаків> 5, дає число з нормальним наступом цифр 1,3,7,9? Це варіація на коментарі Давичака.
додано Автор Zackkenyon, джерело
@Gerry: Я пропонував, щоб Пауль Зігель поспілкувався з Вікіпедією для відповіді на своє питання про те, чи було встановлено, що певне число є нормальним. Це був Джеральд Едгар, а не я, який вважав, що нормальність є необхідною (недостатньою) умовами для "випадкової послідовності". Для моєї відповіді на питання Джима, див. Мою відповідь на питання Джима.
додано Автор Joel Brown, джерело
@ Паул: Так. Див. Вікіпедію.
додано Автор Joel Brown, джерело
@Timothy, ви не пропонуєте використовувати .123456789101112131415 ... як джерело випадкових цифр, чи є ви?
додано Автор andrew, джерело