Umumlashtirilgan inversiv kongruentsiyali pseudorandom raqamlar - Generalized inversive congruential pseudorandom numbers

Ning chiziqli bo'lmagan konstruktiv usullariga yondoshish bir xil yolg'on tasodifiy sonlarni yaratish [0,1) oralig'ida Inversiv kongruent generator asosiy modul bilan. O'zboshimchalik bilan kompozit modullar uchun umumlashtirish ${ displaystyle m = p_ {1}, nuqta p_ {r}}$ o'zboshimchalik bilan ajralib turadi asosiy ${ displaystyle p_ {1}, dots, p_ {r} geq 5}$ bu erda bo'ladi.

Ruxsat bering ${ displaystyle mathbb {Z} _ {m} = {0,1, ..., m-1 }}$ . Uchun butun sonlar ${ displaystyle a, b in mathbb {Z} _ {m}}$ $ gcd (a, m) = 1 $ bilan umumlashtirilgan teskari mos keladigan ketma-ketlik ${ displaystyle (y_ {n}) _ {n geqslant 0}}$ elementlari ${ displaystyle mathbb {Z} _ {m}}$ bilan belgilanadi

{ displaystyle y_ {0} = { rm {seed}}}

{ displaystyle y_ {n + 1} equiv ay_ {n} ^ { varphi (m) -1} + b { pmod {m}} { text {,}} n geqslant 0}

qayerda ${ displaystyle varphi (m) = (p_ {1} -1) nuqtalar (p_ {r} -1)}$ dan kam musbat butun sonlar sonini bildiradi m qaysiki nisbatan asosiy ga m.

Misol

M = 15 = ni olaylik ${ displaystyle 3 times 5 , a = 2, b = 3}$ va ${ displaystyle y_ {0} = 1}$ . Shuning uchun ${ displaystyle varphi (m) = 2 marta 4 = 8 ,}$ va ketma-ketligi ${ displaystyle (y_ {n}) _ {n geqslant 0} = (1,5,13,2,4,7,1, nuqta)}$ maksimal emas.

Quyidagi natija shuni ko'rsatadiki, bu ketma-ketliklar asosiy modullar bilan quyidagi teskari mos keladigan ketma-ketlik bilan chambarchas bog'liq.

Uchun ${ displaystyle 1 leq i leq r}$ ruxsat bering ${ displaystyle mathbb {Z} _ {p_ {i}} = {0,1, dots, p_ {i} -1 }, m_ {i} = m / p_ {i}}$ va ${ displaystyle a_ {i}, b_ {i} in mathbb {Z} _ {p_ {i}}}$ bilan tamsayılar bo'ling

{ displaystyle a equiv m_ {i} ^ {2} a_ {i} { pmod {p_ {i}}} ; { text {and}} ; b equiv m_ {i} b_ {i} { pmod {p_ {i}}} { text {. }}}

Ruxsat bering ${ displaystyle (y_ {n}) _ {n geqslant 0}}$ elementlari ketma-ketligi bo'lishi ${ displaystyle mathbb {Z} _ {p_ {i}}}$ , tomonidan berilgan

{ displaystyle y_ {n + 1} ^ {(i)} equiv a_ {i} (y_ {n} ^ {(i)}) ^ {p_ {i} -2} + b_ {i} { pmod {p_ {i}}} ; { text {,}} n geqslant 0 ; { text {where}} ; y_ {0} equiv m_ {i} (y_ {0} ^ {(i )}) { pmod {p_ {i}}} ; { text {taxmin qilingan. }}}

Teorema 1

Ruxsat bering ${ displaystyle (y_ {n} ^ {(i)}) _ {n geqslant 0}}$ uchun ${ displaystyle 1 leq i leq r}$ yuqoridagi kabi belgilanishi kerak

{ displaystyle y_ {n} equiv m_ {1} y_ {n} ^ {(1)} + m_ {2} y_ {n} ^ {(2)} + dots + m_ {r} y_ {n} ^ {(r)} { pmod {m}}.}

Ushbu teorema shuni ko'rsatadiki, Umumiy Inversive Kongruential Generator-ni amalga oshirish mumkin, bu erda aniq sonli hisoblashlar faqat ${ displaystyle mathbb {Z} _ {p_ {1}}, dots, mathbb {Z} _ {p_ {r}}}$ lekin emas ${ displaystyle mathbb {Z} _ {m}.}$

Isbot:

Birinchidan, bunga rioya qiling ${ displaystyle m_ {i} equiv 0 { pmod {p_ {j}}}, ; { text {for}} ; i neq j,}$ va shuning uchun ${ displaystyle y_ {n} equiv m_ {1} y_ {n} ^ {(1)} + m_ {2} y_ {n} ^ {(2)} + dots + m_ {r} y_ {n} ^ {(r)} { pmod {m}}}$ agar va faqat agar ${ displaystyle y_ {n} equiv m_ {i} (y_ {n} ^ {(i)}) { pmod {p_ {i}}}}$ , uchun ${ displaystyle 1 leq i leq r}$ indüksiyonda ko'rsatiladi ${ displaystyle n geqslant 0}$ .

Buni eslang ${ displaystyle y_ {0} equiv m_ {i} (y_ {0} ^ {(i)}) { pmod {p_ {i}}}}$ uchun taxmin qilingan ${ displaystyle 1 leq i leq r}$ . Endi, deylik ${ displaystyle 1 leq i leq r}$ va ${ displaystyle y_ {n} equiv m_ {i} (y_ {n} ^ {(i)}) { pmod {p_ {i}}}}$ butun son uchun ${ displaystyle n geqslant 0}$ . Keyin to'g'ridan-to'g'ri hisob-kitoblar va Ferma teoremasi Yo'l bering

{ displaystyle y_ {n + 1} equiv ay_ {n} ^ { varphi (m) -1} + b equiv m_ {i} (a_ {i} m_ {i} ^ { varphi (m)} (y_ {n} ^ {(i)}) ^ { varphi (m) -1} + b_ {i}) equiv m_ {i} (a_ {i} (y_ {n} ^ {(i)} ) ^ {p_ {i} -2} + b_ {i}) equiv m_ {i} (y_ {n + 1} ^ {(i)}) { pmod {p_ {i}}}}

,

bu kerakli natijani anglatadi.

Umumlashtirilgan teskari kongressiyali psevdandom tasodifiy sonlar bir o'lchovda yaxshi taqsimlangan. Ularning statistik mustaqillik xususiyatlarini baholash uchun ishonchli nazariy yondashuv nomuvofiqlikka asoslangan s- soxta tasodifiy sonlarning juftliklari.

GIC Generatorining nomuvofiqlik chegaralari

Biz yozuvlardan foydalanamiz ${ displaystyle D_ {m} ^ {s} = D_ {m} (x_ {0}, nuqtalar, x_ {m} -1)}$ qayerda ${ displaystyle x_ {n} = (x_ {n}, x_ {n} +1, nuqta, x_ {n} + s-1)}$ $\in$ ${ displaystyle [0,1) ^ {s}}$ uchun umumiylashtirilgan teskari kongressiyali psevdordan tasodifiy sonlar ${ displaystyle s geq 2}$ .

Yuqori chegara

Ruxsat bering

{ displaystyle s geq 2}

Keyin nomuvofiqlik

{ displaystyle D_ {m} ^ {s}}

qondiradi

{ displaystyle D_ {m}}

{ displaystyle ^ {s}}

<

{ displaystyle m ^ {- 1/2}}

\times

{ displaystyle ({ frac {2} { pi}}}

\times

{ displaystyle log m + { frac {7} {5}}) ^ {s}}

\times

{ displaystyle textstyle prod _ {i = 1} ^ {r} (2s-2 + s (p_ {i}) ^ {- 1/2}) + s_ {m} ^ {- 1}}

har qanday umumlashtirilgan teskari kelishuv operatori uchun.

Pastki chegara:

Umumiy inversiv kelishuv generatorlari mavjud

{ displaystyle D_ {m}}

{ displaystyle ^ {s}}

\geq

{ displaystyle { frac {1} {2 ( pi +2)}}}

\times

{ displaystyle m ^ {- 1/2}}

:

\times

{ displaystyle textstyle prod _ {i = 1} ^ {r} ({ frac {p_ {i} -3} {p_ {i} -1}}) ^ {1/2}}

barcha o'lchovlar uchun s

:\geq

2.

Ruxsat etilgan raqam uchun r ning asosiy omillari m, 2-teorema shuni ko'rsatadiki ${ displaystyle D_ {m} ^ {(s)} = O (m ^ {- 1/2} ( log m) ^ {s})}$ har qanday umumlashtirilgan teskari kelishuvlar ketma-ketligi uchun. Bunday holda, Teorema 3, kelishmovchilikka ega bo'lgan Umumlashtirilgan Inversiv Kongruensial generatorlar mavjudligini anglatadi ${ displaystyle D_ {m} ^ {(s)}}$ bu hech bo'lmaganda kattalik tartibiga teng ${ displaystyle m ^ {- 1/2}}$ barcha o'lchovlar uchun ${ displaystyle s geq 2}$ . Ammo, agar m faqat kichik tub sonlardan tashkil topgan, keyin r kattalik tartibida bo'lishi mumkin ${ displaystyle ( log m) / log log m}$ va shuning uchun ${ displaystyle textstyle prod _ {i = 1} ^ {r} (2s-2 + s (p_ {i}) ^ {- 1/2}) = O {(m ^ { epsilon})}}$ har bir kishi uchun ${ displaystyle epsilon> 0}$ .^[1] Shuning uchun, bir kishi umumiy holatda oladi ${ displaystyle D_ {m} ^ {s} = O (m ^ {- 1/2 + epsilon})}$ har bir kishi uchun ${ displaystyle epsilon> 0}$ .

Beri ${ displaystyle textstyle prod _ {i = 1} ^ {r} ((p_ {i} -3) / (p_ {i} -1)) ^ {1/2} geqslant 2 ^ {- r / 2}}$ , shunga o'xshash dalillar shuni anglatadiki, umumiy holatda Teoremadagi pastki chegara hech bo'lmaganda kattalik tartibiga to'g'ri keladi ${ displaystyle m ^ {- 1/2- epsilon}}$ har bir kishi uchun ${ displaystyle epsilon> 0}$ . Aynan mana shu kattalik diapazoni deyarli har doim kattalik tartibiga ega bo'lgan m mustaqil va bir tekis taqsimlangan tasodifiy nuqtalarning nomuvofiqligini topadi. ${ displaystyle m ^ {- 1/2} ( log log m) ^ {1/2}}$ nomuvofiqliklar uchun takrorlangan logarifma qonuniga binoan.^[2] Shu ma'noda, Umumlashtirilgan Inversiv Kongressiyali Psevdo-tasodifiy sonlar haqiqiy tasodifiy sonlarni juda yaqin tarzda modellashtiradi.

Shuningdek qarang

Adabiyotlar

^ G. H. Xardi va E. M. Rayt, Raqamlar nazariyasiga kirish, 5-nashr, Clarendon Press, Oksford, 1979.
^ J. Kiefer, Empirik d.f.ning katta og'ishlari to'g'risida. Fo vektor tasodifiy o'zgaruvchilari va takrorlanadigan logaritma qonuni, PacificJ. Matematika. 11 (1961), 649-660-betlar.

Izohlar

Eyxenauer-Herrmann, Yurgen (1994), Umumlashtirilgan inversiv kongruent pseudorandom raqamlar to'g'risida (birinchi tahr.), Amerika Matematik Jamiyati, JSTOR 2153575

[one-1] G. H. Xardi va E. M. Rayt, Raqamlar nazariyasiga kirish, 5-nashr, Clarendon Press, Oksford, 1979.

[two-2] J. Kiefer, Empirik d.f.ning katta og'ishlari to'g'risida. Fo vektor tasodifiy o'zgaruvchilari va takrorlanadigan logaritma qonuni, PacificJ. Matematika. 11 (1961), 649-660-betlar.

[1]

[2]