Кіріспе

Бинарлы (бульдік) кездейсоқ айнымалылардың кездейсоқ процесі

Ықтималдық және статистикада Бернулли процесі (Жакоб Бернулли есімімен аталған) – бинарлы кездейсоқ айнымалылардың шекті немесе шексіз тізбегі. Сондықтан, бұл дискретті уақыттық стохастикалық процесс, ол тек екі мәнді – 0 және 1 қабылдайды. Бернулли процесінің компоненттік айнымалылары Xi бірдей таралымға ие және тәуелсіз. Қарапайым тілмен айтқанда, Бернулли процесі – бұл мүмкін әділетсіз монетамен (бірақ тұрақты түрде әділетсіздікпен) қайталанатын монета лақтыру. Тізбектегі әрбір Xi айнымалысы Бернулли сынағымен немесе тәжірибесімен байланысты. Олардың барлығы бірдей Бернулли таралымын қамтиды. Бернулли процесі туралы айтуға болатын көптеген нәрселерді екіден астам нәтижеге (мысалы, алты жақты ойыншық үшін процесс) жалпылауға болады; бұл жалпылау Бернулли схемасы деп аталады. Бернулли сынақтарының шектеулі үлгісіне ғана сүйене отырып, процесс анықтау мәселесін монетаның әділдігін тексеру мәселесі деп атауға болады.

Ресми анықтама

Бернулли процесін ықтималдық кеңістіктерінің тілінде, бастар немесе құйрық мәндерін қабылдайтын кездейсоқ шаманың тәуелсіз іске асырылымдарының кездейсоқ тізбегі ретінде формалдауға болады. Жеке мәннің күй кеңістігі мынамен белгіленеді:

Борел алгебрасы

Сандардың санаулы шексіз тобының көшірмелерінің тікелей көбейтіндісін қарастырыңыз. Бір жақты жиынтықты немесе екі жақты жиынтықты қарастыру қалыпты жағдай. Бұл кеңістікте өнім топологиясы деп аталатын табиғи топология бар. Бұл топологиядағы жиынтықтар – монета лақтырудың шекті тізбектері, яғни H және T (H – сырға, T – құйрық) әрпінен құралған шекті ұзындықтағы тізбектер, ал қалған (шексіз ұзын) тізбек "маңызды емес" деп есептеледі. Мұндай шекті тізбектер жиынтығы өнім топологиясында цилиндр жиынтықтары деп аталады. Мұндай тізбектердің барлық жиыны сигма-алгебраны, нақтырақ айтқанда, Борел алгебрасын құрайды. Бұл алгебра әдетте түрлендіріліп жазылады, мұнда элементтері монета лақтырудың шекті ұзындықтағы тізбектері (цилиндр жиынтықтары) болып табылады.

Бернулли өлшемі

Егер сырға немесе қақпаққа түсу мүмкіндігі p ықтималдығымен берілсе, онда өнім кеңістігінде табиғи өлшемді (немесе екі жақты процесс үшін) анықтауға болады. Басқаша айтқанда, егер дискретті кездейсоқ шама X, 0 ≤ p ≤ 1 шартында p параметрі бар Бернулли таралымына ие болса, оның ықтималдық массалық функциясы былай беріледі:

және

Біз бұл таралымды Ber(p) деп белгілейміз. Кез келген нақты, шексіз ұзын монета лақтыру тізбегінің ықтималдығы дәл нөлге тең екені белгілі; себебі, кез келген A жиыны үшін 1-ге тең ықтималдық, берілген шексіз тізбектің өлшемі нөлге тең екенін білдіреді. Дегенмен, кейбір шексіз монета лақтыру тізбектерінің сыныптары басқаларына қарағанда әлдеқайда ықтимал деп айтуға болады, бұл асимптотикалық теңбөлу қасиетімен сипатталады. Формалды анықтаманы аяқтау үшін, Бернулли процесі жоғарыда көрсетілгендей ықтималдық үштігімен беріледі.

Динамикалық жүйелер

Бернулли процесін сонымен қатар, эргодикалық жүйенің мысалы ретінде динамикалық жүйе деп түсінуге болады, нақтырақ айтқанда, бірнеше әртүрлі тәсілмен өлшемді сақтайтын динамикалық жүйе ретінде. Оның бір жолы – ауысу кеңістігі, екіншісі – одометр. Бұл мәселелер төменде қарастырылады.

Бернулли реті

Бернулли тізбегі термині Бернулли процесінің жүзеге асырылуын білдіру үшін көбінесе бейресми түрде қолданылады. Дегенмен, бұл терминнің төменде келтірілгендей мүлдем басқа формальды анықтамасы бар. Бернулли процесін бір ғана кездейсоқ шама ретінде формальды түрде анықтауға болады (алдыңғы бөлімді қараңыз). Кез келген шексіз x монета лақтыру тізбегі үшін, Бернулли процесімен байланысты Бернулли тізбегі деп аталатын бүтін сандар тізбегі болады. Мысалы, егер x монета лақтыру тізбегін көрсететін болса, онда оған сәйкес Бернулли тізбегі – монета лақтыру нәтижесі «сырға» (heads) тең болатын табиғи сандар немесе уақыт мезеттерінің тізімі болады. Осылай анықталған Бернулли тізбегі – табиғи сандар жиынындағы кездейсоқ ішкі жиын болып табылады. Дерлік барлық Бернулли тізбектері эргодикалық тізбектер болып табылады.

Кездейсоқтық экстракциясы

Кез келген Бернулли процесінен фон Нейман экстракторы арқылы p = 1/2-ге тең Бернулли процесін тудыруға болады, бұл ең алғашқы кездейсоқтық экстракторы болып табылады және ол шынайы біркелкі кездейсоқтықты шығарады.

Итерацияланған фон Нейман экстракторы

Бұл тиімділіктің төмендеуі, немесе кіріс ағынындағы кездейсоқтықтың пайдасыздыққа айналуы, кіріс деректері бойынша алгоритмді қайталап орындау арқылы азайтылуы мүмкін. Осылайша, шығыс "энтропия шегіне кез келген дәлдікпен жақын" болуына қол жеткізіледі. Фон Нейман алгоритмінің қайталанған нұсқасы, сондай-ақ кеңейтілген көп деңгейлі стратегия (AMLS) деп те аталады, 1992 жылы Юваль Перес ұсынған.