¬ипадковий виб≥р. √енеруванн¤ посл≥довност≥ випадкових б≥т≥в на практиц≥ Ї не такою простою справою, ¤к може видатись на перший погл¤д, адже реальна обчислювальна машина не маЇ н≥¤кого механ≥зму дл¤ Уп≥дкиданн¤ монеткиФ. ћи повернемось до цього питанн¤ в розд≥л≥ VI, а до того моменту будемо вважати, що ймов≥рн≥сний алгоритм здатен отримати ¤к завгодно довгу посл≥довн≥сть випадкових б≥т≥в, причому на отриманн¤ одного б≥ту йде один крок роботи алгоритму.

” подальшому виклад≥ конкретних ймов≥рн≥сних алгоритм≥в ми вживатимемо приписи на кшталт Увибрати випадковий елемент ≥з ск≥нченноњ множини Ф. ÷е означаЇ, що елементмаЇ б≥ти сконструйованим певним чином ≥з випадковоњ посл≥довност≥ , причому кожен з елемент≥в множини мусить отримуватис¤ з однаковою ймов≥рн≥стю. —пос≥б такого конструюванн¤ найчаст≥ше буде довол≥ очевидним. ” цьому пункт≥ ми заздалег≥дь розберемо к≥лька простих випадк≥в, ¤к≥ дал≥ зустр≥чатимутьс¤ без детальних по¤снень.

Ќайпрост≥ше влаштувати випадковий виб≥р елемента ≥з множини †дл¤ , або ≥з †дл¤ простого . (ѕрост≥ числа такого вигл¤ду називаютьс¤ простими ‘ерма). ƒл¤ цього випадкова дв≥йкова посл≥довн≥сть довжини просто розгл¤даЇтьс¤ ¤к дв≥йковий запис елемента такоњ множини.

ўоб отримати випадковий елемент ≥з †дл дов≥льного , можна вибрати випадковий елемент ≥з , де , ≥ ¤кщо , то використовувати цей елемент, ¤кщо ж , то виб≥р сл≥д повторити ще раз. ¬насл≥док ц≥Їњ процедури буде отримано з ймов≥рн≥стю . «розум≥ло, що в раз≥ невдач≥ повторювати виб≥р доведетьс¤ не надто довго. —правд≥, ймов≥рн≥сть того, що попаде в лише за ≥-тим разом, дор≥внюЇ , а математичне спод≥ванн¤ к≥лькост≥ повторень процедури до першого усп≥шного вибору дор≥внюЇ

.

“аким же чином проводитьс¤ виб≥р випадкового елемента ≥з дл¤ дов≥льного простого . ўоб вибрати випадковий елемент з множини , де ≥прост≥, можна скористатис¤ насл≥дком II.2.13 з  итайськоњ теореми про остач≥. «г≥дно ≥з ним, досить вибрати ≥ - випадков≥ елементи множин ≥ , ≥ обчислити , дл¤ ¤кого ≥ . “акий елементр≥вном≥рно розпод≥лений на .``

ћетод вишуканий, але прост≥ший ≥ ефективн≥ший дл¤ великих≥спос≥б породженн¤ випадкового елемента з Ї таким. ¬ибираЇмо випадковий елемент з ≥ перев≥р¤Їмо, чи в≥н д≥литьс¤ на ¤кесь ≥з чисел ≥. якщо н≥, то , що нам ≥ потр≥бно, ¤кщо ж д≥литьс¤, то процедуру вибору повторюЇмо ще раз. …мов≥рн≥сть того, що виб≥р буде усп≥шно зд≥йснено за один раз, дор≥внюЇ . ÷ей спос≥б добрий також тим, що в≥н придатний дл¤ породженн¤ випадкового елементу множини дл¤ дов≥льного . ј саме, вибираЇтьс¤ випадковий елемент з †≥ обчислюЇтьс¤ Ќ—ƒ. якщо останн≥й дор≥внюЇ 1, то виб≥р зд≥йснено, а ≥накше виб≥р сл≥д повторити. …мов≥рн≥стьтого, що виб≥р буде усп≥шно зроблено за один раз, дор≥внюЇ . ќй≥нимо, наск≥льки малою Ї ймов≥рн≥сть того, що елемент ≥з все ще не буде вибрано упродовж повторень процедури вибору. ÷¤ ймов≥рн≥сть дор≥внюЇ . «а твердженн¤м II.2.15, при великих . ќтже, ймов≥рн≥сть, ¤ку ми оц≥нюЇмо, обмежена зверху величиною , ¤ка, у свою чергу, не перевищуЇ за нер≥вн≥стю ¬.4. ѕ≥дсумовуючи, бачимо,що з високою ймов≥рн≥стю (наск≥льки високою, залежить в≥д нашого вибору константи ) випадковий елемент з, можна вибрати в результат≥ не б≥льше, ¤к незалежних вибор≥в випадкового елемента з ≥ перев≥рки умови Ќ—ƒ=1.

” цьому контекст≥ доречно згадати класичний результат ƒ≥р≥хле. Ќехай - випадковий елемент ≥з множини , де також вибрано випадковим чином в д≥апазон≥ в≥д 1 до N. “од≥ ймов≥рн≥сть того, що Ќ—ƒ=1 при зростаючому N пр¤муЇ до .