متتالية عشوائية خوارزمياً

قالب:Distinguish-redirect intuitively, تسلسل عشوائي خوارزمي (أو تسلسل عشوائي) هو تسلسل من الأرقام الثنائية يبدو عشوائيًا لأي خوارزمية تعمل على آلة تورينغ شاملة (غير محددة أو محددة) . يمكن تطبيق هذا المفهوم بشكل مشابه على التسلسلات على أي أبجدية محدودة (مثل الأرقام العشرية). التسلسلات العشوائية هي موضوعات رئيسية للدراسة في نظرية المعلومات الخوارزمية.

في نظرية الاحتمالات النظرية للقياس، التي قدمها أندريه كولموغوروف في عام 1933، لا يوجد شيء يسمى تسلسل عشوائي. على سبيل المثال، ضع في اعتبارك قلب عملة عادلة عدد لا نهائي من المرات. أي تسلسل معين، سواء كان $0000\dots$ أو $011010\dots$، لديه احتمال متساوٍ تقريبًا صفر. لا توجد طريقة للتعبير عن أن تسلسلًا واحدًا "أكثر عشوائية" من تسلسل آخر، باستخدام لغة نظرية القياس. ومع ذلك، من الواضح بديهيًا أن $011010\dots$ يبدو أكثر عشوائية من $0000\dots$. نظرية العشوائية الخوارزمية تُشكل هذه البديهية بشكل رسمي.

نظرًا لأن أنواع مختلفة من الخوارزميات تُعتبر أحيانًا، بدءًا من الخوارزميات ذات الحدود المحددة على وقت تشغيلها إلى الخوارزميات التي قد تسأل أسئلة من آلة الأورacle، هناك مفاهيم مختلفة للعشوائية. الأكثر شيوعًا من هذه تُعرف باسم عشوائية مارتن-لوف (K-عشوائية أو 1-عشوائية)، ولكن توجد أيضًا أشكال أقوى وأضعف من العشوائية. عندما يُستخدم مصطلح "عشوائي خوارزمي" للإشارة إلى تسلسل معين (نهائي أو غير نهائي) دون توضيح، يُفترض عادةً أنه يعني "غير قابل للضغط" أو، في حالة التسلسل غير النهائي وعشوائي خوارزميًا (أي، K-غير قابل للضغط)، "عشوائي مارتن-لوف-تشايتين".

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

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

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

تُرمز فئة جميع التسلسلات العشوائية (الثنائية) لمارتن-لوف بـ RAND أو MLR.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 التاريخ

 ريتشارد فون ميزس

ريتشارد فون ميسيس قام بتعريف مفهوم اختبار العشوائية لتحديد تسلسل عشوائي على أنه ذلك الذي يجتاز جميع اختبارات العشوائية. وقد عرّف "الجامع" (kollektiv) على أنه سلسلة ثنائية لا نهائية $x_{1:\infty }$ المعرفة بالشكل التالي:

• يوجد حد $\lim _{n}{\frac {1}{n}}\sum _{i=1}^{n}x_{i}=p\in (0,1)$.
• لأي قاعدة "مقبولة"، بحيث تختار سلسلة فرعية لا نهائية $(x_{m_{i}})_{i}$ من السلسلة، يبقى لدينا $\lim _{n}{\frac {1}{n}}\sum _{i=1}^{n}x_{m_{i}}=p$. وقد أطلق على هذا المبدأ "استحالة نظام المراهنة".

لاختيار سلسلة فرعية، يتم أولاً اختيار دالة ثنائية $\phi$، بحيث تعطي أي سلسلة ثنائية $x_{1:k}$ نتيجة إما 0 أو 1. إذا أعطت نتيجة 1، نضيف $x_{k+1}$ إلى السلسلة الفرعية، وإلا نتابع. في هذا التعريف، قد تمتنع بعض القواعد المقبولة إلى الأبد على بعض التسلسلات، وبالتالي تفشل في اختيار سلسلة فرعية لا نهائية. نحن نعتبر فقط تلك التي تختار سلسلة فرعية لا نهائية.

بعبارة أخرى، كل سلسلة ثنائية لا نهائية هي لعبة رمي عملة، وقاعدة مقبولة هي وسيلة للاعب قمار ليتخذ قرارًا متى يراهن. الجامع هو لعبة رمي عملة حيث لا يوجد طريقة للاعب قمار واحد أن يتفوق على الآخر على المدى الطويل. أي أنه لا يوجد نظام مراهنة يعمل في هذه اللعبة.

يمكن تعميم التعريف من الأبجدية الثنائية إلى الأبجدية القابلة للعد:

• تقترب تكرارات كل حرف من حد أكبر من الصفر.
• لأي قاعدة "مقبولة"، بحيث تختار سلسلة فرعية لا نهائية $(x_{m_{i}})_{i}$ من السلسلة، فإن تكرار كل حرف في السلسلة الفرعية لا يزال يقترب من نفس الحد.

عادة ما تُعرف القواعد المقبولة بأنها قواعد قابلة للحساب بواسطة آلة تورينغ، ونطلب أن يكون $p=1/2$. مع هذا، نحصل على تسلسلات ميسيس-والد-تشيرش العشوائية. هذا ليس تقييدًا، حيث يمكننا بناء تسلسلات عشوائية مع أي $p\in (0,1)$ قابل للحساب.

نظرية (أبراهام والد، 1936، 1937) إذا كان هناك عدد قابل للعد فقط من القواعد المقبولة، فإن أي تسلسل تقريبًا هو جامع.

مخطط الإثبات: استخدم الاحتمالات النظرية.

ثبّت قاعدة مقبولة واحدة. عيّن تسلسل عشوائي من فضاء برنولي. مع احتمال 1 (استخدم المارتينغالات)، لا يزال للسلسلة الفرعية التي اختارتها القاعدة المقبولة $\lim _{n}{\frac {1}{n}}\sum _{i=1}^{n}x_{m_{i}}=p$. الآن أضف جميع القواعد القابلة للعد. مع احتمال 1، لا يزال لكل سلسلة فرعية اختارها كل قاعدة $\lim _{n}{\frac {1}{n}}\sum _{i=1}^{n}x_{m_{i}}=p$.

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

بناء فيل (جان فيل، 1939) هناك جامع مع عدد قابل للعد من القواعد المقبولة بحيث، لكل $n$، ${\frac {1}{n}}\sum _{k=1}^{n}x_{k}\leq p$.

 پر مارتن-لوف

إن بناء فيل يشير إلى أن مفهوم العشوائية وفقاً لميسيس-والد-تشيرش ليس كافياً، لأن بعض التسلسلات العشوائية لا تلبي بعض قوانين العشوائية. على سبيل المثال، لا يفي بناء فيل بأحد قوانين اللوغاريتم المتكرر:

$$\limsup _{n\to \infty }{\frac {-\sum _{k=1}^{n}(x_{k}-1/2)}{\sqrt {2n\log \log n}}}\neq 1$$

بشكل ساذج، يمكن إصلاح ذلك عن طريق طلب أن تلبي السلسلة جميع قوانين العشوائية الممكنة، حيث أن "قانون العشوائية" هو خاصية يتم تلبية من قبل جميع التسلسلات باحتمالية 1. ومع ذلك، لكل سلسلة لا نهائية $y_{1:\infty }\in 2^{\mathbb {N} }$، لدينا قانون عشوائية ينص على أن $x_{1:\infty }\neq y_{1:\infty }$، مما يؤدي إلى الاستنتاج بأنه لا توجد تسلسلات عشوائية.

بير مارتن-لوف (1966) عرّف "عشوائية مارتن-لوف" من خلال السماح فقط بقوانين العشوائية القابلة للحساب بواسطة آلة تورينغ. بعبارة أخرى، تكون السلسلة عشوائية إذا وفقط إذا اجتازت جميع اختبارات العشوائية القابلة للحساب بواسطة تورينغ.

لقد أطلق على الأطروحة التي تفيد بأن تعريف عشوائية مارتن-لوف "يلتقط بشكل صحيح" الفكرة البديهية للعشوائية اسم أطروحة مارتن-لوف-تشايتين; وهي مشابهة إلى حد ما لـ أطروحة تشيرش-تورينغ.

أطروحة مارتن-لوف-تشايتين. المفهوم الرياضي لـ "عشوائية مارتن-لوف" يلتقط الفكرة البديهية بأن سلسلة لا نهائية تكون "عشوائية".

أطروحة تشيرش-تورينغ. المفهوم الرياضي لـ "القابلية للحساب بواسطة آلات تورينغ" يلتقط الفكرة البديهية بأن دالة تكون "قابلة للحساب". مثلما أن القابلية للحساب بواسطة تورينغ لها العديد من التعريفات المعادلة، فإن عشوائية مارتن-لوف أيضاً لها العديد من التعريفات المعادلة. انظر القسم التالي.

كان التعريف الأصلي لمارتن-لوف للتسلسل العشوائي من حيث الأغطية الفارغة البناءة؛ حيث عرّف تسلسلاً بعشوائي إذا لم يكن موجودًا في أي غطاء من هذا القبيل. جريگوري چايتين، ليونيد ليفين وكلاوس-پيتر شنور قدموا توصيفًا من حيث التعقيد الخوارزمي: التسلسل عشوائي إذا كان هناك حد موحد لضغط أجزائه الأولية. شنور قدم تعريفًا ثالثًا معادلًا من حيث مارتينجال. كتاب لي وڤيتاني "مقدمة في تعقيد كولموگوروف وتطبيقاته" هو المدخل القياسي لهذه الأفكار.

• التعقيد الخوارزمي (چايتين 1969، شنور 1973، ليفين 1973): يمكن اعتبار التعقيد الخوارزمي (المعروف أيضًا باسم تعقيد كولموگوروف أو تعقيد حجم البرنامج) كحد أدنى لضغط الخوارزمي لتسلسل محدود (من الحروف أو الأرقام الثنائية). يعين لكل تسلسل من هذا النوع w عددًا طبيعيًا K(w) يقيس بشكل بديهي الطول الأدنى لبرنامج حاسوبي (مكتوب بلغة برمجة ثابتة) لا يأخذ أي مدخلات وسيخرج w عند تشغيله. يتطلب التعقيد أن يكون خاليًا من البادئات: يتبع البرنامج (تسلسل من 0 و 1) بسلسلة لا نهاية لها من الأصفار، ويتضمن طول البرنامج (بافتراض توقفه) عدد الأصفار إلى يمين البرنامج التي يقرأها آلة تورينغ العالمية. الحاجة إلى المتطلب الإضافي هو أننا يمكن أن نختار طولًا بحيث يشفر الطول معلومات حول الجزء الفرعي. بالنظر إلى عدد طبيعي c وتسلسل w، نقول إن w هو c-غير قابل للضغط إذا $K(w)\geq |w|-c$.

تكون السلسلة اللانهائية S عشوائية مارتن-لوف إذا وفقط إذا كان هناك ثابت c بحيث تكون جميع البادئات المحدودة الخاصة بـ S غير قابلة للضغط بمعامل c. بشكل أكثر إيجازًا، $K(w)\geq |w|-O(1)$.

• الأغطية الفارغة البناءة (مارتن-لوف 1966): هذا هو التعريف الأصلي لمارتن-لوف. بالنسبة لسلسلة ثنائية محدودة w نسمح لـ C_w بتمثيل الأسطوانة المولدة بواسطة w. هذه هي مجموعة جميع السلاسل اللانهائية التي تبدأ بـ w، وهي مجموعة مفتوحة أساسية في فضاء كانتور. يتم تعريف مقياس المنتج μ(C_w) للأسطوانة المولدة بواسطة w ليكون 2^−|w|. كل مجموعة مفتوحة في فضاء كانتور هي اتحاد لتسلسل قابل للعد من مجموعات مفتوحة أساسية منفصلة، ومقياس مجموعة مفتوحة هو مجموع مقاييس أي تسلسل من هذا القبيل. المجموعة المفتوحة الفعالة هي مجموعة مفتوحة تكون اتحاد لتسلسل مجموعات مفتوحة أساسية يحدده تسلسل من السلاسل الثنائية القابلة للحساب بشكل متكرر. غطاء فارغ بناء أو مجموعة فعالة ذات مقياس 0 هي تسلسل قابل للحساب بشكل متكرر $U_{i}$ من مجموعات مفتوحة فعالة بحيث $U_{i+1}\subseteq U_{i}$ و$\mu (U_{i})\leq 2^{-i}$ لكل عدد طبيعي i. كل غطاء فارغ فعال يحدد مجموعة G-دلتا ذات مقياس 0، وهي تقاطع المجموعات $U_{i}$.

يتم تعريف السلسلة بأنها عشوائية مارتن-لوف إذا لم تكن موجودة في أي مجموعة $G_{\delta }$ تم تحديدها بواسطة غطاء فارغ بناء.

• المارتينجالات البناءة (شنور 1971): المارتينجال هو دالة $d:\{0,1\}^{*}\to [0,\infty )$ بحيث، لكل السلاسل المحدودة w، $d(w)=(d(w^{\smallfrown }0)+d(w^{\smallfrown }1))/2$، حيث $a^{\smallfrown }b$ هو التسلسل للسلاسل a وb. وهذا ما يسمى بشرط "العدالة": إذا تم اعتبار المارتينجال كإستراتيجية مراهنة، فإن الشرط أعلاه يتطلب أن يلعب المراهن ضد احتمالات عادلة. يقال أن المارتينجال d ينجح في سلسلة S إذا $\limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,$ حيث $S\upharpoonright n$ هي أول n بتات من S. المارتينجال d هو بناء (المعروف أيضًا باسم قابل للحساب بشكل ضعيف, قابل للحساب السفلي) إذا كانت هناك دالة قابلة للحساب ${\widehat {d}}:\{0,1\}^{*}\times \mathbb {N} \to {\mathbb {Q} }$ بحيث، لكل السلاسل الثنائية المحدودة w

1. ${\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),$ لكل الأعداد الصحيحة الموجبة t,

1. $\lim _{t\to \infty }{\widehat {d}}(w,t)=d(w).$

السلسلة عشوائية مارتن-لوف إذا وفقط إذا لم ينجح أي مارتينجال بناء عليه.

 تفسيرات التعريفات

توصيف تعقيد كولموگوروف ينقل الفكرة بأن التسلسل العشوائي غير قابل للضغط: لا يمكن إنتاج أي بادئة بواسطة برنامج أقصر بكثير من البادئة نفسها.

توصيف الغطاء الفارغ ينقل الفكرة بأن الرقم الحقيقي العشوائي لا يجب أن يكون له أي خاصية "غير شائعة". يمكن اعتبار كل مجموعة ذات مقياس 0 كخاصية غير شائعة. ليس من الممكن لتسلسل أن يكون في أي مجموعة ذات مقياس 0، لأن كل مجموعة تحتوي على نقطة واحدة لها مقياس 0. كانت فكرة مارتن-لوف هي حصر التعريف في المجموعات ذات المقياس 0 والتي يمكن وصفها بشكل فعال؛ يحدد تعريف الغطاء الفارغ الفعال مجموعة قابلة للعد من المجموعات ذات المقياس 0 التي يمكن وصفها بشكل فعال ويعرّف تسلسلاً بأنه عشوائي إذا لم يكن موجودًا في أي من هذه المجموعات ذات المقياس 0 الخاصة. نظرًا لأن اتحاد مجموعة قابلة للعد من المجموعات ذات المقياس 0 له مقياس 0، يؤدي هذا التعريف مباشرة إلى النظرية التي تقول بوجود مجموعة ذات مقياس 1 من التسلسلات العشوائية. لاحظ أنه إذا عرفنا فضاء كانتور للتسلسلات الثنائية بفترة [0,1] من الأرقام الحقيقية، فإن المقياس على فضاء كانتور يتوافق مع مقياس ليبيچ.

يمكن تفسير "مجموعة ذات مقياس 0 فعال" على أنها آلة تورينغ قادرة على تحديد، بالنظر إلى سلسلة ثنائية لا نهائية، ما إذا كانت السلسلة تبدو عشوائية عند مستويات الدلالة الإحصائية. المجموعة هي تقاطع مجموعات متقلصة $U_{1}\supset U_{2}\supset U_{3}\supset \cdots$، وبما أن كل مجموعة $U_{n}$ محددة بواسطة تسلسل قابل للعد من البادئات، بالنظر إلى أي سلسلة ثنائية لا نهائية، إذا كانت موجودة في $U_{n}$، فإن آلة تورينغ يمكن أن تقرر في وقت محدود أن السلسلة تقع داخل $U_{n}$. لذلك، يمكنها "رفض الفرضية بأن السلسلة عشوائية عند مستوى دلالة $2^{-n}$". إذا كانت آلة تورينغ قادرة على رفض الفرضية عند جميع مستويات الدلالة، فإن السلسلة ليست عشوائية. السلسلة العشوائية هي التي، لكل اختبار قابل للحساب بواسطة تورينج للعشوائية، تتمكن من البقاء مرفوضة إلى الأبد عند مستوى دلالة معين.

توصيف المارتينجال ينقل الفكرة بأنه لا ينبغي لأي إجراء فعال أن يتمكن من جني المال من المراهنة ضد تسلسل عشوائي. المارتينجال d هو استراتيجية مراهنة. d يقرأ سلسلة محدودة w ويراهن بالمال على البتة التالية. يراهن بجزء من ماله على أن البتة التالية ستكون 0، ثم الباقي من ماله على أن البتة التالية ستكون 1. يضاعف d المال الذي وضعه على البتة التي حدثت بالفعل، ويخسر الباقي. d(w) هو مقدار المال الذي لديه بعد رؤية السلسلة w. نظرًا لأن الرهان الذي تم وضعه بعد رؤية السلسلة w يمكن حسابه من القيم d(w), d(w0), وd(w1)، فإن حساب مقدار المال الذي لديه يعادل حساب الرهان. تقول توصيف المارتينجال أنه لا يمكن لأي استراتيجية مراهنة قابلة للتنفيذ بواسطة أي حاسوب (حتى في المعنى الضعيف للاستراتيجيات البناءة، التي ليست بالضرورة قابلة للحساب) أن تجني المال من المراهنة على تسلسل عشوائي.

 خصائص وأمثلة على تسلسلات مارتن-لوف العشوائية

 الشمولية

هناك مارتينجال بناء د شامل. هذا المارتينجال شامل بمعنى أنه، بالنظر إلى أي مارتينجال بناء د، إذا نجح د على تسلسل، فإن د ينجح على ذلك التسلسل أيضًا. وبالتالي، ينجح د على كل تسلسل في RAND^c (لكن، نظرًا لأن د بناء، فإنه لا ينجح على أي تسلسل في RAND). (شنور 1971) يوجد غطاء فارغ بناء لـ RAND^c. وهذا يعني أن جميع الاختبارات الفعالة للعشوائية (أي الأغطية الفارغة البناءة) يتم، بطريقة ما، دمجها في هذا الاختبار الشامل للعشوائية، حيث أن أي تسلسل يمر بهذا الاختبار الفردي للعشوائية سيمر بجميع اختبارات العشوائية. (مارتن-لوف 1966) بشكل بديهي، يقول هذا الاختبار الشامل للعشوائية "إذا كان التسلسل يحتوي على بادئات طويلة بشكل متزايد يمكن ضغطها بشكل متزايد على هذه الآلة تورينغ الشاملة"، فإنه ليس عشوائيًا." -- انظر القسم التالي.

مخطط الإنشاء: قم بترقيم الأغطية الفارغة الفعالة كـ $((U_{m,n})_{n})_{m}$. يكون الترقيم أيضًا فعالًا (يتم ترقيمه بواسطة آلة تورينغ شاملة معدلة). الآن لدينا غطاء فارغ فعال شامل بواسطة التقطيع: $(\cup _{n}U_{n,n+k+1})_{k}$.

 اجتياز اختبارات العشوائية

إذا فشل تسلسل في اختبار العشوائية الخوارزمي، فإنه يكون قابلًا للضغط خوارزميًا. وبالعكس، إذا كان قابلًا للضغط خوارزميًا، فإنه يفشل في اختبار العشوائية الخوارزمي.

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

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

على سبيل المثال، ضع في اعتبارك تسلسلًا ثنائيًا مرسومًا بشكل IID من توزيع بيرنولي. بعد أخذ عدد كبير $N$ من العينات، يجب أن نحصل على حوالي $M\approx pN$ من الآحاد. يمكننا ترميز هذا التسلسل على أنه "قم بإنشاء جميع التسلسلات الثنائية بطول $N$، و$M$ من الآحاد. من هؤلاء، التسلسل $i$-ث في الترتيب المعجمي.".

وفقًا تقريب ستيرلنج، $\log _{2}{\binom {N}{pN}}\approx NH(p)$ حيث $H$ هو دالة الإنتروبيا الثنائية. وهكذا، عدد البتات في هذا الوصف هو:

$$2(1+\epsilon )\log _{2}N+(1+\epsilon )NH(p)+O(1)$$

المصطلح الأول هو لترميز الأعداد $N$ و$M$. المصطلح الثاني هو لترميز العدد $i$. (استخدم ترميز إلياس أوميغا.) المصطلح الثالث هو لترميز باقي الوصف. عندما يكون $N$ كبيرًا، يكون لهذا الوصف فقط $\sim H(p)N$ من البتات، وبالتالي فهو قابل للضغط، بنسبة ضغط $\sim H(p)$. على وجه الخصوص، تكون نسبة الضغط واحدة بالضبط (غير قابلة للضغط) فقط عندما $p=1/2$. (مثال 14.2.8 )

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 استحالة نظام المراهنة

المقالة الرئيسية: استحالة نظام المراهنة

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

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

 أمثلة

• احتمالية توقف چايتين Ω هو مثال على تسلسل عشوائي.
• كل تسلسل عشوائي غير قابل للحساب.
• كل تسلسل عشوائي هو طبيعي، ويحقق قانون الأعداد الكبيرة، ويحقق جميع الخصائص القابلة للحساب بواسطة تورينغ والتي يحققها تيار IID من الأرقام العشوائية الموحدة. (نظرية 14.5.2 )

 العلاقة مع التسلسل الهرمي الحسابي

• RAND^c (متمم RAND) هو مقياس ضمني 0 لمجموعة جميع التسلسلات اللانهائية. يُفهم ذلك من حقيقة أن كل غطاء فارغ بناء يغطي مجموعة ذات مقياس 0، وهناك فقط عدد قابل للعد من الأغطية الفارغة البناءة، وأن اتحاد عدد قابل للعد من المجموعات ذات المقياس 0 له مقياس 0. هذا يعني أن RAND هو مجموعة ذات مقياس 1 لمجموعة جميع التسلسلات اللانهائية.
• الفئة RAND هي مجموعة $\Sigma _{2}^{0}$ في فضاء كانتور، حيث يشير $\Sigma _{2}^{0}$ إلى المستوى الثاني من التسلسل الهرمي الحسابي. وذلك لأن التسلسل S موجود في RAND إذا وفقط إذا كانت هناك مجموعة مفتوحة في الغطاء الفارغ الفعال الشامل لا تحتوي على S؛ يمكن اعتبار هذه الخاصية قابلة للتحديد بواسطة صيغة $\Sigma _{2}^{0}$.
• هناك تسلسل عشوائي هو $\Delta _{2}^{0}$، أي، قابل للحساب بالنسبة إلى أوراكل لمشكلة التوقف. (شنور 1971) يعتبر Ω چايتين مثالاً على مثل هذا التسلسل.
• لا يوجد تسلسل عشوائي هو قابل للقرار، قابل للتعداد الحاسوبي، أو قابل للتعداد المعاكس. نظرًا لأن هذه المستويات تتوافق مع $\Delta _{1}^{0}$، $\Sigma _{1}^{0}$، و$\Pi _{1}^{0}$ من التسلسل الهرمي الحسابي، فإن هذا يعني أن $\Delta _{2}^{0}$ هو أدنى مستوى في التسلسل الهرمي الحسابي حيث يمكن العثور على تسلسلات عشوائية.
• كل تسلسل قابل للاختزال بواسطة تورينغ إلى بعض التسلسلات العشوائية. (كوتشيرا 1985/1989، گاچس 1986). وبالتالي، هناك تسلسلات عشوائية بدرجات تورينغ عالية بشكل تعسفي.

 العشوائية النسبية

نظرًا لأن كل من التعريفات المكافئة لتسلسل مارتن-لوف العشوائي يعتمد على ما يمكن حسابه بواسطة بعض آلة تورينغ، يمكن للمرء بشكل طبيعي أن يسأل ما الذي يمكن حسابه بواسطة آلة تورينغ آلة الأوراكل. بالنسبة لأوراكل ثابت A، يقال أن تسلسل B الذي ليس فقط عشوائيًا بل في الواقع، يحقق التعريفات المكافئة للقابلية للحساب بالنسبة إلى A (على سبيل المثال، لا ينجح أي مارتينجال بناء بالنسبة إلى الأوراكل A على B) بأنه عشوائي بالنسبة إلى A. قد تحتوي تسلسلاتان، بينما هما عشوائيتان بذاتهما، على معلومات متشابهة جدًا، وبالتالي لن يكون أي منهما عشوائيًا بالنسبة للآخر. في أي وقت يوجد فيه اختزال تورينغ من تسلسل إلى آخر، لا يمكن أن يكون التسلسل الثاني عشوائيًا بالنسبة للأول، تمامًا كما أن التسلسلات القابلة للحساب بذاتها ليست عشوائية؛ على وجه الخصوص، يعني هذا أن Ω چايتين ليس عشوائيًا بالنسبة إلى مشكلة التوقف.

نتيجة مهمة تتعلق بالعشوائية النسبية هي نظرية ڤان لامباجين، التي تنص على أنه إذا كانت C هي التسلسل المكون من A وB عن طريق التداخل بين البتة الأولى من A، والبتة الأولى من B، والبتة الثانية من A، والبتة الثانية من B، وهكذا، فإن C عشوائي خوارزميًا إذا وفقط إذا كان A عشوائي خوارزميًا، وB عشوائي خوارزميًا بالنسبة إلى A. نتيجة قريبة الصلة هي أنه إذا كانت A وB كلاهما عشوائيين بذاتهما، فإن A عشوائي بالنسبة إلى B إذا وفقط إذا كان B عشوائيًا بالنسبة إلى A.

 أقوى من عشوائية مارتن-لوف

تمنحنا العشوائية النسبية المفهوم الأول الذي هو أقوى من عشوائية مارتن-لوف، وهو العشوائية بالنسبة إلى بعض الأوراكل الثابت A. بالنسبة لأي أوراكل، يكون هذا على الأقل بنفس القوة، وبالنسبة لمعظم الأوراكل، يكون أقوى بشكل صارم، حيث سيكون هناك تسلسلات عشوائية مارتن-لوف ليست عشوائية بالنسبة إلى الأوراكل A. تعتبر الأوراكلات المهمة غالبًا هي مشكلة التوقف، $\emptyset '$، وأوراكل القفزة n، $\emptyset ^{(n)}$، حيث أن هذه الأوراكلات قادرة على الإجابة عن أسئلة محددة تنشأ بشكل طبيعي. يُطلق على التسلسل الذي يكون عشوائيًا بالنسبة إلى الأوراكل $\emptyset ^{(n-1)}$ اسم n-عشوائي؛ التسلسل هو 1-عشوائي، إذن، إذا وفقط إذا كان عشوائيًا مارتن-لوف. يُطلق على التسلسل الذي يكون n-عشوائيًا لكل n اسم عشوائي حسابي. تظهر التسلسلات n-العشوائية أحيانًا عند النظر في خصائص أكثر تعقيدًا. على سبيل المثال، هناك فقط عدد قليل من مجموعات $\Delta _{2}^{0}$، لذلك قد يعتقد المرء أن هذه يجب أن تكون غير عشوائية. ومع ذلك، فإن احتمال التوقف Ω هو $\Delta _{2}^{0}$ و1-عشوائي؛ فقط بعد الوصول إلى 2-عشوائية يصبح من المستحيل أن تكون مجموعة عشوائية $\Delta _{2}^{0}$.

 أضعف من عشوائية مارتين-لوف

بالإضافة إلى ذلك، هناك عدة مفاهيم للعشوائية أضعف من عشوائية مارتين-لوف. بعض هذه المفاهيم تشمل العشوائية الضعيفة، وعشوائية شنور، والعشوائية القابلة للحساب، والعشوائية القابلة للحساب الجزئي. أظهر يونگ وانگ أن عشوائية شنور تختلف عن العشوائية القابلة للحساب. بالإضافة إلى ذلك، يُعرف أن عشوائية كولموغوروف-لوڤلاند ليست أقوى من عشوائية مارتين-لوف، لكن لم يُعرف ما إذا كانت أضعف بالفعل.

على الطرف المقابل من طيف العشوائية يوجد مفهوم مجموعة K-التافهة. هذه المجموعات مضادة للعشوائية حيث أن جميع القطاعات الأولية فيها قابلة للضغط لوغاريتميًا (أي، $K(w)\leq K(|w|)+b$ لكل قطاع أولي w)، لكنها غير قابلة للحساب.

 انظر أيضًا

• تسلسل عشوائي
• گرگوري چايتين
• علم الإحصاء
• طريقة مونتي كارلو
• مجموعة K-التافهة
• احتمالية الشمولية
• العشوائية الإحصائية

 قراءة إضافية

• Eagle, Antony (2021), Zalta, Edward N., ed., Chance versus Randomness (Spring 2021 ed.), Metaphysics Research Lab, Stanford University, https://plato.stanford.edu/archives/spr2021/entries/chance-randomness/, retrieved on 2024-01-28 
• Downey, Rod; Hirschfeldt, Denis R.; نيس, أندريه; تيروين, سباستيان أ. (2006). "معايرة العشوائية". The Bulletin of Symbolic Logic. 12 (3/4): 411–491. CiteSeerX 10.1.1.135.4162. doi:10.2178/bsl/1154698741. Archived from the original on 2016-02-02.
• گاك, پيتر (1986). "كل تسلسل قابل للتقليل إلى عشوائي" (PDF). Information and Control. 70 (2/3): 186–192. doi:10.1016/s0019-9958(86)80004-3.
• كوتشرا, أ. (1985). "Measure, Π01-classes and complete extensions of PA". 1141: 245–259, Springer-Verlag. doi:10.1007/BFb0076224. 
• كوتشرا, أ. (1989). "On the use of diagonally nonrecursive functions". 129: 219–239, North-Holland. 
• ليڤن، ل. (1973). "On the notion of a random sequence". Soviet Mathematics - Doklady. 14: 1413–1416.
• لي، م.; ڤيتاني، پ. م. ب. (1997). An Introduction to Kolmogorov Complexity and its Applications (Second ed.). Berlin: Springer-Verlag.
• مارتين-لوف, پ. (1966). "تعريف تسلسل العشوائية". Information and Control. 9 (6): 602–619. doi:10.1016/s0019-9958(66)80018-9.
• نيس, أندريه (2009). الحسابية والعشوائية. Oxford Logic Guides. Vol. 51. Oxford: Oxford University Press. ISBN 978-0-19-923076-1. Zbl 1169.03034.
• شنور، ك. پ. (1971). "نهج موحد لتعريف تسلسل عشوائي". Mathematical Systems Theory. 5 (3): 246–258. doi:10.1007/BF01694181. S2CID 8931514.
• شنور, كلاوس پ. (1973). "تعقيد العمليات والاختبارات العشوائية الفعالة". Journal of Computer and System Sciences. 7 (4): 376–388. doi:10.1016/s0022-0000(73)80030-3.
• چايتين, گرگوري ج. (1969). "حول طول البرامج لحساب تسلسلات ثنائية محدودة: اعتبارات إحصائية". Journal of the ACM. 16 (1): 145–159. doi:10.1145/321495.321506. S2CID 8209877.
• ڤيل، ج. (1939). دراسة نقدية لمفهوم الجماعي. باريس: Gauthier-Villars.