تسلسل منخفض التباين

في الرياضيات ، المتتالية ذات التباين المنخفض هي متتالية تتميز بالخاصية التالية: لكل قيم${\displaystyle N}$، وتسلسلها الفرعي${\displaystyle x_{1},\ldots ,x_{N}}$يتميز بانخفاض التباين .

بصورة عامة، يكون التباين في متتالية ما منخفضًا إذا كانت نسبة النقاط في المتتالية التي تقع ضمن مجموعة عشوائية B قريبة من التناسب مع قياس B ، كما يحدث في المتوسط ​​(ولكن ليس لعينات محددة) في حالة المتتالية المتساوية التوزيع . تختلف التعريفات المحددة للتباين باختلاف اختيار B ( مثل الكرات الفائقة ، والمكعبات الفائقة ، وما إلى ذلك) وكيفية حساب التباين لكل B (عادةً ما يتم توحيده) ودمجه (عادةً بأخذ أسوأ قيمة).

تُسمى المتتاليات ذات التباين المنخفض أيضًا بالمتتاليات شبه العشوائية ، نظرًا لاستخدامها الشائع كبديل للأعداد العشوائية الموزعة توزيعًا منتظمًا . ويُستخدم مصطلح "شبه" للدلالة بشكل أوضح على أن قيم المتتالية ذات التباين المنخفض ليست عشوائية ولا شبه عشوائية ، ولكنها تشترك في بعض خصائص المتغيرات العشوائية، وفي تطبيقات معينة مثل طريقة مونت كارلو شبه العشوائية، يُعد انخفاض التباين فيها ميزة مهمة.

تتمتع الأرقام شبه العشوائية بميزة على الأرقام العشوائية البحتة من حيث أنها تغطي مجال الاهتمام بسرعة وبشكل متساوٍ.

يُستخدم هذا الأسلوب في تطبيقين مفيدين: إيجاد الدالة المميزة لدالة كثافة الاحتمال ، وإيجاد دالة المشتقة لدالة حتمية مع قدر ضئيل من التشويش. كما تُمكّن الأرقام شبه العشوائية من حساب العزوم ذات الرتب العليا بدقة عالية وبسرعة فائقة.

تشمل التطبيقات التي لا تتضمن الفرز إيجاد المتوسط ​​والانحراف المعياري والالتواء والتفرطح للتوزيع الإحصائي، وإيجاد القيم العظمى والصغرى التكاملية والعالمية للدوال الحتمية المعقدة. كما يمكن استخدام الأرقام شبه العشوائية لتوفير نقاط بداية للخوارزميات الحتمية التي تعمل محليًا فقط، مثل تكرار نيوتن- رافسون .

يمكن أيضًا دمج الأرقام شبه العشوائية مع خوارزميات البحث. وباستخدام خوارزمية البحث ، يمكن استخدام الأرقام شبه العشوائية لإيجاد المنوال والوسيط وفترات الثقة والتوزيع التراكمي لتوزيع إحصائي، بالإضافة إلى جميع القيم الصغرى المحلية وجميع حلول الدوال القطعية.

تباين مجموعة​${\displaystyle P=\{x_{1},\dots ,x_{N}}\}$يُعرَّف، باستخدام تدوين نيدررايتر ، على النحو التالي:$${\displaystyle D_{N}(P)=\sup _{B\in J}\left|{\frac {A(B;P)}{N}}-\lambda _{s}(B)\right|}$$

أين${\displaystyle \lambda _{s}}$هو${\displaystyle s}$مقياس ليبيغ ذو الأبعاد ، ${\displaystyle A(B;P)}$هو عدد النقاط في${\displaystyle P}$التي تندرج ضمن${\displaystyle B}$، و${\displaystyle J}$هي مجموعة${\displaystyle s}$فترات أو مربعات ذات أبعاد من الشكل

$${\displaystyle \prod _{i=1}^{s}[a_{i},b_{i})=\{\mathbf {x} \in \mathbf {R} ^{s}:a_{i}\leq x_{i}<b_{i}\}\,}$$

أين${\displaystyle 0\leq a_{i}<b_{i}\leq 1}$.

التباين النجمي${\displaystyle D_{N}^{*}(P)}$يتم تعريفها بشكل مشابه، باستثناء أن القيمة العليا تُؤخذ على المجموعة${\displaystyle J^{*}}$من الصناديق المستطيلة الشكل

$${\displaystyle \prod _{i=1}^{s}[0,u_{i})}$$

أين${\displaystyle u_{i}}$يقع في الفترة نصف المفتوحة [0، 1) .

يرتبط الاثنان بـ

$${\displaystyle D_{N}^{*}\leq D_{N}\leq 2^{s}D_{N}^{*}.\,}$$

ملاحظة : وفقًا لهذه التعريفات، يُمثل التباين أسوأ حالة أو أقصى انحراف في كثافة النقاط لمجموعة منتظمة. ومع ذلك، توجد أيضًا مقاييس خطأ أخرى ذات دلالة، مما يؤدي إلى تعريفات ومقاييس تباين أخرى. على سبيل المثال،${\displaystyle L^{2}}$-تباين أو توسيط معدل${\displaystyle L^{2}}$تُستخدم الفروقات أيضًا بكثافة لمقارنة جودة مجموعات النقاط الموحدة. وكلاهما أسهل بكثير في الحساب بالنسبة للمجموعات الكبيرة.${\displaystyle N}$و${\displaystyle s}$.

يترك${\displaystyle {\overline {I}}^{s}}$كن${\displaystyle s}$مكعب وحدة الأبعاد ،${\displaystyle {\overline {I}}^{s}=[0,1]\times \cdots \times [0,1]}$. يترك${\displaystyle f}$تباين محدود${\displaystyle V(f)}$على${\displaystyle {\overline {I}}^{s}}$بمعنى هاردي وكراوس. ثم لأي${\displaystyle x_{1},\ldots ,x_{N}}$في${\displaystyle I^{s}=[0,1)^{s}=[0,1)\times \cdots \times [0,1)}$،

$${\displaystyle \left|{\frac {1}{N}}\sum _{i=1}^{N}f(x_{i})-\int _{{\bar {I}}^{s}}f(u)\,du\right|\leq V(f)\,D_{N}^{*}(x_{1},\ldots ,x_{N}).}$$ تتميز متباينة كوكسما - هلاوكا بالدقة بالمعنى التالي: لأي مجموعة نقاط${\displaystyle \{x_{1},\ldots ,x_{N}\}}$في${\displaystyle I^{s}}$وأي${\displaystyle \varepsilon >0}$هناك وظيفة${\displaystyle f}$مع تباين محدود و${\displaystyle V(f)=1}$بحيث

$${\displaystyle \left|{\frac {1}{N}}\sum _{i=1}^{N}f(x_{i})-\int _{{\bar {I}}^{s}}f(u)\,du\right|>D_{N}^{*}(x_{1},\ldots ,x_{N})-\varepsilon .}$$

لذلك، فإن جودة قاعدة التكامل العددي تعتمد فقط على التباين${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})}$.

يترك${\displaystyle D=\{1,2,\ldots ,d\}}$. ل${\displaystyle \emptyset \neq u\subseteq D}$نكتب $${\displaystyle dx_{u}:=\prod _{j\in u}dx_{j}}$$ ويرمز بـ${\displaystyle (x_{u},1)}$النقطة التي تم الحصول عليها من x عن طريق استبدال الإحداثيات غير الموجودة في u بـ${\displaystyle 1}$. ثم

$${\displaystyle {\frac {1}{N}}\sum _{i=1}^{N}f(x_{i})-\int _{{\bar {I}}^{s}}f(u)\,du=\sum _{\emptyset \neq u\subseteq D}(-1)^{|u|}\int _{[0,1]^{|u|}}\operatorname {disc} (x_{u},1){\frac {\partial ^{|u|}}{\partial x_{u}}}f(x_{u},1)\,dx_{u},}$$

أين${\displaystyle \operatorname {disc} (z)={\frac {1}{N}}\sum _{i=1}^{N}\prod _{j=1}^{d}1_{[0,z_{j})}(x_{i,j})-\prod _{j=1}^{d}z_{i}}$هي دالة التباين.

بتطبيق متباينة كوشي-شفارتز للتكاملات والمجاميع على متطابقة هلاوكا-زاريمبا، نحصل على${\displaystyle L^{2}}$نسخة من عدم المساواة Koksma-Hlawka:

$${\displaystyle \left|{\frac {1}{N}}\sum _{i=1}^{N}f(x_{i})-\int _{{\bar {I}}^{s}}f(u)\,du\right|\leq \|f\|_{d}\operatorname {disc} _{d}(\{t_{i}\}),}$$

أين

$${\displaystyle \operatorname {disc} _{d}(\{t_{i}\})=\left(\sum _{\emptyset \neq u\subseteq D}\int _{[0,1]^{|u|}}\operatorname {disc} (x_{u},1)^{2}\,dx_{u}\right)^{1/2}}$$

و

$${\displaystyle \|f\|_{d}=\left(\sum _{u\subseteq D}\int _{[0,1]^{|u|}}\left|{\frac {\partial ^{|u|}}{\partial x_{u}}}f(x_{u},1)\right|^{2}dx_{u}\right)^{1/2}.}$$

${\displaystyle L^{2}}$يُعدّ التباين ذا أهمية عملية كبيرة لأنه يسمح بإجراء حسابات صريحة وسريعة لمجموعة نقاط معينة. وبهذه الطريقة، يسهل إنشاء مُحسِّنات لمجموعة النقاط باستخدام${\displaystyle L^{2}}$التناقض كمعيار.

يصعب حسابيًا إيجاد القيمة الدقيقة لاختلاف مجموعات النقاط الكبيرة. توفر متباينة إردوش - توران - كوكسما حدًا أعلى.

يترك${\displaystyle x_{1},\ldots ,x_{N}}$كن نقاطًا في${\displaystyle I^{s}}$و${\displaystyle H}$ليكن عددًا صحيحًا موجبًا كيفيًا.

$${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\leq \left({\frac {3}{2}}\right)^{s}\left({\frac {2}{H+1}}+\sum _{0<\|h\|_{\infty }\leq H}{\frac {1}{r(h)}}\left|{\frac {1}{N}}\sum _{n=1}^{N}e^{2\pi i\langle h,x_{n}\rangle }\right|\right)}$$

أين

$${\displaystyle r(h)=\prod _{i=1}^{s}\max\{1,|h_{i}|\}\quad {\text{for}}\quad h=(h_{1},\ldots ,h_{s})\in \mathbb {Z} ^{s}.}$$

الفرضية الأولى: يوجد ثابت${\displaystyle c_{s}}$يعتمد ذلك فقط على البُعد${\displaystyle s}$بحيث $${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq c_{s}{\frac {(\ln N)^{s-1}}{N}}}$$ لأي مجموعة نقاط منتهية${\displaystyle {x_{1},\ldots ,x_{N}}}$.

الفرضية الثانية: يوجد ثابت${\displaystyle c'_{s}}$يعتمد فقط على  :${\displaystyle s}$بحيث:${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq c'_{s}{\frac {(\ln N)^{s}}{N}}}$

لعدد لا نهائي من${\displaystyle N}$لأي متتالية لانهائية${\displaystyle x_{1},x_{2},x_{3},\ldots }$.

هذه الفرضيات متكافئة. وقد تم إثباتها لـ${\displaystyle s\leq 2}$بقلم دبليو إم شميدت . في الأبعاد الأعلى، لا تزال المشكلة المقابلة مفتوحة. تعود أفضل الحدود الدنيا المعروفة إلى مايكل لاسي وزملاؤه.

يترك${\displaystyle s=1}$. ثم

$${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq {\frac {1}{2N}}}$$

لأي مجموعة نقاط منتهية${\displaystyle \{x_{1},\dots ,x_{N}}\}$.

يترك${\displaystyle s=2}$أثبت دبليو إم شميدت أنه لأي مجموعة نقاط منتهية${\displaystyle \{x_{1},\dots ,x_{N}}\}$،

$${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq C{\frac {\log N}{N}}}$$

أين

$${\displaystyle C=\max _{a\geq 3}{\frac {1}{16}}{\frac {a-2}{a\log a}}=0.023335\dots .}$$

للأبعاد العشوائية${\displaystyle s>1}$أثبت كي إف روث ذلك

$${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq {\frac {1}{2^{4s}}}{\frac {1}{((s-1)\log 2)^{\frac {s-1}{2}}}}{\frac {\log ^{\frac {s-1}{2}}N}{N}}}$$

لأي مجموعة نقاط منتهية${\displaystyle \{x_{1},\dots ,x_{N}}\}$أثبت جوزيف بيك ^{[ 1 ]} تحسينًا لوغاريتميًا مزدوجًا لهذه النتيجة في ثلاثة أبعاد. وقد حسّنها د. بيليك وإم . تي. لاسي إلى قوة لوغاريتمية واحدة. أفضل حد معروف لـ s  >  2 يعود إلى د. بيليك وإم . تي. لاسي وأ. فاجارشاكيان. ^{[ 2 ]} يوجد${\displaystyle t>0}$اعتمادًا على s بحيث $${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq t{\frac {\log ^{{\frac {s-1}{2}}+t}N}{N}}}$$

لأي مجموعة نقاط منتهية ${\displaystyle \{x_{1},\dots ,x_{N}}\}$.

يمكن حساب الحد الأدنى العام للاختلاف المحلي المتوسط ​​باستخدام الحد الأدنى لحجم الفجوة وأحجام الفجوات التي تزيد عن متوسط ​​الفجوة ^{[ 3 ]} .

لأن أي توزيع للأرقام العشوائية يمكن تعيينه على توزيع منتظم، ويتم تعيين الأرقام شبه العشوائية بنفس الطريقة، فإن هذه المقالة تتعلق فقط بتوليد الأرقام شبه العشوائية على توزيع منتظم متعدد الأبعاد.

توجد تركيبات متسلسلة معروفة بحيث $${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\leq C{\frac {(\ln N)^{s}}{N}}.}$$ أين${\displaystyle C}$ثابت معين، يعتمد على المتتالية. بعد الفرضية الثانية، يُعتقد أن هذه المتتاليات تتمتع بأفضل رتبة تقارب ممكنة. من الأمثلة على ذلك متتالية فان دير كوربوت ، ومتتاليات هالتون ، ومتتاليات سوبول . أحد القيود العامة هو أن طرق البناء لا تضمن عادةً سوى رتبة التقارب. عمليًا، لا يمكن تحقيق تباين منخفض إلا إذا${\displaystyle N}$كبيرة بما يكفي، وبالنسبة لقيم s الكبيرة المعطاة، فإن هذا الحد الأدنى${\displaystyle N}$قد تكون كبيرة جدًا. وهذا يعني إجراء تحليل مونت كارلو باستخدام، على سبيل المثال،${\displaystyle s=20}$المتغيرات و${\displaystyle N=1000}$قد لا توفر النقاط من مولد تسلسل منخفض التباين سوى تحسين طفيف للغاية في الدقة .

أرقام عشوائية

يمكن توليد متواليات من الأرقام شبه العشوائية من الأرقام العشوائية عن طريق فرض ارتباط سلبي على تلك الأرقام العشوائية. إحدى طرق القيام بذلك هي البدء بمجموعة من الأرقام العشوائية.${\displaystyle r_{i}}$على${\displaystyle [0,0.5)}$وإنشاء أرقام شبه عشوائية${\displaystyle s_{i}}$وهي موحدة على${\displaystyle [0,1)}$استخدام:

${\displaystyle s_{i}=r_{i}}$ل${\displaystyle i}$غريب و${\displaystyle s_{i}=0.5+r_{i}}$ل${\displaystyle i}$حتى.

ثمة طريقة ثانية للقيام بذلك باستخدام الأرقام العشوائية الأولية، وهي إنشاء مسار عشوائي بإزاحة 0.5 كما يلي:

$${\displaystyle s_{i}=s_{i-1}+0.5+r_{i}{\pmod {1}}.\,}$$

أي، خذ الرقم شبه العشوائي السابق، أضف 0.5 والرقم العشوائي، واحصل على النتيجة بتردد  1.

بالنسبة لأكثر من بُعد واحد، يمكن استخدام المربعات اللاتينية ذات البُعد المناسب لتوفير إزاحات لضمان تغطية المجال بأكمله بالتساوي.

متتالية هالتون

تُعدّ متتالية هالتون تعميمًا طبيعيًا لمتتالية فان دير كوربوت إلى أبعاد أعلى. ليكن s بُعدًا اختياريًا، و _b₁ , ..., bₙ أعدادًا صحيحة أولية فيما بينها _أكبر من 1. عرّف

$${\displaystyle x(n)=(g_{b_{1}}(n),\dots ,g_{b_{s}}(n)).}$$

ثم يوجد ثابت C يعتمد فقط على b1 _، ...، bs _، بحيث تكون المتتالية { x ( n )}، حيث _{n ≥ 1،} متتالية ذات بُعد s .

$${\displaystyle D_{N}^{*}(x(1),\dots ,x(N))\leq C'{\frac {(\log N)^{s}}{N}}.}$$

مجموعة هامرسلي

يترك${\displaystyle b_{1},\ldots ,b_{s-1}}$ليكن عددان صحيحان موجبان أوليان فيما بينهما أكبر من 1.${\displaystyle s}$و${\displaystyle N}$، ال${\displaystyle s}$مجموعة هامرسلي متعددة الأبعاد${\displaystyle N}$يتم تعريفها بواسطة ^{[ 8 ]}

$${\displaystyle x(n)=\left(g_{b_{1}}(n),\dots ,g_{b_{s-1}}(n),{\frac {n}{N}}\right)}$$

ل${\displaystyle n=1,\ldots ,N}$. ثم

$${\displaystyle D_{N}^{*}(x(1),\dots ,x(N))\leq C{\frac {(\log N)^{s-1}}{N}}}$$

أين${\displaystyle C}$ثابت يعتمد فقط على${\displaystyle b_{1},\ldots ,b_{s-1}}$.

ملاحظة : تُظهر الصيغ أن مجموعة هامرسلي هي في الواقع متتالية هالتون، لكننا نحصل على بُعد إضافي مجانًا بإضافة مسح خطي. هذا ممكن فقط إذا ${\displaystyle N}$معروف مسبقًا. المجموعة الخطية هي أيضًا المجموعة ذات أقل تباين ممكن في بُعد واحد بشكل عام. لسوء الحظ، بالنسبة للأبعاد الأعلى، لا توجد مجموعات "سجلات التباين" هذه معروفة.${\displaystyle s=2}$معظم مولدات مجموعات النقاط ذات التباين المنخفض تقدم على الأقل تباينات شبه مثالية.

تمثل النقاط الموضحة أدناه أول 100 و1000 و10000 عنصر في متتالية من نوع سوبول. وللمقارنة، تم عرض 10000 عنصر من متتالية من النقاط شبه العشوائية. تم توليد متتالية التباين المنخفض باستخدام خوارزمية TOMS 659. ^{[ 10 ]} يتوفر تطبيق للخوارزمية بلغة فورتران من مكتبة Netlib .

أول 100 نقطة في متتالية ذات تباين منخفض من نوع سوبول .	أول 1000 نقطة في نفس التسلسل. تشكل هذه النقاط الألف أول 100 نقطة، بالإضافة إلى 900 نقطة أخرى.

أول 10000 نقطة في نفس التسلسل. هذه النقاط العشرة آلاف تشكل أول 1000 نقطة، بالإضافة إلى 9000 نقطة أخرى.	للمقارنة، إليكم أول 10000 نقطة في سلسلة من الأرقام شبه العشوائية الموزعة بشكل منتظم. وتظهر بوضوح مناطق ذات كثافة أعلى وأخرى ذات كثافة أقل.

• نظرية التناقض
• سلسلة ماركوف مونت كارلو
• طريقة شبه مونت كارلو
• شبكة متفرقة
• أخذ العينات المنتظم

• الخوارزميات المجمعة لجمعية ACM (انظر الخوارزميات 647 و 659 و 738).
• تسلسلات شبه عشوائية من مكتبة جنو العلمية
• تخضع عملية أخذ العينات شبه العشوائية للقيود في موقع FinancialMathematics.Com
• مولد متسلسلة سوبول بلغة C++
• مرجع واجهة برمجة تطبيقات SciPy QMC: scipy.stats.qmc