Генериране на бели зайци и просто разпитване на случайни хора

Генериране на бели зайци и просто разпитване на случайни хора

Тук ще се опитаме да разберем смисъла на случайната проба, и какво можем да направим с една колекция от случайни проби взети от даден набор от елементи.

Случайни проби

Нека си представим ситуация в която имаме набор от елементи, и искаме да направим статистическа картинка, която ни дава обща представа за целия набор, и какво се случва с него.

Първият ни вариант, разбира се, е да погледнем всеки елемент от набора, да видим каква информация ни дава той, да съберем цялата информация и да я генерализираме.
Например: имаме един клас от 1000 ученици. Искаме да знаем нещо за този клас, например колко са момичета и колко - момчета.

Най-лесният ни вариант е да вземем всеки един ученик, да видим дали е момче или момиче, и да ги оставим настрана, избирайки следващия. Накрая ще имаме пълна картина за това, и ще знаем колко от 1000та ученици са момчета и колко - момичета.

Нека сега си представим, че нямаме възможност да питаме всеки отделно - това би ни отнело прекалено много време. Тук пристигаме на вариант две - метода на взимане на случайни проби.

Нека си представим, че имаме възможност да питаме 100 от 1000-та ученици дали са момчета или момичета. Как бихме постигнали това?

Ами по принцип може да ни мине през главата, че просто можем да влезем в една лекция където те са се събрали, и да ги питаме подред: първият е момиче, вторият е момче, и т.н. до номер сто. Но тук можем да сбъркаме много. Простата причина за това е, че в една такава подредба в лекционната зала играят прекалено много фактори- тя не е никак случайна. Може би двама приятели ще седнат заедно за да бърборят, може би момичетата са по-любознателни и ще седят на първите редове, може би двойки ще седят заедно, за да прекарват всичкото възможно време заедно, и т.н. Това ще повлияе много на нашата крайна статистика, която само взима под внимание 100 от 1000 души - едва 10% от набора.

Нека по-добре се изхитрим малко, и вземем 100 души на съвсем случаен принцип - всяко място на което седи някой има дезигниран номер - от 1 до 1000. Написваме тези номера на листчета и ги слагаме в една шапка, разбъркваме добре и теглим. По този начин накрая на упражнението, ще имаме 100 номера от 1 до 1000, и за всеки номер ще можем да разберем, дали на това място в залата седи момче или момиче - тази информация ще бъде взета на случаен принцип, и ние ще имаме достатъчна увереност, че ако генерализираме тези данни от 100 на 1000, ще имаме много подобно процентно отношение между момчета и момичета, на това което би ни дало точната енумерация на всичките 1000 души. В това се състои методът на простото взимане на случайни проби.

Освен простото такова, съществуват и други варианти, като систематично взимане на случайни проби, или групово такова, и т.н. Те се различават предимно в метода на избиране на пробите - т.е. в ситематичното, вместо да теглим от шапка случайни номера, бихме си избрали всеки номер през даден интервал, например всеки десети номер: 0, 10, 20, ...,990. Разбира се, за всеки един от тези методи съществуват среди, в които са полезни, и такива в които не вършат работа, заради факторите които управляват поведението на нашите набори.
Например, в нашият случай с учениците, систематичният вариант сигурно би дал резултати много подобни на случайния метод, но груповият - там нещата са различни. Както споменахме, напълно е възможно в нашата лекционна зала момичета да седят до момичета, и момчета - до момчета - по техен избор. Ако започнем да взимаме проби групово, т.е. например номер 37 и 4те най-близки места до него (по х и у), има голяма вероятност да попаднем на ученици от същия пол, което надали е вярно за цялата лекционна зала. Ако накрая на изброяването сме попаднали на повече групи от момчета, отколкото от момичета, може да си направим грешното заключение, че имаме повече момчета в класа, отколкото момичета.

Но този вариант ще ни даде друга полезна информация, а именно - ако погледнем всяка група, която сме изтеглили, ще знаем дали сме прави в предположението си, че учениците предпочитат да седят в групи от същия пол. Тази информация ще е невъзможно да бъде събрана използвайки систематичния метод.

Да не забравяме и че, въпреки че в нашия пример в това няма логика, в някои случаи може да е полезно след като сме изтеглили нечий номер от шапката, да го върнем обратно в нея, и да има вероятност да го изтеглим отново. Разбира се, в нашия случай не очакваме нищо да се е променило в пола на нашия ученик между две изтегляния на неговия номер, но това не е задължително да е вярно.

Шапката

Както може би сте забелязали, нашият план има една малка слабост. Вместо да си губим времето да питаме всеки отделно дали е момче или момиче, ние си губим времето в писане на всички номера от 1 до 1000 на листчета, в намиране на подходяща шапка без бели зайци в нея, и в теглене на сто листчета от шапката. Защо вместо това не се обърнем към компютъра, и не го накараме да ни изтегли 100 числа между 1 и 1000?

Тук влизат в играта т.нар. генератори на псевдо-случайни числа. Тук също може да се запитаме - за тази наша важна задача, за какво са ни псевдо-случайни числа? Ние искаме най-доброто, не псевдо!

Причините защо псевдо-случайността е достатъчна за нас са няколко:

  1. Случайното генериране на числа е всъщност доста трудоемка задача. За да се постигне трябва да използваме източници с голяма ентропия и елементи на истинска случайност - движение на въздушните пластове, температурен шум, квантови ефекти. Разбира се, това не го прави невъзможно, но просто е прекалено за нашата малка задача. Както ще видим по-нататък, псевдо-случайността покрива нашите критерии.
  2. Псевдо генерираните случайни числа могат да бъдат повторени. Сиреч, ако въведем същите данни в един генератор, той ще изплюе същата последователност от числа. Това е полезно, когато един експеримент трябва да може да бъде повторен абсолютно идентично.

Разбира се, съществуват множество алгоритми за генериране на такива числа, но нека се концентрираме върху един който е хем лесен за приложение, хем достатъчно успешен и употребяван, а именно:

Линейно-конгруентен генератор

...дори не ме карайте да търся превод на "конгруентен". Дори руснаците ги мързи в тази насока.

Та, този метод, въпреки името си, е доста прост, и използва следната формула да изчисли следващото ни случайно число:

$$  X_{n+1} = (aX_n + c) \% m $$

където \(X_{n+1}\) е следващият елемент, \(X_n\) е сегашният (т.нар. семе), \(a,c,m\) са цели числа с определени свойства, които ще разгледаме, а "%" означава "остатък от деленето". И тази елементарна линейна формула претендира, че може да ни генерира псевдо-случайни числа.

Какво искаме тогава от тези числа, за да ги наречем псевдо-случайни?

  1. Искаме те да са сравнително добре разпръснати в даден регион. Нека си изберем региона [0;1].
  2. Искаме да не се повтарят. Защо? Защото в момента в който едно от числата се повтори, генераторът ще започне да плюе същите числа, както може да се види от формулата. Той ще стане цикличен.

Така, нека напишем набързо малко код в езика C#, който да прилага тази формула върху въведеното семе. Да не забравяме, че всеки път когато извадим ново число, то се превръща в новото семе

namespace LinearCongruentialGenerator {
  public static class LCG {
    public static ulong Next (ulong seed, ulong a, ulong c, ulong m) {
      return (seed * a + c) % m;
    }
  }
}

Добре, да видим как ще се справи нашият генератор със следните числа, въведени в него

семето \(X_1=1\), \(a=5, c=0, m=1024\)

Първо, този генератор ще вади числа от 1 до 1024, това е целта на \(m\). Затова, за да го нормализираме до [0;1], ще делим всички числа на 1024. Нека го накараме да ни извади 10000 числа и видим резултата:

timeseries

Хм, ами както виждаме, поне на пръв поглед числата покриват равномерно региона от 0 до 1, но имаме голям проблем - след определен брой числа (512 по-точно) генераторът започва да генерира абсолютно същите числа в абсолютно същия ред. Това е и основния проблем на този алгоритъм: ако не се подберат добри стойности за a, c и m, цикличността на числата става голяма.

Нека набързо разгледаме и други ефекти, които произлизат от лошия ни избор

running_averages_pointtype_0

Това е графика показваща средната стойност от всички генерирани числа \(\sum_i \frac{X_i}{N}\) спрямо броя на изтеглени числа N. Имайки предвид, че теглим числа от 0 до 1, можем да очакваме, при равномерно разпределение, средната им стойност да е 0,5, т.е. имаме точно толкова числа над 0,5, колкото и под. Интересна е цикличната зависимост на средната стойност спрямо изтегления брой числа. Да си припомним, че нашите числа се повтарят след всяко 512-то изтеглено такова. Готина графика, във всеки случай.

Но следващата наистина показва колко е нереално нашето изтегляне на числа. Ако сме изтеглили 512 числа, и им дадем на всяко номер \(i\in[0,511]\), можем да направим следната шашма: на х начертаем всички числа с нечетен индекс, т.е. \(i=1,3,5,...,511\), а на у всички числа с четен индекс: \(i=0,2,4,...,510\) , получаваме тази много интересна графика:

brilliant

Като цяло, може да се каже, че не сме се справили много добре в изтеглянето на псевдо-случайни числа, въпреки, че първият ни критерий е покрит. Нека набързо разгледаме добри практики за избирането на числата в алгоритъма:

  1. m е нашият модул, от него зависи максималното число, както и индиректно периодът на цикличност. Периодът не може да е по-голям от m. Обикновено се избира да е 2 на някаква степен n, сиреч \(2^n\)
  2. a e множител. Добре е той да е такъв, че \(a-1\) да е кратно на всички прости делители на m.
  3. c се избира така, че c и m да са взаимно прости.

Нека сега използваме следните стойности за нашите променливи: \(a = 25214903917, c=11, m=2^{48}\) и нормализираме отново в региона [0;1]. Това са стойностите, които използва генераторът drand48 в езика C++ и в Линукс. Нека проверим как се справяме с изтеглянето на 100000 числа:

white_noise

Тук сме изплюли 10 пъти повече числа от предния път, и въпреки това не се вижда никаква цикличност. Истински бял шум, причинен от изтеглянето на нашите метафорични бели зайци от шапката.

Заключение

Генерирането на числа, които да изглеждат като случайни е пипкава работа, но с малко нагласяне произвежда резултати, които да могат да задоволят нашите нужди. Другия път ще се опитаме да използваме това наше генериране за малко по-разчупени задачи, където са необходими случайни числа, а именно: Приблизително изчисляване на π.