Послідовність з низькою розбіжністю — послідовність, яка має таку властивість, що за всіх значень її підпослідовність має низьку розбіжність.
Грубо кажучи, розбіжність послідовності невелика, якщо частка її елементів, що потрапляють у довільну множину , близька до того, щоб бути пропорційною мірі множини , як це відбувалося б у середньому (але не для конкретних вибірок) у разі рівномірно розподіленої послідовності. Конкретні визначення розбіжності різняться залежно від вибору множини (гіперсфери, гіперкуба тощо), а також від того, як ця розбіжність обчислена (зазвичай нормалізовано) і скомбінована (зазвичай шляхом взяття найгіршого значення) для кожної множини .
Послідовності з низькою розбіжністю також називають квазівипадковими послідовностями через поширене їх використання як заміни рівномірно розподілених випадкових чисел. Префікс «квазі» використовується для точнішого позначення того, що значення послідовності з низькою розбіжністю не є ні [en], ні псевдовипадковими. Але, разом з тим, такі послідовності мають деякі властивості випадкових величин, і в певних застосуваннях, таких як метод квазі-Монте-Карло, їхня низька розбіжність є важливою перевагою.
Деякі застосування
Квазівипадкові числа мають перевагу перед суто випадковими числами в тому, що вони швидко й рівномірно охоплюють потрібну ділянку.
Одне з корисних застосувань полягає у знаходженні характеристичної функції для густини ймовірності. Квазівипадкові числа дозволяють досить швидко обчислювати з високою точністю моменти довільних порядків. Застосування, які не включають сортування, можна використати для знаходження середнього значення, стандартного відхилення, асиметрії та ексцесу статистичних розподілів, для знаходження інтегралів, а також глобальних максимумів та мінімумів складних детермінованих функцій. Квазівипадкові числа також можна використати для забезпечення початкових точок для детермінованих алгоритмів, які працюють тільки локально, таких як ітерація Ньютона — Рафсона.
Квазівипадкові числа також використовують у алгоритмах пошуку та сортування. За допомогою алгоритмів пошуку квазівипадкові числа можна використати в статистиці для знаходження моди, медіани, довірчих інтервалів та функцій розподілу.
Див. також
Література
- Кейперс Л., Нидеррайтер Г. Равномерное распределение последовательностей. — М. : Наука, 1985. — 408 с.
Це незавершена стаття з алгебри. Ви можете проєкту, виправивши або дописавши її. |
В іншому мовному розділі є повніша стаття Low-discrepancy sequence(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою з англійської.
|
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Poslidovnist z nizkoyu rozbizhnistyu poslidovnist yaka maye taku vlastivist sho za vsih znachen n displaystyle n yiyi pidposlidovnist s 1 s n displaystyle s 1 s n maye nizku rozbizhnist Grubo kazhuchi rozbizhnist poslidovnosti nevelika yaksho chastka yiyi elementiv sho potraplyayut u dovilnu mnozhinu B displaystyle B blizka do togo shob buti proporcijnoyu miri mnozhini B displaystyle B yak ce vidbuvalosya b u serednomu ale ne dlya konkretnih vibirok u razi rivnomirno rozpodilenoyi poslidovnosti Konkretni viznachennya rozbizhnosti riznyatsya zalezhno vid viboru mnozhini B displaystyle B gipersferi giperkuba tosho a takozh vid togo yak cya rozbizhnist obchislena zazvichaj normalizovano i skombinovana zazvichaj shlyahom vzyattya najgirshogo znachennya dlya kozhnoyi mnozhini B displaystyle B Poslidovnosti z nizkoyu rozbizhnistyu takozh nazivayut kvazivipadkovimi poslidovnostyami cherez poshirene yih vikoristannya yak zamini rivnomirno rozpodilenih vipadkovih chisel Prefiks kvazi vikoristovuyetsya dlya tochnishogo poznachennya togo sho znachennya poslidovnosti z nizkoyu rozbizhnistyu ne ye ni en ni psevdovipadkovimi Ale razom z tim taki poslidovnosti mayut deyaki vlastivosti vipadkovih velichin i v pevnih zastosuvannyah takih yak metod kvazi Monte Karlo yihnya nizka rozbizhnist ye vazhlivoyu perevagoyu Deyaki zastosuvannyaKvazivipadkovi chisla mayut perevagu pered suto vipadkovimi chislami v tomu sho voni shvidko j rivnomirno ohoplyuyut potribnu dilyanku Odne z korisnih zastosuvan polyagaye u znahodzhenni harakteristichnoyi funkciyi dlya gustini jmovirnosti Kvazivipadkovi chisla dozvolyayut dosit shvidko obchislyuvati z visokoyu tochnistyu momenti dovilnih poryadkiv Zastosuvannya yaki ne vklyuchayut sortuvannya mozhna vikoristati dlya znahodzhennya serednogo znachennya standartnogo vidhilennya asimetriyi ta ekscesu statistichnih rozpodiliv dlya znahodzhennya integraliv a takozh globalnih maksimumiv ta minimumiv skladnih determinovanih funkcij Kvazivipadkovi chisla takozh mozhna vikoristati dlya zabezpechennya pochatkovih tochok dlya determinovanih algoritmiv yaki pracyuyut tilki lokalno takih yak iteraciya Nyutona Rafsona Kvazivipadkovi chisla takozh vikoristovuyut u algoritmah poshuku ta sortuvannya Za dopomogoyu algoritmiv poshuku kvazivipadkovi chisla mozhna vikoristati v statistici dlya znahodzhennya modi mediani dovirchih intervaliv ta funkcij rozpodilu Div takozhRivnomirno rozpodilena poslidovnistLiteraturaKejpers L Niderrajter G Ravnomernoe raspredelenie posledovatelnostej M Nauka 1985 408 s Ce nezavershena stattya z algebri Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi V inshomu movnomu rozdili ye povnisha stattya Low discrepancy sequence angl Vi mozhete dopomogti rozshirivshi potochnu stattyu za dopomogoyu perekladu z anglijskoyi Divitis avtoperekladenu versiyu statti z movi anglijska Perekladach povinen rozumiti sho vidpovidalnist za kincevij vmist statti u Vikipediyi nese same avtor redaguvan Onlajn pereklad nadayetsya lishe yak korisnij instrument pereglyadu vmistu zrozumiloyu movoyu Ne vikoristovujte nevichitanij i nevidkorigovanij mashinnij pereklad u stattyah ukrayinskoyi Vikipediyi Mashinnij pereklad Google ye korisnoyu vidpravnoyu tochkoyu dlya perekladu ale perekladacham neobhidno vipravlyati pomilki ta pidtverdzhuvati tochnist perekladu a ne prosto skopiyuvati mashinnij pereklad do ukrayinskoyi Vikipediyi Ne perekladajte tekst yakij vidayetsya nedostovirnim abo neyakisnim Yaksho mozhlivo perevirte tekst za posilannyami podanimi v inshomovnij statti Dokladni rekomendaciyi div Vikipediya Pereklad