Haltonova sekvence - Halton sequence
v statistika, Haltonovy sekvence jsou sekvence slouží ke generování bodů v prostoru pro numerické metody, jako např Simulace Monte Carlo. Ačkoli tyto sekvence jsou deterministický, jsou z nízký nesoulad, tj. se zdají být náhodný k mnoha účelům. Poprvé byly představeny v roce 1960 a jsou příkladem a kvazi-náhodné číslo sekvence. Zobecňují jednorozměrné van der Corputovy sekvence.
Příklad Haltonovy sekvence použité ke generování bodů v (0, 1) × (0, 1) v R.2
Haltonova sekvence je konstruována podle deterministické metody, která používá coprime čísla jako jeho základny. Jako jednoduchý příklad vezměme jednu dimenzi Haltonovy sekvence založenou na 2 a druhou na 3. Abychom vygenerovali sekvenci pro 2, začneme rozdělením intervalu (0,1) na polovinu, poté na čtvrtiny, osminy atd., který generuje
- 1⁄2, 1⁄4, 3⁄4, 1⁄8, 5⁄8, 3⁄8, 7⁄8, 1⁄16, 9⁄16,...
Ekvivalentně je n-té číslo této posloupnosti číslo n zapsané v binární reprezentaci, převrácené a zapsané za desetinnou čárkou. To platí pro každou základnu. Jako příklad, abychom našli šestý prvek výše uvedené sekvence, napíšeme 6 = 1 * 22 + 1*21 + 0*20 = 1102, které lze převrátit a umístit za desetinnou čárku na 0,0112 = 0*2-1 + 1*2-2 + 1*2-3 = 3⁄8. Sekvence výše je tedy stejná jako
- 0.12, 0.012, 0.112, 0.0012, 0.1012, 0.0112, 0.1112, 0.00012, 0.10012,...
Abychom vygenerovali sekvenci pro 3, rozdělíme interval (0,1) na třetiny, pak devátiny, dvacáté sedminy atd., Které generují
- 1⁄3, 2⁄3, 1⁄9, 4⁄9, 7⁄9, 2⁄9, 5⁄9, 8⁄9, 1⁄27,...
Když je spárujeme, dostaneme posloupnost bodů v jednotkovém čtverci:
- (1⁄2, 1⁄3), (1⁄4, 2⁄3), (3⁄4, 1⁄9), (1⁄8, 4⁄9), (5⁄8, 7⁄9), (3⁄8, 2⁄9), (7⁄8, 5⁄9), (1⁄16, 8⁄9), (9⁄16, 1⁄27).
I když standardní Haltonovy sekvence fungují velmi dobře v nízkých rozměrech, byly zaznamenány problémy s korelací mezi sekvencemi generovanými z vyšších prvočísel. Například pokud jsme začali s prvočísly 17 a 19, prvních 16 párů bodů: (1⁄17, 1⁄19), (2⁄17, 2⁄19), (3⁄17, 3⁄19) ... (16⁄17, 16⁄19) by bylo perfektní lineární korelace. Aby se tomu zabránilo, je běžné upustit prvních 20 položek nebo jiné předem stanovené množství v závislosti na zvolených prvočíslech. Bylo také navrženo několik dalších metod. Jedním z nejvýznamnějších řešení je zakódovaná Haltonova sekvence, která využívá permutace koeficientů použitých při konstrukci standardní sekvence. Dalším řešením je vyskočený Halton, který přeskakuje body ve standardní posloupnosti. Použitím např. Pouze každého 409. bodu (jsou možná i další prvočísla nepoužívaná v Haltonově základní sekvenci) lze dosáhnout významných zlepšení.[1]
Implementace v pseudokódu
algoritmus Haltonova sekvence je vstupy: index základna výstup: výsledek zatímco dělat vrátit se
Viz také
Reference
- ^ Kocis a Whiten, 1997
- Kuipers, L .; Niederreiter, H. (2005), Rovnoměrné rozdělení sekvencí, Dover Publications, str. 129, ISBN 0-486-45019-8
- Niederreiter, Harald (1992), Generování náhodných čísel a metody kvazi-Monte Carla, SIAM, str. 29, ISBN 0-89871-295-5.
- Halton, J. (1964), „Algorithm 247: Radical-inverse quasi-random point sequence“, Komunikace ACM, 7: 701-701, doi:10.1145/355588.365104.
- Kočiš, Ladislav; Whiten, William (1997), „Výpočetní vyšetřování sekvencí s nízkou odchylkou“, Transakce ACM na matematickém softwaru, 23: 266-296, doi:10.1145/264029.264064.