عملية برنولي

غالباً ما يُطلق على القيمتين المحتملتين لكل X _i اسم "النجاح" و"الفشل". وبالتالي، عند التعبير عنها كرقم 0 أو 1، يمكن تسمية النتيجة بعدد النجاحات في "المحاولة" رقم i .

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

في العديد من التطبيقات ، يمر الوقت بين التجارب مع ازدياد قيمة المؤشر i. في الواقع، تحدث التجارب X1 _، X2 _، ... ، Xi _، ... عند "نقاط زمنية" 1، 2، ...، i ، .... ومع ذلك ، فإن مرور الوقت وما يرتبط به من مفاهيم "الماضي" و"المستقبل" ليس ضروريًا. بشكل عام، أي قيمتين _{لـ Xi و Xj} في العملية هما _ببساطة قيمتان من مجموعة متغيرات عشوائية مُفهرسة بـ {1، 2، ...، n }، وهي الحالات المحدودة، أو بـ {1، 2، 3، ...}، وهي الحالات غير المحدودة.              

يمكن نمذجة تجربة واحدة ذات نتيجتين محتملتين فقط، يُشار إليهما غالبًا بـ "النجاح" و"الفشل"، ويتم ترميزهما عادةً بالرقمين 1 و0، باستخدام توزيع برنولي . ^{[ 1 ]} يمكن اشتقاق العديد من المتغيرات العشوائية وتوزيعات الاحتمالات ، بالإضافة إلى توزيعات برنولي، من عملية برنولي.

• عدد النجاحات في أول n محاولة، والذي له توزيع ذو الحدين B( n , p ) 
• عدد حالات الفشل اللازمة للحصول على r من حالات النجاح، والذي يتبع التوزيع ذي الحدين السالب NB( r , p ) 
• عدد حالات الفشل اللازمة لتحقيق نجاح واحد، والذي يتبع التوزيع الهندسي NB(1, p )، وهو حالة خاصة من التوزيع ذي الحدين السالب 

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

لنفترض أن لدينا عددًا لا نهائيًا من النواتج المباشرة لنسخ من${\displaystyle 2=\{H,T\}}$من الشائع فحص المجموعة أحادية الجانب${\displaystyle \Omega =2^{\mathbb {N} }=\{H,T\}^{\mathbb {N} }}$أو المجموعة ذات الوجهين${\displaystyle \Omega =2^{\mathbb {Z} }}$توجد طوبولوجيا طبيعية على هذا الفضاء، تُسمى طوبولوجيا الضرب . تتكون المجموعات في هذه الطوبولوجيا من متواليات منتهية من رميات العملة، أي سلاسل منتهية الطول من H و T ( حيث H تعني صورة و T تعني كتابة)، مع اعتبار باقي المتوالية (غير المحدودة الطول) "غير مهم". تُسمى هذه المجموعات من المتواليات المنتهية بمجموعات الأسطوانات في طوبولوجيا الضرب. تُشكل مجموعة جميع هذه السلاسل جبر سيجما ، وتحديدًا جبر بوريل . يُكتب هذا الجبر عادةً على النحو التالي:${\displaystyle (\Omega ,{\mathcal {B}})}$حيث عناصر${\displaystyle {\mathcal {B}}}$هي سلاسل ذات طول محدود من رميات العملة (مجموعات الأسطوانة).

إذا تم تحديد احتمالات ظهور الصورة أو الكتابة بواسطة الاحتمالات${\displaystyle \{p,1-p\}}$عندئذٍ يمكن تعريف مقياس طبيعي على فضاء المنتج، معطى بواسطة${\displaystyle P=\{p,1-p\}^{\mathbb {N} }}$(أو عن طريق${\displaystyle P=\{p,1-p\}^{\mathbb {Z} }}$(للعملية ثنائية الجانب). بعبارة أخرى، إذا كان للمتغير العشوائي المتقطع X توزيع برنولي بمعامل p ، حيث 0 ≤ p ≤ 1، وكانت دالة كتلة الاحتمال الخاصة به معطاة بـ

${\displaystyle pX(1)=P(X=1)=p}$و${\displaystyle pX(0)=P(X=0)=1-p}$.

نرمز إلى هذا التوزيع بـ Ber( p ). ^{[ 1 ]}

بافتراض مجموعة أسطوانات، أي تسلسل محدد لنتائج رمي العملة${\displaystyle [\omega _{1},\omega _{2},\cdots \omega _{n}]}$في بعض الأحيان${\displaystyle 1,2,\cdots ,n}$، يُعطى احتمال رصد هذا التسلسل المحدد بواسطة

${\displaystyle P([\omega _{1},\omega _{2},\cdots ,\omega _{n}])=p^{k}(1-p)^{nk}}$

حيث k هو عدد مرات ظهور H في المتتالية، و n − k هو عدد مرات ظهور T في المتتالية. توجد عدة أنواع مختلفة من الرموز لما سبق؛ أحدها الشائع هو كتابة

${\displaystyle P(X_{1}=x_{1},X_{2}=x_{2},\cdots ,X_{n}=x_{n})=p^{k}(1-p)^{nk}}$

حيث كل${\displaystyle X_{i}}$هو متغير عشوائي ذو قيمة ثنائية مع${\displaystyle x_{i}=[\omega _{i}=H]}$في تدوين أقواس إيفرسون ، مما يعني إما${\displaystyle 1}$لو${\displaystyle \omega _{i}=H}$أو${\displaystyle 0}$لو${\displaystyle \omega _{i}=T}$هذا الاحتمال${\displaystyle P}$يُطلق عليه عادةً اسم مقياس برنولي . ^{[ 2 ]}

لاحظ أن احتمال أي تسلسل محدد لا نهائي الطول من رميات العملة يساوي صفرًا تمامًا؛ وذلك لأن${\displaystyle \lim _{n\to \infty }p^{n}=0}$، لأي${\displaystyle 0\leq p<1}$إن احتمال يساوي 1 يعني أن أي متتالية لانهائية معينة لها قياس يساوي صفرًا . ومع ذلك، يمكن القول إن بعض فئات المتتاليات اللانهائية لرمي العملة أكثر احتمالًا من غيرها، وهذا ما تحدده خاصية التوزيع المتساوي التقاربي .

وختاماً للتعريف الرسمي، تُعطى عملية برنولي بثلاثية الاحتمالات${\displaystyle (\Omega ,{\mathcal {B}},P)}$، كما هو موضح أعلاه.

إحدى طرق إنشاء نظام ديناميكي من عملية برنولي هي اعتباره فضاء إزاحة . يوجد تناظر إزاحة طبيعي على فضاء الضرب.${\displaystyle \Omega =2^{\mathbb {N} }}$يُقدمها عامل المناوبة

${\displaystyle T(X_{0},X_{1},X_{2},\cdots )=(X_{1},X_{2},\cdots )}$

إن مقياس برنولي، المعرّف أعلاه، ثابت تحت الإزاحة؛ أي أنه لأي مجموعة أسطوانات${\displaystyle \sigma \in {\mathcal {B}}}$، لدى المرء

${\displaystyle P(T^{-1}(\sigma ))=P(\sigma )}$

وبالتالي فإن مقياس برنولي هو مقياس هار ؛ إنه مقياس ثابت على فضاء المنتج.

بدلاً من مقياس الاحتمالية${\displaystyle P:{\mathcal {B}}\to \mathbb {R} }$بدلاً من ذلك، ضع في اعتبارك دالة عشوائية${\displaystyle f:{\mathcal {B}}\to \mathbb {R} }$الدفع للأمام

${\displaystyle f\circ T^{-1}}$

محدد بواسطة${\displaystyle \left(f\circ T^{-1}\right)(\sigma )=f(T^{-1}(\sigma ))}$هي مرة أخرى وظيفة ما${\displaystyle {\mathcal {B}}\to \mathbb {R} .}$وهكذا، الخريطة${\displaystyle T}$يؤدي إلى خريطة أخرى${\displaystyle {\mathcal {L}}_{T}}$في فضاء جميع الدوال${\displaystyle {\mathcal {B}}\to \mathbb {R} .}$أي، بالنظر إلى بعض${\displaystyle f:{\mathcal {B}}\to \mathbb {R} }$، أحد التعريف

${\displaystyle {\mathcal {L}}_{T}f=f\circ T^{-1}}$

الخريطة${\displaystyle {\mathcal {L}}_{T}}$هو مؤثر خطي ، كما هو واضح.${\displaystyle {\mathcal {L}}_{T}(f+g)={\mathcal {L}}_{T}(f)+{\mathcal {L}}_{T}(g)}$و${\displaystyle {\mathcal {L}}_{T}(af)=a{\mathcal {L}}_{T}(f)}$للوظائف${\displaystyle f,g}$وثابت${\displaystyle a}$يُسمى هذا المؤثر الخطي مؤثر النقل أو مؤثر رويل-فروبينيوس-بيرون . يمتلك هذا المؤثر طيفًا ، أي مجموعة من الدوال الذاتية والقيم الذاتية المناظرة لها. أكبر قيمة ذاتية هي قيمة فروبينيوس-بيرون الذاتية ، وهي في هذه الحالة تساوي 1. المتجه الذاتي المرتبط به هو المقياس الثابت: وهو في هذه الحالة مقياس برنولي.${\displaystyle {\mathcal {L}}_{T}(P)=P.}$

إذا قام المرء بتقييد${\displaystyle {\mathcal {L}}_{T}}$إذا كان التأثير على كثيرات الحدود، فإن الدوال الذاتية هي (بشكل غريب) كثيرات حدود برنولي ! ^{[ 3 ] [ 4 ]} من المفترض أن برنولي لم يكن على علم بهذه المصادفة في التسمية.

يمكن توضيح ما سبق بشكل أكثر دقة. بالنظر إلى سلسلة لا نهائية من الأرقام الثنائية${\displaystyle b_{0},b_{1},\cdots }$يكتب

${\displaystyle y=\sum _{n=0}^{\infty }{\frac {b_{n}}{2^{n+1}}}.}$

والنتيجة${\displaystyle y}$هو عدد حقيقي في الفترة [0، 1].${\displaystyle 0\leq y\leq 1.}$التحول${\displaystyle T}$يُحدث تشاكلاً ، ويسمى أيضاً${\displaystyle T}$، على الفترة [1]. بما أن${\displaystyle T(b_{0},b_{1},b_{2},\cdots )=(b_{1},b_{2},\cdots ),}$يمكن للمرء أن يرى ذلك${\displaystyle T(y)=2y{\bmod {1}}.}$ تُسمى هذه الخريطة بالتحويل الثنائي ؛ لتسلسل البتات اللانهائي المزدوج${\displaystyle \Omega =2^{\mathbb {Z} },}$التشاكل المستحث هو خريطة بيكر .

لننظر الآن إلى فضاء الدوال في${\displaystyle y}$بالنظر إلى بعض${\displaystyle f(y)}$يمكن للمرء أن يجد ذلك

${\displaystyle \left[{\mathcal {L}}_{T}f\right](y)={\frac {1}{2}}f\left({\frac {y}{2}}\right)+{\frac {1}{2}}f\left({\frac {y+1}{2}}\right)}$

تقييد عمل المشغل${\displaystyle {\mathcal {L}}_{T}}$بالنسبة للدوال التي تنتمي إلى كثيرات الحدود، نجد أن لها طيفًا منفصلاً يُعطى بواسطة

${\displaystyle {\mathcal {L}}_{T}B_{n}=2^{-n}B_{n}}$

حيث${\displaystyle B_{n}}$هي كثيرات حدود برنولي . في الواقع، تخضع كثيرات حدود برنولي للمتطابقة

${\displaystyle {\frac {1}{2}}B_{n}\left({\frac {y}{2}}\right)+{\frac {1}{2}}B_{n}\left({\frac {y+1}{2}}\right)=2^{-n}B_{n}(y)}$

لاحظ أن المجموع

${\displaystyle y=\sum _{n=0}^{\infty }{\frac {b_{n}}{3^{n+1}}}}$

تعطي دالة كانتور ، كما هو مُعرَّف تقليديًا. وهذا أحد أسباب كون المجموعة${\displaystyle \{H,T\}^{\mathbb {N} }}$يُطلق عليها أحيانًا اسم مجموعة كانتور .

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

في هذه الحالة، التحويل${\displaystyle T}$يُعطى بواسطة

${\displaystyle T\left(1,\dots ,1,0,X_{k+1},X_{k+2},\dots \right)=\left(0,\dots ,0,1,X_{k+1},X_{k+2},\dots \right).}$

لا يبقى مقياس برنولي ثابتًا إلا في الحالة الخاصة لـ${\displaystyle p=1/2}$(العملة العادلة)؛ وإلا فلا. وهكذا،${\displaystyle T}$في هذه الحالة، يكون النظام الديناميكي محافظًا على القياس ، وإلا فهو مجرد نظام محافظ .

مثّل العملية المرصودة كسلسلة من الأصفار والآحاد، أو البتات، وقم بتجميع تدفق الإدخال هذا في أزواج غير متداخلة من البتات المتتالية، مثل (11)(00)(10)... . ثم لكل زوج،

• إذا كانت البتات متساوية، يتم تجاهلها؛
• إذا لم تكن البتات متساوية، فقم بإخراج البت الأول.

يلخص هذا الجدول عملية الحساب.

على سبيل المثال، يتم تجميع دفق إدخال مكون من ثمانية بتات 10011011 في أزواج كالتالي: (10)(01)(10)(11) . ثم، وفقًا للجدول أعلاه، تُترجم هذه الأزواج إلى مخرجات الإجراء: (1)(0)(1)() (= 101 ).

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

يستخدم مستخرج فون نيومان بتتين للإدخال لإنتاج بتات إخراج إما صفر أو واحد، لذا فإن الإخراج أقصر من الإدخال بمعامل  2 على الأقل. في المتوسط، تتجاهل العملية الحسابية نسبة p ²  +  (1  − p ) ² من أزواج الإدخال (00 و 11)، والتي تقترب من واحد عندما تكون p قريبة من الصفر أو واحد، وتصل إلى أدنى حد لها عند 1/4 عندما تكون p = 1/2 للعملية الأصلية (في هذه الحالة يكون طول دفق الإخراج ربع طول دفق الإدخال في المتوسط).   

الشفرة الزائفة للعملية الرئيسية لفون نيومان (الكلاسيكية) :

إذا كان (Bit1 ≠ Bit2) { output(Bit1) } 

يمكن التخفيف من هذا الانخفاض في الكفاءة، أو هدر العشوائية الموجودة في تدفق المدخلات، عن طريق تكرار الخوارزمية على بيانات الإدخال. وبهذه الطريقة، يمكن جعل المخرجات "قريبة جدًا من حد الإنتروبيا". ^{[ 5 ]}

تم تقديم النسخة التكرارية من خوارزمية فون نيومان، والمعروفة أيضًا باسم استراتيجية المستويات المتعددة المتقدمة (AMLS)، ^{[ 6 ] بواسطة يوفال بيريز في عام 1992. [ 5 ]} تعمل هذه الخوارزمية بشكل تكراري، حيث تعيد تدوير "العشوائية المهدرة" من مصدرين: تسلسل البتات المهملة وغير المهملة، وقيم الأزواج المهملة (0 للـ 00، و1 للـ 11). وتعتمد على حقيقة أنه، بالنظر إلى التسلسل المُولّد مسبقًا، يظل كلا المصدرين عبارة عن تسلسلات بتات قابلة للتبادل، وبالتالي مؤهلة لجولة أخرى من الاستخراج. في حين أنه يمكن تكرار توليد تسلسلات إضافية إلى ما لا نهاية لاستخراج كل الإنتروبيا المتاحة، إلا أن ذلك يتطلب كمية غير محدودة من الموارد الحاسوبية، لذلك عادةً ما يتم تحديد عدد التكرارات بقيمة منخفضة - إما أن تكون هذه القيمة محددة مسبقًا، أو يتم حسابها أثناء التشغيل.

وبشكل أكثر تحديدًا، عند إدخال سلسلة من البيانات، تستهلك الخوارزمية بتات الإدخال في أزواج، مما يؤدي إلى توليد مخرجات مع سلسلتين جديدتين، () يعطي تدوين ورقة AMLS:

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

مثال: تتم معالجة دفق الإدخال من ورقة AMLS، 11001011101110 باستخدام 1 لـ H و 0 لـ T، بهذه الطريقة:

ابتداءً من الخطوة 1، يكون المدخل عبارة عن دمج التسلسل 2 والتسلسل 1 من الخطوة السابقة (الترتيب اختياري ولكن يجب أن يكون ثابتًا). يكون الناتج النهائي ()()(1)()(1)()(1)()()(0)(0)()(0)(1)(1)()(1) (= 1111000111 )، أي أنه من 14 بت من المدخل تم توليد 10 بتات من الناتج، مقارنةً بـ 3 بتات فقط باستخدام خوارزمية فون نيومان وحدها. كما أن ثبات الناتج بمقدار 2 بت بالضبط لكل دورة لكل زوج بتات (مقارنةً بتغيره من صفر إلى 1 بت في خوارزمية فون نيومان التقليدية) يسمح بتنفيذات ذات زمن ثابت ومقاومة لهجمات التوقيت .

خوارزمية فون نيومان-بيريز (المتكررة) - الشفرة الزائفة للعملية الرئيسية:

إذا كان (Bit1 ≠ Bit2) { output(1, Sequence1) output(Bit1) } آخر { output(0, Sequence1) output(Bit1, Sequence2) } 

تم تقديم تعديل آخر في عام 2016، بناءً على ملاحظة أن قناة Sequence2 لا توفر إنتاجية كبيرة، ويمكن للتنفيذ المادي ذي عدد محدود من المستويات أن يستفيد من التخلص منها في وقت مبكر مقابل معالجة المزيد من مستويات Sequence1. ^{[ 7 ]}