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

📅 آخر تحديث: ١٨ يوليو ٢٠٢٦
✍️ نُشر في: ١٨ يوليو ٢٠٢٦
📷 يحتوي على 55 صور
الموسوعة الحرة

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

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

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

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

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

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

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

تاريخ

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

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

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

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

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

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

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

عادةً ما تُعرَّف القواعد المقبولة بأنها قواعد قابلة للحساب بواسطة آلة تورينج، ونحن نشترطص=1/2{\displaystyle p=1/2}وبذلك، نحصل على متواليات ميزس-والد-تشرش العشوائية . وهذا ليس قيدًا، لأنه بالنظر إلى متوالية معص=1/2{\displaystyle p=1/2}يمكننا إنشاء متواليات عشوائية باستخدام أي شيء آخر قابل للحسابص∈(0،1){\displaystyle p\in (0,1)}[ 1 ] (هنا ، تشير كلمة "Church" إلى ألونسو تشيرش ، الذي اقترح في ورقته البحثية عام 1940 استخدام قواعد قابلة للحساب بواسطة تورينج. [ 2 ] )

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

مخطط البرهان: استخدم الاحتمالية القائمة على نظرية القياس.

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

ومع ذلك، تبين أن هذا التعريف غير كافٍ. فمن البديهي أن يتذبذب المتوسط ​​طويل الأمد لتسلسل عشوائي على جانبيص{\displaystyle p}كما هو الحال في المشي العشوائي الذي يعبر نقطة الأصل عددًا لا نهائيًا من المرات. ومع ذلك، أظهر جان فيل أنه حتى مع وجود عدد قابل للعد من القواعد، يوجد تسلسل ثنائي يميل نحوص{\displaystyle p}نسبة من الآحاد، ولكن بالنسبة لكل بادئة منتهية، تكون نسبة الآحاد أقل منص{\displaystyle p}[ 4 ]​

بناء فيل (جان فيل، 1939): توجد مجموعة ذات عدد لا نهائي من القواعد المقبولة، بحيث يكون لكلن{\displaystyle n}،1ن∑ك=1نxك≤ص{\displaystyle {\frac {1}{n}}\sum _{k=1}^{n}x_{k}\leq p}[ 5 ]​

بير مارتن لوف

يشير بناء فيل إلى أن مفهوم ميزس-والد-تشرش للعشوائية غير كافٍ، لأن بعض المتتاليات العشوائية لا تُحقق بعض قوانين العشوائية. على سبيل المثال، لا يُحقق بناء فيل أحد قوانين اللوغاريتم المتكرر .ليم سوبن→∞-∑ك=1ن(xك-1/2)2نسجل⁡سجل⁡ن≠1{\displaystyle \limsup _{n\to \infty }{\frac {-\sum _{k=1}^{n}(x_{k}-1/2)}{\sqrt {2n\log \log n}}}\neq 1}ببساطة، يمكن حل هذه المشكلة باشتراط أن تُحقق المتتالية جميع قوانين العشوائية الممكنة، حيث يُعرَّف "قانون العشوائية" بأنه خاصية تُحققها جميع المتتاليات باحتمالية 1. ومع ذلك، بالنسبة لكل متتالية لانهائيةy1:∞∈2شمال{\displaystyle y_{1:\infty }\in 2^{\mathbb {N} }}لدينا قانون العشوائية الذيx1:∞≠y1:∞{\displaystyle x_{1:\infty }\neq y_{1:\infty }}مما يؤدي إلى استنتاج مفاده أنه لا توجد تسلسلات عشوائية.

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

تُعرف الفرضية القائلة بأن تعريف عشوائية مارتن-لوف "يلتقط بشكل صحيح" المفهوم البديهي للعشوائية باسم فرضية مارتن-لوف-شايتين ؛ وهي تشبه إلى حد ما فرضية تشيرش-تورينغ . [ 7 ]

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

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

ثلاثة تعريفات متكافئة

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

تكون المتتالية اللانهائية S عشوائية وفقًا لمارتن-لوف إذا وفقط إذا كان هناك ثابت c بحيث تكون جميع البادئات المنتهية لـ S غير قابلة للانضغاط بالنسبة لـ c . وبعبارة أخرى،ك(w)≥|w|-يا(1){\displaystyle K(w)\geq |w|-O(1)}.
  • الأغطية الصفرية البنّاءة (مارتن-لوف، 1966): هذا هو تعريف مارتن-لوف الأصلي. بالنسبة لسلسلة ثنائية منتهية w، نرمز بـ C <sub> w</sub> إلى الأسطوانة المولدة بواسطة w . هذه هي مجموعة جميع المتتاليات اللانهائية التي تبدأ بـ w ، وهي مجموعة مفتوحة أساسية في فضاء كانتور . يُعرَّف مقياس الضرب μ( C<sub> w</sub> ) للأسطوانة المولدة بواسطة w بأنه 2 <sup>-| w |</sup> . كل مجموعة جزئية مفتوحة من فضاء كانتور هي اتحاد متتالية قابلة للعد من مجموعات مفتوحة أساسية منفصلة، ​​ومقياس أي مجموعة مفتوحة هو مجموع مقاييس أي متتالية من هذا القبيل. المجموعة المفتوحة الفعالة هي مجموعة مفتوحة تمثل اتحاد متتالية المجموعات المفتوحة الأساسية المحددة بواسطة متتالية قابلة للتعداد بشكل متكرر من السلاسل الثنائية. الغطاء الصفري البنّاء أو مجموعة المقياس الفعال 0 هي متتالية قابلة للتعداد بشكل متكرريوأنا{\displaystyle U_{i}}من المجموعات المفتوحة الفعالة بحيثيوأنا+1⊆يوأنا{\displaystyle U_{i+1}\subseteq U_{i}}وμ(يوأنا)≤2-أنا{\displaystyle \mu (U_{i})\leq 2^{-i}}لكل عدد طبيعي i . كل غطاء صفري فعال يحدد aجيدلتا{\displaystyle G_{\delta }}مجموعة ذات قياس 0، أي تقاطع المجموعاتيوأنا{\displaystyle U_{i}}.
تُعرَّف المتتالية بأنها عشوائية وفقًا لمارتن-لوف إذا لم تكن مُحتواة في أيجيدلتا{\displaystyle G_{\delta }}مجموعة محددة بواسطة غطاء صفري بناء.
  • مارتينجال بناءة (شنور 1971): مارتينجال هي وظيفةد:{0،1}*→[0،∞){\displaystyle d:\{0,1\}^{*}\to [0,\infty )}بحيث يكون ذلك، بالنسبة لجميع السلاسل المحدودة w ،د(w)=(د(w⌢0)+د(w⌢1))/2{\displaystyle d(w)=(d(w^{\smallfrown }0)+d(w^{\smallfrown }1))/2}، أينأ⌢ب{\displaystyle a^{\smallfrown }b}هي عبارة عن دمج السلسلتين a و b . يُطلق على هذا "شرط العدالة": إذا نُظر إلى المارتينجال كاستراتيجية مراهنة، فإن الشرط المذكور أعلاه يتطلب أن يلعب المراهن ضد احتمالات عادلة. يُقال إن المارتينجال d ناجح على متتالية S إذاليم سوبن→∞د(S↾ن)=∞،{\displaystyle \limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,}أينS↾ن{\displaystyle S\upharpoonright n}تمثل أول n بت من S. يكون المارتينجال d بنائيًا (يُعرف أيضًا باسم قابل للحساب ضعيفًا ، أو قابل للحساب شبه السفلي ) إذا وُجدت دالة قابلة للحسابد^:{0،1}*×شمال→سؤال{\displaystyle {\widehat {d}}:\{0,1\}^{*}\times \mathbb {N} \to {\mathbb {Q} }}بحيث يكون، بالنسبة لجميع السلاسل الثنائية المحدودة w
  1. د^(w،ت)≤د^(w،ت+1)<د(w)،{\displaystyle {\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),}لكل الأعداد الصحيحة الموجبة t ،
  2. ليمت→∞د^(w،ت)=د(w).{\displaystyle \lim _{t\to \infty }{\widehat {d}}(w,t)=d(w).}
تكون المتتالية عشوائية وفقًا لمارتن-لوف إذا وفقط إذا لم ينجح أي مارتينجال بناء عليها.

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

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

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

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

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

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

عالمية

يوجد مارتينجال بنائي شامل d . هذا المارتينجال شامل بمعنى أنه، بالنظر إلى أي مارتينجال بنائي d ، إذا نجح d على متتالية ما، فإنه ينجح على تلك المتتالية أيضًا. وبالتالي، ينجح d على كل متتالية في RAND c (ولكن، نظرًا لأن d بنائي، فإنه لا ينجح على أي متتالية في RAND). (شنور 1971)

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

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

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

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

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

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

على سبيل المثال، لنفترض وجود متتالية ثنائية مأخوذة عشوائياً من توزيع برنولي بشكل مستقل ومتطابق . بعد أخذ عدد كبيرشمال{\displaystyle N}من العينات، ينبغي أن يكون لدينا حواليم≈صشمال{\displaystyle M\approx pN}يمكننا ترميز هذه المتتالية على النحو التالي: "إنشاء جميع المتتاليات الثنائية بطول واحد".شمال{\displaystyle N}، وم{\displaystyle M}واحد منها. ومن بينها، الـأنا{\displaystyle i}التسلسل رقم -th بالترتيب المعجمي.

باستخدام تقريب ستيرلينغ ،سجل2⁡(شمالصشمال)≈شمالح(ص){\displaystyle \log _{2}{\binom {N}{pN}}\approx NH(p)}أينح{\displaystyle H}هي دالة الإنتروبيا الثنائية . وبالتالي، فإن عدد البتات في هذا الوصف هو2(1+ϵ)سجل2⁡شمال+(1+ϵ)شمالح(ص)+يا(1){\displaystyle 2(1+\epsilon )\log _{2}N+(1+\epsilon )NH(p)+O(1)}المصطلح الأول مخصص لترميز الأرقام بالبادئةشمال{\displaystyle N}وم{\displaystyle M}المصطلح الثاني مخصص لترميز الرقم باستخدام البادئةأنا{\displaystyle i}(استخدم ترميز إلياس أوميغا .) المصطلح الثالث مخصص لترميز بقية الوصف باستخدام البادئات. عندماشمال{\displaystyle N}كبير، هذا الوصف يحتوي فقط على∼ح(ص)شمال{\displaystyle \sim H(p)N}بتات، وبالتالي فهي قابلة للضغط، بنسبة ضغط∼ح(ص){\displaystyle \sim H(p)}على وجه الخصوص، تكون نسبة الانضغاط مساوية للواحد بالضبط (غير قابلة للانضغاط) فقط عندماص=1/2{\displaystyle p=1/2}(مثال 14.2.8 [ 10 ] )

استحالة وجود نظام للمقامرة

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

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

أمثلة

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

  • مجموعة RAND c ( متممة RAND) هي مجموعة جزئية قياسها صفر من مجموعة جميع المتتاليات اللانهائية. ويتضح ذلك من حقيقة أن كل غطاء صفري بنائي يغطي مجموعة قياسها صفر، وأن عدد الأغطية الصفرية البنائية محدود بالعد ، وأن أي اتحاد قابل للعد لمجموعات قياسها صفر يكون قياسه صفرًا. وهذا يعني أن RAND هي مجموعة جزئية قياسها واحد من مجموعة جميع المتتاليات اللانهائية.
  • فئة RAND هيΣ20{\displaystyle \Sigma _{2}^{0}}مجموعة جزئية من فضاء كانتور، حيثΣ20{\displaystyle \Sigma _{2}^{0}}يشير هذا إلى المستوى الثاني من التسلسل الهرمي الحسابي . وذلك لأن المتتالية S تنتمي إلى RAND إذا وفقط إذا وُجدت مجموعة مفتوحة في الغطاء الصفري الفعال الشامل لا تحتوي على S ؛ ويمكن اعتبار هذه الخاصية قابلة للتعريف بواسطةΣ20{\displaystyle \Sigma _{2}^{0}}صيغة.
  • هناك تسلسل عشوائي وهوΔ20{\displaystyle \Delta _{2}^{0}}أي أنها قابلة للحساب بالنسبة إلى مرجع أوراكل لمسألة التوقف. (شنور 1971) Ω لشايتين هو مثال على مثل هذه المتتالية.
  • لا يوجد تسلسل عشوائي قابل للتقرير ، أو قابل للحصر الحسابي ، أو قابل للحصر الحسابي المشترك . لأن هذه تتوافق معΔ10{\displaystyle \Delta _{1}^{0}}،Σ10{\displaystyle \Sigma _{1}^{0}}، وΠ10{\displaystyle \Pi _{1}^{0}}مستويات التسلسل الهرمي الحسابي ، وهذا يعني أنΔ20{\displaystyle \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. ومن المراجع المهمة التي يتم تناولها غالبًا مشكلة التوقف.∅′{\displaystyle \emptyset '}و "أوراكل القفزة رقم n "،∅(ن){\displaystyle \emptyset ^{(n)}}حيث أن هذه العرافات قادرة على الإجابة على أسئلة محددة تنشأ بشكل طبيعي. تسلسل عشوائي بالنسبة للعرافة∅(ن-1){\displaystyle \emptyset ^{(n-1)}}يُطلق على المتتالية اسم متتالية عشوائية من الرتبة n ؛ وبالتالي، تكون المتتالية عشوائية من الرتبة 1 إذا وفقط إذا كانت عشوائية وفقًا لنموذج مارتن-لوف. تُسمى المتتالية التي تكون عشوائية من الرتبة n لكل قيمة n عشوائية حسابيًا. تظهر المتتاليات العشوائية من الرتبة n أحيانًا عند دراسة خصائص أكثر تعقيدًا. على سبيل المثال، يوجد عدد قابل للعد فقط منΔ20{\displaystyle \Delta _{2}^{0}}قد يظن المرء أن هذه المجموعات يجب أن تكون غير عشوائية. ومع ذلك، فإن احتمال التوقف Ω هوΔ20{\displaystyle \Delta _{2}^{0}}وعشوائية-1؛ فقط بعد الوصول إلى عشوائية-2 يصبح من المستحيل أن تكون المجموعة عشوائيةΔ20{\displaystyle \Delta _{2}^{0}}.

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

إضافةً إلى ذلك، توجد عدة مفاهيم للعشوائية أضعف من عشوائية مارتن-لوف. من هذه المفاهيم: العشوائية الضعيفة من الرتبة 1، وعشوائية شنور، والعشوائية القابلة للحساب، والعشوائية القابلة للحساب جزئيًا. وقد بيّن يونغجي وانغ [ 11 ] أن عشوائية شنور تختلف عن العشوائية القابلة للحساب. كما أن عشوائية كولموغوروف-لوفلاند ليست أقوى من عشوائية مارتن-لوف، ولكن ليس من المعروف ما إذا كانت أضعف منها في الواقع.

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

انظر أيضاً

مراجع

  1. ↑ لي، مينغ؛ فيتاني، ب.م. (2019). "1.9 العشوائية". مقدمة في تعقيد كولموغوروف وتطبيقاته (  الطبعة الرابعة). تشام: سبرينغر. ISBN 978-3-030-11298-1.
  2. ↑ كوبلاند، آرثر هـ. (يونيو 1940). "ألونزو تشيرش. حول مفهوم المتتالية العشوائية. نشرة الجمعية الرياضية الأمريكية ، المجلد 46 (1940)، الصفحات 130-135". مجلة المنطق الرمزي (مراجعة). 5 (2): 71-72 . doi : 10.2307/2266178 . ISSN 0022-4812 . JSTOR 2266178. S2CID 124646586 .   
  3. ^ والد، أ. (1936). حول فكرة التجميع في حساب الاحتمالات. Comptes Rendus des Seances de l'Académie des Sciences, 202، 180–183. والد، أ. (1937). Die Wiederspruchsfreiheit des Kollektivbegriffes der Wahrscheinlichkeitsrech- nung. Ergebnisse eines Mathematischen Kolloquiums, 8, 38–72
  4. ^ فيل، ج. (1939). دراسة نقدية لمفهوم الجمع ، دراسات الاحتمالات، حساب الاحتمالات وتطبيقاتها ، غوتييه فيلار.
  5. ↑ ليب، إليوت هـ.؛ أوشيرسون، دانيال؛ وينشتاين، سكوت (2006-07-11). "برهان ابتدائي لنظرية جان فيل". arXiv : cs/0607054 .
  6. ↑ مارتن-لوف، بير (1966-12-01). "تعريف المتتاليات العشوائية" . المعلومات والتحكم . 9 (6): 602-619 . doi : 10.1016/S0019-9958(66)80018-9 . ISSN 0019-9958 . 
  7. ↑ جان بول ديلاهاي ، العشوائية، وعدم القدرة على التنبؤ، وغياب النظام ، في فلسفة الاحتمالات ، ص 145-167، سبرينغر 1993.
  8. ↑ لي، فيتاني، القسم 2.4
  9. ↑ كوفر، ت. (يناير 1973). "ترميز المصادر التعدادية". معاملات IEEE في نظرية المعلومات . 19 (1): 73-77 . doi : 10.1109/TIT.1973.1054929 . ISSN 0018-9448 . 
  10. 1 2 كوفير، توماس م.؛ توماس، جوي أ. (18-07-2006). عناصر نظرية المعلومات ، الطبعة الثانية . هوبوكين، نيوجيرسي: وايلي-إنترساينس. ISBN  978-0-471-24195-9.
  11. ↑ يونغجي وانغ: العشوائية والتعقيد. أطروحة دكتوراه، 1996، http://webpages.uncc.edu/yonwang/papers/thesis.pdf

للمزيد من القراءة

  • إيجل، أنتوني (2021)، "الصدفة مقابل العشوائية" ، في زالتا، إدوارد ن. (محرر)، موسوعة ستانفورد للفلسفة (  طبعة ربيع 2021)، مختبر أبحاث الميتافيزيقا، جامعة ستانفورد ، تاريخ الاسترجاع 28 يناير 2024
  • داوني، رود؛ هيرشفيلدت، دينيس ر.؛ نيس، أندريه؛ تيروين، سيباستيان أ. (2006). "معايرة العشوائية" . نشرة المنطق الرمزي . 12 (3/4): 411-491 . CiteSeerX 10.1.1.135.4162 . doi : 10.2178/bsl/1154698741 . مؤرشف من الأصل في 2016-02-02. 
  • غاتش، بيتر (1986). "كل متتالية قابلة للاختزال إلى متتالية عشوائية" (ملف PDF) . المعلومات والتحكم . 70 (2/3): 186-192 . doi : 10.1016/s0019-9958(86)80004-3 . مؤرشف من الأصل (ملف PDF) بتاريخ 4 مارس 2016. تم الاطلاع عليه بتاريخ 2 سبتمبر 2015 .
  • كوتشيرا، أ. (1985). "القياس، وفئات Π 0 1 ، والامتدادات الكاملة لـ PA". أسبوع نظرية الاستدعاء الذاتي . سلسلة محاضرات في الرياضيات. المجلد  1141. سبرينغر-فيرلاغ. الصفحات 245-259 . doi : 10.1007/BFb0076224 . ISBN  978-3-540-39596-6.
  • كوتشيرا، أ. (1989). "حول استخدام الدوال غير المتكررة قطريًا". دراسات في المنطق وأسس الرياضيات . المجلد  129. نورث هولاند. الصفحات 219-239 . 
  • ليفين، ل. (1973). "حول مفهوم المتتالية العشوائية". الرياضيات السوفيتية - دوكلادي . 14 : 1413-1416 .
  • لي، م.؛ فيتاني، ب.م.ب. (1997). مقدمة في تعقيد كولموغوروف وتطبيقاته (  الطبعة الثانية). برلين: سبرينغر-فيرلاغ.
  • مارتن-لوف، ب. (1966). "تعريف المتتاليات العشوائية". المعلومات والتحكم . 9 (6): 602-619 . doi : 10.1016/s0019-9958(66)80018-9 .
  • نيس، أندريه (2009). الحوسبة والعشوائية . أدلة أكسفورد المنطقية. المجلد  51. أكسفورد: مطبعة جامعة أكسفورد. ISBN 978-0-19-923076-1. Zbl 1169.03034 . 
  • شنور، سي بي (1971). "نهج موحد لتعريف المتتالية العشوائية". نظرية الأنظمة الرياضية . 5 (3): 246-258 . doi : 10.1007/BF01694181 . S2CID 8931514 . 
  • شنور، كلاوس ب. (1973). "تعقيد العمليات والاختبارات العشوائية الفعالة" . مجلة علوم الحاسوب والنظم . 7 (4): 376-388 . doi : 10.1016/s0022-0000(73)80030-3 .
  • تشايتين، غريغوري ج. (1969). "حول طول برامج حساب المتتاليات الثنائية المحدودة: اعتبارات إحصائية" . مجلة ACM . 16 (1): 145-159 . doi : 10.1145/321495.321506 . S2CID 8209877 . 
  • فيل، ج. (1939). دراسة نقدية للفكرة الجماعية . باريس: غوتييه فيلار.