Generování (pseudo)náhodných čísel

Generování (pseudo)náhodných čísel

Výkonnost a spolehlivost prog. systémů – KIV/VSS

Richard Lipka 27.9.2016

Co je náhodné číslo? VSS - Generování (pseudo)náhodných čísel

• Která posloupnost je náhodnější? – 010000101000101010 – 010101010101010101 – 000001111100000111 – 000000001111111111 • Jaké je nejnáhodnější číslo? • V praxi často věci, které nedokážeme dostatečně dobře předvídat („nahodnost“ = neschopnost odhadnout další hodnotu)

27.9.2016

2

Využití náhody •

Kryptografie

•

VSS - Generování (pseudo)náhodných čísel

– Tvorba dostatečně velkých náhodných klíčů v SSL  bez kvalitního zdroje náhody nelze zabezpečit komunikaci

Testování – Generování testovacích dat – Simulace chování uživatelů

•

Hry – Hazardní hry – Varianty v chování počítačového protivníka – Simulace prostředí

•

Matematické modelování a simulace – Metoda Monte Carlo, simulace

• •

Randomizace vzorků Rozhodování – „Athénská demokracie“ – čím víc losů tím větší šance

27.9.2016

3

Metoda Monte Carlo VSS - Generování (pseudo)náhodných čísel

• Simulační metoda založená na využití pseudonáhodných (nebo náhodných) čísel – Výpočty určitých integrálů a diferenciálních rovnic které nedokážu řešit analyticky – Modelování přírodních dějů (nukleární fyzika) s mnoha stupni volnosti (dokáži popsat dílčí děje a chci vidět jak vypadá výsledek) – Modelování dějů zahrnujících velkou míru nejistoty (lidské chování) – Optimalizace – Obecně jakýkoliv jev který lze popsat pravděpodobnostními metodami • První praktické využití – Stanislaw Ulam, modelování trajektorie neutronu při průchodu hmotou (1946?)

27.9.2016

4

Metoda Monte Carlo – obecný postup • Obecný postup: VSS - Generování (pseudo)náhodných čísel

• Odhad BMI v popupaci

– Definovat možné vstupy – popsat pravděpodobnostním rozdělením jevy a vztahy mezi nimi • Váha, výška, věk, pohlaví …

– Náhodně generovat vstupy s potřebným rozdělením • Pro každou hodnotu vlastní generátor (omezení velikosti a podobně)

– Vypočítat případné výsledky pro každou kombinací vstupů • Spočítat BMI každého člověka

– Provést agregaci výsledků • Určit BMI pro populaci jako střední hodnotu

 Potřebuji dostatek dostatečně náhodných čísel pro dostatek dílčích experimentů 27.9.2016

5

Metoda Monte Carlo – hodnota 𝜋

–


1. Nakreslím na podklad čtverec a vepsanou kružnici 2. Náhodně (rovnoměrně) házím do čtverce zrnka písku Generuji x a y souřadnice, důležitá je rovnoměrnost

3. Sečtu počet zrnek v kruhu a v celém čtverci 4. Poměr těchto hodnot je odhadem poměru jejich ploch –

Čím více hodnot, tím přesnější odhad

–

𝑆𝑘𝑟𝑢ℎ = 𝜋𝑟 2 𝑆č𝑡𝑣𝑒𝑟𝑒𝑐 = 𝑟 2

𝑆𝑘𝑟𝑢ℎ 𝑆č𝑡𝑣𝑒𝑟𝑒𝑐

=

𝜋𝑟 2 2𝑟 2

=

27.9.2016

𝜋 4

→𝜋=4

𝑆𝑘𝑟𝑢ℎ ∙ 𝑆č𝑡𝑣𝑒𝑟𝑒𝑐 6

Zdroje náhody 1.

Statické – tabulky –


2.

Potřebují nějaký zdroj pro prvotní tvorbu

Fyzikální generátory –

3.

„dostatečně náhodné“ přírodní jevy

Aritmetické metody – –

Náplň zbytku přednášky V současné době nejčastější

„Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.“ John von Neumann, 1951, Various techniques used in connection with random digits

27.9.2016

7

Tabulky náhodných čísel VSS - Generování (pseudo)náhodných čísel

A Million Random Digits with 100,000 Normal Deviates (1955, RAND corporation) • K dostání na Amazonu (cca 55$) • Generováno elektronickou ruletou

„Such a terrific reference work! But with so many terrific random digits, it's a shame they didn't sort them, to make it easier to find the one you're looking for.“ 27.9.2016

8

Fyzikální generátory •

– – – – –

•


Náhoda získána měřením nějakého reálného procesu Čítače částic / nukleární rozpad Tepelný šum, elektromagnetický šum Počasí Házení kostek, míchání karet …

Rychlost generátoru – Kolik náhodných bitů za jednotku času lze získat?  Někdy jako počátek pro pseudonáhodné generátory

•

Při opotřebení selhávají „tiše“ – Testovat opakovaně jejich výstup (např. RFC 4086)

•

Jevy které je velmi obtížné předvídat  využitelné v kryptografii 27.9.2016

9

/dev/random v Linuxu •

Zdroj náhody získané z jádra

• •

„Skutečná náhoda“ - lepší než jakýkoliv čistě aritmetický generátor, zamýšlené pro kryptografii Čtení je blokující  když nemá dost „náhody“, čeká až ji získá –

•

Odhaduje kolik náhody „zbývá“ v zásobníku

existuje i /dev/urandom – neblokující; považován za kryptograficky bezpečný zdroj (pokud je dost entropie na začátku, bude bezpečný pro dostatečně dlouhou řadu čísel) – –

•

časování diskových operací, stisknutí kláves a pohybů myši (podle implementace systému – může využívat teplotu CPU, audio vstup, ….)


–

stejný algoritmus, jen bez odhadu „zbývající náhody“ Je lepší sáhnout po něm než po /dev/random

/dev/hwrng pokud je k dispozici lepší HW generátor náhody (podrobná analýza implementace i vlastností v http://www.pinkas.net/PAPERS/gpr06.pdf)

•

Ve Windows CryptoAPI (uzavřené), GnuPG

27.9.2016

10

Pseudonáhodné generátory • Algebraické – definovány funkcí VSS - Generování (pseudo)náhodných čísel

– Posloupnost čísel, které „na první pohled“ vypadají náhodně (ale nejsou) – Z posloupnosti nejspíš nejde odvodit vlastnosti generátoru (nevyřešený problém - NP)

• Deterministické – musí dopadnout vždy stejně – Při stejné iniciaci (seed) dají vždy stejný výsledek (stejnou posloupnost) může a nemusí být užitečná vlastnost

• Konečné – Posloupnost se po nějaké době (periodě) začne opakovat

27.9.2016

11

Dobrý pseudonáhodný generátor Rychlý (/dev/random/ není moc rychlé) Malá spotřeba paměti Dlouhá perioda


• • •

– neopakuje se moc brzy, vyčerpá rozumnou část dostupných čísel – Ideálně může zopakovat stejné číslo před koncem periody

•

Replikovatelný – lze snadno získat tutéž posloupnost – Hodí se pro debugging a testování, pro tvorbu klíčů do DB a podobně (funkcionálně generované hry – stejný obsah ze stejného seed – Elite Dangerous)

•

Nezávislé hodnoty – Posloupnost projde testem statistické nezávislosti

(a dalšími testy – celá baterie je na http://stat.fsu.edu/pub/diehard/)

•

Odpovídá požadovanému rozdělení – Střední hodnota, odchylka, histogram 27.9.2016

12

Trocha statistiky • Nezbytné pro porozumění naměřeným hodnotám VSS - Generování (pseudo)náhodných čísel

– Jak moc jim mohu věřit, co doopravdy říkají?

• Náhodná veličina X – ?Je výsledek měření náhodný jev? – Měřitelná opakovatelně v čase, zpracovávaná statistickými metodami

• Charakteristiky – Střední hodnota – 𝐷 𝑋 (obvykle vážený průměr) – Rozptyl (střední kvadratická odchylka) - 𝐷 𝑋 = – Směrodatná odchylka - σ = 𝐷(𝑋) 27.9.2016

𝑛 𝑖=1

𝑥𝑖 − 𝐸(𝑋) 2 𝑝𝑖

13

Trocha statistiky – směrodatná odchylka VSS - Generování (pseudo)náhodných čísel

27.9.2016

14

Trocha statistiky – rozdělení VSS - Generování (pseudo)náhodných čísel

• Pravidlo přiřazující každému jevu určitou pravděpodobnost – Diskrétní veličina – Spojitá veličina

• Lepší charakteristika než střední hodnota nebo odchylka – Parametrizovatelné – Vím co od výsledků čekat – pokud tomu neodpovídají, vím že je něco špatně 27.9.2016

15

Diskrétní rozdělení VSS - Generování (pseudo)náhodných čísel

• Izolované jevy – Počet lidí kteří vešli do místnosti, počet lidí ve frontě, výsledek hodu mincí

• Pravděpodobnostní funkce 𝑃 𝑥 𝑛 𝑖=1

𝑃 𝑥𝑖 = 1

• (kumulativní) distribuční funkce 𝐹 𝑋 =𝑃 𝑋≤𝑥 =

𝑃 𝑡 𝑡≤𝑥 27.9.2016

16

Spojité rozdělení VSS - Generování (pseudo)náhodných čísel

• Spojité děje (popsatelné spojitou veličinou) – Teplota, tlak, rychlost, ….

• Hustota pravděpodobnosti ρ 𝑥 Ω

ρ 𝑥 𝑑𝑥 = 1, 𝑃 𝑥1 ≤ 𝑋 ≤ 𝑥2 =

• Distribuční funkce

𝑥2 ρ 𝑥1

𝑥 𝑑𝑥

𝑥

F 𝑋 =𝑃 𝑋≤𝑥 =

ρ 𝑡 𝑑𝑡 −∞

27.9.2016

17


• Hustota pravděpodobnosti (prvd. konkrétní hodnoty je vždy 0)

• Distribuční funkce

27.9.2016

18

Rovnoměrné rozdělení (Uniform distribution)

Hustota pravděpodobnosti 27.9.2016


• Základ pro ostatní generátory – Parametry: minimum a maximum – Hodnoty ze zadaného rozsahu se stejnou pravděpodobností – Obvykle v rozsahu 0, 1 - normalizovaná podoba (neplést s normálním rozdělením!)

Distribuční funkce Grafy: https://en.wikipedia.org/wiki/Uniform_distribution_(continuous)

19

Rovnoměrné rozdělení (Uniform distribution)

∞

𝑎+𝑏 𝐸𝑥 = 𝑥𝑓 𝑥 𝑑𝑥 = 2 −∞ Rozptyl: 2

=

1 (𝑏 − 𝑎)2 12 27.9.2016

𝑥

𝐹 𝑥 =𝑃 𝜇≤𝑥 =

𝑓 𝜇 𝑑𝜇 −∞

0 𝑥−𝑎 𝐹 𝑥 = 𝑏−𝑎 1

Střední hodnota:

D 𝑥 =𝐸 𝑥−𝐸 𝑥

Distrubuční funkce:


Hustota pravděpodobnosti: 1 𝑝𝑟𝑜 𝑎 ≤ 𝑦 ≤ 𝑏 𝑓 𝑥 = 𝑏−𝑎 0 𝑝𝑟𝑜 𝑥 < 𝑎 ∪ 𝑥 > 𝑏

𝑝𝑟𝑜 𝑥 < 𝑎 𝑝𝑟𝑜 𝑥 ∈ 𝑎, 𝑏

𝑝𝑟𝑜 𝑥 > 𝑏

Směrodatná odchylka: 𝑏−𝑎 2 𝜎= 𝐷𝑥 = 2 12 20

Kvazirovnoměrné rozdělení

Distribuční funkce pro n=2


• Diskrétní rozložení, pro zobrazení čísla na n bitech – Pokud je n dostatečně velké, lze ho použít jako aproximaci rovnoměrného rozložení (a v IT toho moc jiného nezbývá) Střední hodnota: 𝑎+𝑏 𝐸𝑥 = 2 Rozptyl: (𝑏 − 𝑎 + 1)2 −1 𝐷𝑥 = 12

1 0,75 0,5 0,25 0

0

0,25

0,5

0,75

1

27.9.2016

1,25

1,5

21

Generátor pseudonáhodného uniformního rozdělení – Lze snadno zobrazit v intervalu


• Generuje celé číslo na zobrazitelném rozsahu (n - 16, 32, 64 bitů) 2𝑛 −1 0, 𝑛 2

– Každou hodnotu by měl generátor dát se stejnou pravděpodobností – Po sobě jdoucí hodnoty statisticky nezávislé – Hodnoty velmi podobné uniformnímu rozdělení (kvazirovnoměrné rozdělení) – Podle potřeby lze dále transformovat 27.9.2016

22

Metoda prostředních řádů

– Sloužila urychlení výpočtu proti čtení náhodných čísel z děrných štítků – Těžké vybrat počáteční hodnotu která zajistí dlouhou periodu

1

2

3 27.9.2016

• Volba počáteční hodnoty 𝑦0 • n bitů / číslic


• Nejstarší známá (John von Neumann, 1949?, 1240?)

• 𝑦𝑡 = 𝑦𝑖−1 2 • 2n bitů / číslic

• Separujeme prostředních n bitů / číslic – dostaneme 𝑦1

23

Metoda prostředních řádů - příklad

2

3

• 𝑦𝑡 = 𝑦𝑖−1 2 • 2n bitů / číslic

• Separujeme prostředních n bitů / číslic – dostaneme 𝑦1

27.9.2016

• Pro jednoduchost v desítkové soustavě:


1

• Volba počáteční hodnoty 𝑦0 • n bitů / číslic

𝑋0 = 7182 𝑠𝑒𝑒𝑑 𝑋𝑡 = 𝑋02 = 51581124 𝑋1 = 5811 𝑅1 = 0.5811 𝑋𝑡 = 𝑋12 = 33767721 𝑋2 = 7767 𝑅2 = 0.7667 24

Metoda prostředních řádů - problém Nevhodný seed () vede ke krátké periodě Nuly mají sklon se hromadit a degenerovat posloupnost

𝑋0 = 6500 𝑠𝑒𝑒𝑑 𝑋𝑡 = 𝑋02 = 42250000 𝑋1 = 2500 𝑅1 = 0.2500 𝑋𝑡 = 𝑋12 = 06250000 𝑋2 = 2500 𝑅2 = 0.2500 27.9.2016


• •

𝑋0 = 5197 𝑠𝑒𝑒𝑑 𝑋𝑡 = 𝑋02 = 27008809 𝑋1 = 0088 𝑋𝑡 = 𝑋12 = 00007744 𝑋2 = 0077 𝑋𝑡 = 𝑋22 = 00005929 𝑋3 = 0059 25

Kongruentní metody (LCG – lineární kongruetní generátor) VSS - Generování (pseudo)náhodných čísel

• Lineární rovnice a modulo aritmetika  ideální pro počítače • Obecný tvar: 𝑦𝑖+1 = 𝑎𝑦𝑖 + 𝑐 𝑚𝑜𝑑 𝑚 – Varianty • 𝑐 = 0 – multiplikativní (Lehmerův generátor, 1949) • 𝑎 = 0 – aditivní

• Generuje celá čísla v rozsahu 0, 𝑚 − 1 𝑦 – Zobrazit do prostoru 0, 1 : 𝑟𝑖 = 𝑖, 𝑚 𝑏𝑖𝑡𝑟𝑎𝑡𝑒 – Přirozená volba 𝑚 = 2 - využít celý rozsah zobrazení čísel • Volba koeficientů a, c a m nemůže být náhodná – chceme co nejdelší periodu • Jednoduchá a snadno pochopitelná implementace 27.9.2016

26

Volba koeficientů – obecný LCG VSS - Generování (pseudo)náhodných čísel

𝑦𝑖+1 = 𝑎𝑦𝑖 + 𝑐 𝑚𝑜𝑑 𝑚 • Pro 𝑐 ≠ 0 a 𝑚 = 2𝑏 (b – velikost čísla v bitech) – Max. perioda: 𝑚 = 2𝑏 pokud platí že: • c a m jsou nesoudělná čísla • 𝑎 = 1 + 4𝑘, kde k je kladné celé číslo

27.9.2016

27

Volba koeficientů – multiplikativní generátor VSS - Generování (pseudo)náhodných čísel

𝑦𝑖+1 = 𝑎𝑦𝑖 𝑚𝑜𝑑 𝑚 • Pro ( 𝑐 = 0 ) a 𝑚 = 2𝑏 (b – velikost čísla v bitech) – Max. perioda: P = 2

𝑏−2

=

𝑚 4

pokud platí že:

• Seed (X0 ) je liché číslo • 𝑎 = 3 + 8𝑘 nebo 𝑎 = 5 + 8𝑘, kde k je kladné celé číslo

• Pro prvočíselné m (hodí se když neznám velikost čísla – vyšší jazyky) – Max. perioda: P = 𝑚 − 1 pokud platí že: • Nejmenší celočíselné k takové, že 𝑎𝑘 − 1 je dělitelné m musí být 𝑘 = 𝑚 − 1

27.9.2016

28

Volba koeficientů • Nevolte vlastní koeficienty pokud opravdu dobře nevíte co děláte VSS - Generování (pseudo)náhodných čísel

– Existují používané a dobře vyzkoušené hodnoty

• Pro šifrování vždy sáhněte po existujících bezpečných generátorech (v dokumentací obvykle označeno jestli jsou nebo nejsou vhodné pro kryptografii) – Špatná volba generátoru vede k nebezpečnému klíči – V Javě rychlý LCG generátor (java.util.Random) i pomalejší ale bezpečný kryptografický generátor (java.security.SecureRandom) využívající vhodnější PRNG (ne skutečnou náhodu!) 27.9.2016

29

Příklady koeficientů pro LCG Zdroj

m

c

Použité bity

GCC glibc

231

1103515245

12345

30..0

ISO/IEC 9899 (C 2011)

232

1103515245

12345

30..16

java.util.Random

248

25214903917

11

47...16

Apple CarbonLib

231 -1 16807

0

C Newlib, MUSL

264

6364136223846793005

1

Visual Basic

224

1140671485

12820163

27.9.2016


a

63...32

30

Problémy s LCG VSS - Generování (pseudo)náhodných čísel

• Mezi generovanými čísly stále existují korelace, byť ne zjevné – Při generování náhodných bodů budou výsledky ležet jen v některých rovinách

• Bity nižších řádů mají kratší periodu • Korelace mezi čísly 2𝑛 od sebe • Udržují svůj stav (obvykle jen 1 číslo) – Může vést k problémům (souběh, blokování) při paralelním programování 27.9.2016

31

LCG v Javě

27.9.2016


• Implementace otevřená, lze snadno dohledat • Pro seed používá 64b Long – Výpočet v Long aritmetice, posun >>> (48 – počet bitů) a vrátí požadovaný počet bitů zprava (max. 32) • Generuje 48 pseudonáhodných bitů a z toho – 32b Integer – 24b Float – 32b + 32b Long – 26b + 27b Double • Generování ve více bitech zlepšuje „náhodnost“ – Stejné číslo se může opakovat v rámci jedné periody – spodní bity jsou u LCG „méně náhodné“ – bitový posun je nahradí horními

32

Kombinované generátory • Využívá několik pseudonáhodných posloupností VSS - Generování (pseudo)náhodných čísel

– Čím víc generátorů, tím náročnější je generování na výpočetní zdroje! – Uniformní rozložení je základ pro další generátory (které mohou potřebovat několik uniformních hodnot pro svůj výsledek)

• Cílem je zlepšení statistické nezávislosti členů generované posloupnosti • Nejčastěji metoda smíšených generátorů (shuffling method) 27.9.2016

33

Metoda smíšených generátorů – 𝐺1 - rovnoměrné rozložení pro 0, 1 – 𝐺2 - diskrétní rovnoměrné rozložení 1..64 – Nezávislé (každý založen na své posloupnosti), s nesoudělnou periodou

• V generátoru pole ypam[1..64] – z něj náhodně vybírám a doplňuji 27.9.2016

V cyklu naplň ypam[i]  𝐺1


• 2 pseudonáhodné generátory

i 𝐺2

𝐺𝑟  ypam[i]

ypam[i]  𝐺1 34

Další předpisy generátorů VSS - Generování (pseudo)náhodných čísel

• Kvadratický kongruentní generátor 2 2 𝑦𝑖 = 𝑎1 𝑦𝑖−1 + 𝑎2 𝑦𝑖−1 + 𝑏 𝑚𝑜𝑑 𝐿 • Feedback shift generator – Založen na posuvném registru, snadná HW konstrukce – Pro tvorbu náhodných bitů 𝑐1 𝑎𝑘−1 + 𝑐2 𝑎𝑘−2 + … 𝑎𝑘 ; 𝑎𝑘 = 𝑚𝑜𝑑 2 +𝑐𝑝 𝑎𝑘−𝑝 • 𝑐1 − 𝑐𝑝 nesoudělná čísla  perioda 2𝑝 − 1 27.9.2016

35

Mersenne Twister

27.9.2016


• Nejrozšířenější současný PRNG – Knihovny C++, Common Lisp, MATLAB, PHP, Python, R, Mathematica, Excel, GNU Octave, Ruby, … • Výhody: – Velmi dlouhá perioda (219937 − 1) – Prochází většinou testů (včetně celé Diehard sady) • Nevýhody: – zabírá „hodně“ paměti (2,5 KiB místo jednoho čísla jako LCG) – Po startu s nevhodným seedem (mnoho nul) může trvat delší dobu než začne generovat použitelné hodnoty (pro podobné seedy budou posloupnosti nějakou dobu podobné) – Není kryptograficky bezpečný (existuje postup jak predikovat jeho výsledky z dostaečně dlouhé sekvence už známých hodnot) 36

Kryptograficky bezpečné PRNG • Test dalšího bitu VSS - Generování (pseudo)náhodných čísel

– Pokud znám prvních 𝑘 bitů posloupnosti, nesmí existovat polynomiální algoritmus který dokáže predikovat (𝑘 + 1) bit s pravděpodobností úspěchu lepší než 50%

• Odolnost proti odhalení stavu – Pokud odhalím stav generátoru, nelze z něj odvodit předcházející stavy (lze odvodit jen následující)  už zašifrovaná data nejsou kompromitována – Pro většinu PRNG problém, pokud znám jejich algoritmus

• Př. Generátor vrací prvky 𝜋 – Projde testem dalšího bitu (a řadou dalších – číslice 𝜋 jsou na sobě nezávislé) – Při odhalení stavu (když zjistím kde v 𝜋 jsem, můžu odvodit i předcházející bity)

27.9.2016

37

Konstrukce bezpečného RNG

27.9.2016


• Jen nástřel, nad rámec VSS (materiály na internetu v hojném množství) • Založené na existujících šifrách – Náhodným klíčem šifruji 0, 1, 2, 3, … (nebo jinou posloupnost) • Založené na „těžkých“ matematických problémech – Výpočet diskrétního logaritmu (𝑏 𝑘 = 𝑔, když znám 𝑏 a 𝑔, kolik je 𝑘?) – Faktorizace čísel (jaká prvočísla dají jako součin moje číslo?) • Speciální návrh – Yarrowův algoritmus (/dev/random) – kombinace jednosměrné hash funkce a blokové šifry (např SHA1 + DES), inicializován skutečnou náhodou – CryptGenRandom ve Windows – neznámá implementace, skutečná náhoda + MD4 hash (MD4 je hash pro kryptografické účely – řada dalších generátorů)

38

Ověření generátoru VSS - Generování (pseudo)náhodných čísel

• Lze hledat matematický důkaz pro požadované vlastnosti – Obecně obtížné, zvlášť pro každou metodu • Testovací sady se pokoušejí o útok na generátor – NIST testy: http://csrc.nist.gov/groups/ST/toolkit/rng/ – Fourmilab testy: http://www.fourmilab.ch/random/ – Diehard testy: http://stat.fsu.edu/pub/diehard/

• Online srovnání řady generátorů s výsledky (na základě alespoň 12MiB hodnot) http://www.cacert.at/cgi-bin/rngresults – Porovnává kvalitu, cenu, rychlost 27.9.2016

39

Generování dalších rozdělení VSS - Generování (pseudo)náhodných čísel

• Uniformní rozdělení obvykle nestačí, běžné děje se řídí jinými zákonitostmi (Gauss, Poisson, …) • Rovnoměrné rozdělení lze transformovat pro získání jiných rozdělení – Obvykle je potřeba víc hodnot

• Základní metody: – Transformační – založena na transformaci distribuční funkce – Vylučovací – založena na hustotě pravděpodobnosti

• Speciální metody pro některá rozdělení 27.9.2016

40

Transformační metoda • Použitelná jen pokud je známa VSS - Generování (pseudo)náhodných čísel

– Distribuční funkce cílového rozdělení – Její inverze (nemusí být vždy snadno zjistitelná)

• Pokud je 𝐹(𝑥) distribuční funkce a 𝐹 −1 (𝑢) odpovídající kvantilová funkce (=inverze distribuční funkce), pak pokud má náhodná veličina U rovnoměrné rozdělení 0, 1 , bude mít veličina 𝑋 = 𝐹 −1 (𝑈) rozdělení s distribuční funkcí 𝐹(𝑥) – Stačí generovat normované rovnoměrné rozdělení a transformovat podle 𝐹 −1 (𝑢) – Efektivní pokud je 𝐹 −1 (𝑢) rychle vypočitatelná a není těžké ji odvodit (nebo dohledat ) 27.9.2016

41

Transformační metoda – geometrická představa VSS - Generování (pseudo)náhodných čísel

https://community.qlik.com/blogs/qlikviewdesignblog/2013/08/26/monte-carlo-methods

27.9.2016

42

Vylučovací metoda VSS - Generování (pseudo)náhodných čísel

• Hodí se pokud je známa hustota pravděpodobnosti 𝑓(𝑥) – Obvykle je – definuje spojité rozložení

• Potřebuje 2 generátory (mohou sdílet posloupnost) – „souřadnice v prostoru“ – 𝐺1 - uniformní rozdělení na 𝑎, 𝑏 𝑥𝑖 = 𝑏 − 𝑎 𝑦1 + 𝑎 – transformace z 0, 1 – 𝐺2 - uniformní rozdělení na 0, 𝑀 𝑧𝑖 = 𝑀𝑦2 – Test 𝑧𝑖 ≤ 𝑓(𝑥𝑖 )

• ANO: 𝑥𝑖 je náhodné číslo ze souboru s rozdělením 𝑓(𝑥) • NE: opakuj, dokud není podmínka splněna 27.9.2016

43

Vylučovací metoda – geometrická představa VSS - Generování (pseudo)náhodných čísel

f(x)

M 𝑧𝑖′ f(x)

𝑧𝑖 0

a

b

𝑥𝑖

27.9.2016

x

44

Generování normálního rozdělení

𝑓 𝑥 =

1 2

𝜎 2𝜋

𝑒


• Lze využít některé speciální vlastnosti • Hustota pravděpodobnosti (𝑥−𝑎)2 − 2𝜎2

– a – střední hodnota – 𝜎 – směrodatná odchylka

• Hustota pravděpodobnosti pro normalizovanou podobu (𝑎 = 0, 𝜎 = 1) 𝑓 𝑧 =

1 2

2𝜋

𝑧2 𝑒− 2 ,

27.9.2016

𝑥−𝑎 𝑧= 𝜎 45

Generování normálního rozdělení – centrální limitní věta

– 𝐸 𝑠𝑛 = 𝑛𝐸 𝑦𝑖 =

– D 𝑠𝑛 = 𝑛𝐷 𝑦𝑖 =

𝑛 = 𝑎′ 2 𝑛 = 𝜎′ 12


• Součet n náhodných čísel s rovnoměrným rozdělením se asymptoticky (pro velké n) blíží k normálnímu rozdělení  generujeme a sčítáme 𝑦𝑖 • 𝑠𝑛 = 𝑛𝑖=1 𝑦𝑖 , hodí se volit 𝑛 = 12 12 =6 2 12 = =1 12

=

 Je snadné generovat Gaussovo rozdělení se střední hodnotou 6 a rozptylem 1 27.9.2016

46

Generování normálního rozdělení – transformace parametrů 𝑠𝑛 −

𝑛 2

= (𝑠𝑛 − 6)


• Veličina 𝑧 =

12 𝑛

– nulová střední hodnota, jednotkový rozptyl – Pro zadané 𝑎 a 𝜎: 𝑧=

𝑥−𝑎 𝜎

 𝑥 = 𝜎𝑧 + 𝑎 = σ

2

12 𝑛

𝑛 𝑖=1 𝑦𝑖

𝑛 − 2

+𝑎 =𝜎

12 𝑖=1 𝑦𝑖

−6 +𝑎

• Pro každé číslo s normálním rozdělením potřebuji 12 hodnot s rovnoměrným rozdělením (pořád rychlejší než předchozí metody – nepočítám 𝑓 𝑥 ani 𝐹 −1 (𝑥)) – Lze ještě rychleji 27.9.2016

47

Box-Müllerova transformace

27.9.2016


• Stačí dvě nezávislé hodnoty 𝑥1 , 𝑥2 s normovaným rovnoměrným rozdělením, pak platí, že: 2 𝑧1 = −2 ln 𝑥1 cos 2𝜋𝑥2 2 𝑧2 = −2 ln 𝑥1 sin 2𝜋𝑥2 jsou nezávislé náhodné veličiny s normovaným normálním rozdělením • Stačí 2 hodnoty, ale výpočet je náročnější (existuje řada dalších metod) • Implementována v Javě (java.util.Random.nextGaussian()) 48

Obecné diskrétní rozdělení VSS - Generování (pseudo)náhodných čísel

• Několik hodnot se známou pravděpodobností (může být různá) – Např. 1 – 30%, 2 – 50%, 3 – 20% (součet musí být 100%)

„Schodová“ distribuční funkce • Ekvivalent transformační metody – Generuji 1 náhodné číslo s normovaným uniformním rozdělením od do hodnota – Podle tabulky určím výslednou hodnotu

27.9.2016

0

0,3

1

0,3

0,8

2

0,8

1

3

49

Generování podle histogramu • Spojité rozdělení zadané histogramem (relativními četnostmi) VSS - Generování (pseudo)náhodných čísel

– Podobné jako předchozí případ – Distribuční funkce po částech lineární  jednotlivé části lze snadno transformovat

• Potřebuji – – – –

Počet intervalů Celkový počet vyhodnocovaných hodnot Velikost intervalu (může se lišit, neobvyklé) Počet čísel v každém intervalu (výšku sloupce)  lze určit relativní četnost 27.9.2016

50

Monte Carlo a generátory •

příjezdů) – Odbočování na křižovatkách (obecné diskrétní rozdělení) – Semafory (deterministické zastavování vozidel) – Chování řidičů (snaží se jet co nejrychleji když mají volnou cestu, dávají správně přednost v křižovatce)

Chci znát

𝑝1

1 − 𝑝1

G

– Intenzity provozu uprostřed modelované sítě (počty vozidel, délky front, …)

G

G

G

•


Znám rozložení dílčích událostí v systému – Příjezdy vozidel (exponenciální / poissonovo rozdělení dob

– Obecně jen další rozdělení, ale vypočítat jeho tvar ze známých charakteristik nedokážu  měřím v simulaci

27.9.2016

51

Testování generátoru VSS - Generování (pseudo)náhodných čísel

• Teoretické (analytické) vs. Empirické testy • Základ empirických testů: – Ověření zadaných vlastností (parametrů generátoru)  porovnání vypočtené hodnoty z tabulek s hodnotou naměřenou na výstupu – Střední hodnota, rozptyl nebo směrodatná odchylka, případně porovnání histogramu s hustotou pravděpodobnosti nebo pravděpodobnostní funkcí – Ověření délky periody – začnou se hodnoty opakovat?

27.9.2016

52

2

χ test – testování rovnoměrnosti VSS - Generování (pseudo)náhodných čísel

• Test hypotézy, zda je náhodně vybraný úsek generované posloupnosti 𝑦𝑖 1𝑛 je náhodným výběrem ze základního souboru 𝑦𝑖 s rovnoměrným rozložením v intervalu 0, 1 – Lze použít i pro jiná rozdělení (gauss, …) – Na základě známého rozdělení χ2 testuji neplatnost hypotézy (test „dokazuje“ že hypotéza neplatí nebo že ji nelze zamítnout – ne že platí)

27.9.2016

53

2

χ test – postup VSS - Generování (pseudo)náhodných čísel

1. Hodnoty z 𝑦𝑖 1𝑛 rozdělím podle velikosti do 𝑘 intervalů, v každém intervalu spočtu četnost 𝜗𝑖 , teoretickou pravděpodobnost že hodnota 𝑦𝑖 spadne do intervalu označím 𝑝𝑖 2. Míru odchylky od2 teoretického rozdělení vypočtu jako 𝜗𝑖 −𝑛𝑝𝑖 𝑘 2 χ = 𝑖=1 𝑛𝑝𝑖

3. Najdu tabulku pro χ2 s k-1 stupni volnosti 4. Pokud χ2 ≤ χ2𝑡𝑎𝑏 , testovanou hypotézu nelze zamítnout, pokud χ2 > χ2𝑡𝑎𝑏 jde o statisticky významný rozdíl a hypotézu zamítnu na dané hladině pravděpodobnosti 𝛼 27.9.2016

54

Užitečné zdroje VSS - Generování (pseudo)náhodných čísel

• Uncommons maths - http://maths.uncommons.org/ – Přesná matematika (Rational), kombinatorika, statistika, náhodná čísla

• Random.org - https://www.random.org/ – Skutečná náhodná čísla online

• NIST Computer security division http://csrc.nist.gov/groups/ST/toolkit/rng/index.html – Návody jak testovat kvalitu pseudonáhodných generátorů (standard) 27.9.2016

55

Děkuji za pozornost VSS - Generování (pseudo)náhodných čísel

• Příště Markovské procesy

27.9.2016

56

Generování (pseudo)náhodných čísel

Recommend Documents