Výběr náhodného prvku z rovnoměrného rozdělení na
konečné množině pomocí náhodných bitů
Petr Savický, Malá Úpa, květen 2012
Úloha z webu na úvod
Nalezněte postup, jak pomocí několika hodů 5-ti stranné kostky
simulovat jeden hod 7-mi stranné kostky.
Hodem m stranné kostky rozumíme výběr z rovnoměrného
rozdělení na {1, ..., m}.
Generování náhodných permutací n prvků
Pro n = 1 vytvoříme permutaci 1.
Pokud máme náhodnou permutaci n − 1 prvků
π1 , . . . , πn−1 ,
lze ji n způsoby rozšířit na permutaci n prvků
n π1
...
πn−1
π1 n . . .
πn−1
π1
. . . n πn−1
π1
...
πn−1 n
Pokud vybereme z n možných pozic pro n z rovnoměrného
rozdělení, zachovává toto rozšíření rovnoměrné rozdělení na
příslušné množině permutací.
Výběr z rovnoměrného rozdělení na m prvcích
Generování náhodné permutace tedy lze převést na generování
náhodného prvku z {1, . . . , m} pro m = 2, . . . , n.
Obvyklý postup je použít ⌊m x˜⌋ + 1, kde x˜ je z “rovnoměrného”
rozdělení na [0, 1).
To obvykle znamená použití 32 nebo 53 náhodných bitů.
Pozorování 1. Pokud je m ≤ 1000, tak by mělo stačit zhruba 10
bitů, obecně zhruba log2 m.
Pozorování 2. Pokud m není mocnina dvojky, nestačí žádný
konečný počet bitů.
Rozdělit 2k možných kombinací k bitů na m stejně velkých částí
lze pouze tehdy, když m dělí 2k .
Příklad: výběr z {1, 2, 3}
vnitřní uzly - větvení podle náhodného bitu
listy - ohodnoceny {1, 2, 3}, obecně {1, . . . , m}
Počet bitů pro výběr z {1, 2, 3}
V jednom kroku generujeme dva bity, tedy máme 4 možné výsledky.
Pr(ukončení v jednom kroku) = p =
E(počet kroků) =
r (3) = E(počet bitů) =
3
4
1
4
=
p
3
8
= 2.666 . . .
3
r (m) bude střední hodnota počtu bitů pro výběr z {1, . . . , m}.
Protože r (4) = 2, je funkce r (m) nemonotonní.
Je nemonotonní i v mnoha dalších bodech, například r (5) > r (7).
4
3
2
1
r(m)
5
6
7
Graf r (m) pro 2 ≤ m ≤ 64
0
10
20
40
30
m
50
60
8
6
4
2
r(m)
10
12
14
Graf r (m) pro 2 ≤ m ≤ 214
0
10000
5000
m
15000
Výsledek
Minimální střední hodnota r (m) počtu bitů potřebných pro
rovnoměrné rozdělení na {1, . . . , m} splňuje
⌈log2 m⌉ ≤ r (m) < ⌈log2 m⌉ + 1
Pro m = 2k je r (m) rovno dolní mezi a současně
r (m) = log2 m
Pro m = 2k + 1 je r (m) blízké horní mezi a současně
r (m) = log2 m + 2 − o(1)
Popis stromu pomocí počtu listů na jednotlivých hladinách
Uzel v hloubce i je navštíven s pravděpodobností 2−i .
Označme ni počet listů v hloubce i ≥ 0 a L = {ni }i ≥0 .
Pravděpodobnost, že proces skončí v listu (součet
pravděpodobností disjunktních jevů)
p(L) =
∞
X
2−i ni ≤ 1
i =0
Věta. Posloupnost L je realizovatelná stromem právě tehdy, když
p(L) ≤ 1 .
Podmínka je zřejmě nutná.
To, že je postačující, ukážeme konstrukcí stromu.
Konstrukce stromu pro danou L
Nechť p(L) ≤ 1. Strom vytváříme po hladinách počínaje kořenem.
Počet uzlů na hladině i po odečtení počtu listů označme ui . Zřejmě
u0 = 1 − n0
ui +1 = 2 ui − ni +1
Řešením této rekurence je
ui = 2 −
i
i
X
2i −k nk .
k=0
Po úpravě a s využitím p(L) ≤ 1 dostaneme
!
i
X
2−k nk ≥ 2i (1 − p(L)) ≥ 0 .
ui = 2i 1 −
k=0
Střední hodnota počtu bitů
Pokud
p(L) =
∞
X
2−i ni = 1 ,
i =0
pak střední hodnota počtu použitých náhodných bitů
t(L) =
∞
X
i 2−i ni .
i =0
Hledáme stromy s malou hodnotou t(L), tedy nemusíme uvažovat
případy, kdy řada nekonverguje a tedy má součet nekonečno.
Poznámka. Řada nekonverguje například, když 2−i ni ∼
1
i (i +1) .
Rozlišení listů podle ohodnocení
(j)
Označme ni počet listů v hloubce i ohodnocených j a
(j)
Lj = {ni }i ≥0 , Zřejmě
m
X
Lj = L .
i =1
Pravděpodobnost, že proces skončí v listu ohodnoceném j je p(Lj ),
!
m
m
X
X
Lj = p(L) .
p(Lj ) = p
i =1
i =1
Příspěvek Lj do t(L) je t(Lj ) a platí
m
X
i =1
t(Lj ) = t
m
X
i =1
Lj
!
= t(L) .
Formulace úlohy
Mezi stromy, které splňují
p(L) = 1
p(Lj ) = 1/m
minimalizovat t(L) =
Pm
i =1 t(Lj ).
Protože libovolná kombinace posloupností Lj , které splňují
p(Lj ) = 1/m, odpovídá stromu, můžeme minimalizovat t(Lj ) pro
každý index j nezávisle.
Jestliže S = {ni }i ≥0 má minimální hodnotu t(S) při splnění
p(S) = 1/m, pak Lj = S pro j = 1, . . . , m je jedním z optimálních
řešení.
Minimum t(S) se nabývá pro jedinou posloupnost S, tedy Lj = S
je jediné optimální řešení.
Pravděpodobně stačí ni ≤ 1
Uvažujme posloupnost S = {ni }i ≥0 , která vyjadřuje počty listů
ohodnocené stejnou výstupní hodnotou.
Pokud pro některé i je ni ≥ 2, můžeme strom přeuspořádat tak,
aby dva listy na hladině i byly následníkem téhož uzlu.
Změnou tohoto uzlu na list a odstraněním jeho následníků
zachováme p(S) a snížíme t(S).
Horní a dolní binární rozvoj čísla
Pro čísla v základním tvaru p/2k , kde 0 < p < 2k lze uvažovat dva
binární rozvoje, jeden konečný a druhý nekonečný, které mají tvar
0.a1 a2 . . . ak−1 100000 . . .
0.a1 a2 . . . ak−1 011111 . . .
Horní rozvoj čísla α ∈ [0, 1] bude takový, že je konečný, pokud
existuje konečný rozvoj α.
Analogicky definujeme dolní rozvoj, který je vždy nekonečný.
Hladová vlastnost binárního rozvoje čísel z [0, 1]
Jestliže α ∈ [0, 1], S = {ni }i ≥0 je libovolná posloupnost
nezáporných celých čísel taková, že platí
α=
∞
X
2−i ni ,
i =0
pak S reprezentuje horní binární rozvoj α právě tehdy, když pro
každé k ≥ 0 je
k
X
2−i ni ≤ α (∗)
i =0
a levá strana je maximální možná mezi všemi posloupnostmi
nezáporných celých čísel ni pro i = 0, . . . , k, které splňují (∗).
Optimální strom je určen horním binárním rozvojem
Minimalizujeme t(S) za podmínky p(S) = 1/m. Platí
t(S) =
∞
X
i 2−i ni =
i =0
=
∞
X
k=0
∞
∞
X
X
2−i ni
k=0 i =k+1
k
1 X −i
2 ni
−
m
i =0
!
a víme, že pro každé k ≥ 0 platí
k
X
i =0
2−i ni ≤
1
.
m
Optimální posloupnost S = {ni }i ≥0 je tedy jednoznačně určena
horním binárním rozvojem 1/m.
Příklad: optimální strom pro m = 11
Binární rozvoj 1/11 má periodu 10.
1
= 0.(0001011101)∗
11
Algoritmus pro obecné m
k ← 1 // počet uzlů na aktuální hladině
x ← 0 // index navštíveného uzlu z {0, . . . , k − 1}
repeat {
k ←2∗k
x ← 2 ∗ x + randomBit()
if (k ≥ m) {
if (x ≥ k − m) {
output(x − (k − m) + 1) // ukončení cyklu
} else {
k ←k −m
}
}
}
Vyjádření r (m) pomocí fraktální funkce
Pro libovolné x ∈ [0, 1] nechť
w (x) =
∞
X
i 2−i ni ,
i =0
kde
x=
∞
X
2−i ni
i =0
je horní binární rozvoj x. Platí
r (m) = m w
1
m
.
Graf funkce w (x) pro x ∈ [0, 1] má fraktální podobu pravidelnější
než původní funkce r (m) pro m ∈ [2k−1 + 1, 2k ] pro velká k.
1.0
0.5
0.0
w(x)
1.5
2.0
Průběh funkce w (x)
0.0
0.2
0.6
0.4
x
0.8
1.0
Děkuji za pozornost.
Download

Výběr náhodného prvku z rovnoměrného rozdělení na konečné