طريقة العزم الثاني

الرسم البياني الفرعي لترشيح روابط برنولي للرسم البياني G عند المعامل p هو رسم بياني فرعي عشوائي مُستمد من G بحذف كل حافة من G باحتمالية 1− p ، بشكل مستقل. الشجرة الثنائية الكاملة اللانهائية T هي شجرة لانهائية حيث يمتلك رأس واحد (يُسمى الجذر) جارين، بينما يمتلك كل رأس آخر ثلاثة جيران. يمكن استخدام طريقة العزم الثاني لإثبات أنه عند كل معامل p ∈ (1/2, 1 ] باحتمالية موجبة، يكون المكون المتصل للجذر في الرسم البياني الفرعي للترشيح لـ T لانهائيًا.

ليكن K مكون الترشيح للجذر، وليكن T _{_n} مجموعة رؤوس T التي تبعد مسافة n عن الجذر. وليكن X _{_n} عدد الرؤوس في T _{_n} ∩ K.

لإثبات أن K لا نهائية باحتمالية موجبة، يكفي أن نبين أن${\displaystyle \Pr(X_{n}>0\ \ \forall n)>0}$منذ الأحداث${\displaystyle \{X_{n}>0\}}$تشكل متتالية متناقصة، وبحسب استمرارية مقاييس الاحتمال، فإن هذا يعادل إثبات أن${\displaystyle \inf _{n}\Pr(X_{n}>0)>0}$.

تعطي متباينة كوشي -شفارتز$${\displaystyle \operatorname {E} [X_{n}]^{2}\leq \operatorname {E} [X_{n}^{2}]\,\operatorname {E} \left[(1_{X_{n}>0})^{2}\right]=\operatorname {E} [X_{n}^{2}]\,\Pr(X_{n}>0).}$$ لذلك، يكفي أن نبين أن $${\displaystyle \inf _{n}{\frac {\operatorname {E} \left[X_{n}\right]^{2}}{\operatorname {E} \left[X_{n}^{2}\right]}}>0\,,}$$ أي أن العزم الثاني محدود من الأعلى بثابت مضروب في مربع العزم الأول (وكلاهما لا يساوي الصفر). في العديد من تطبيقات طريقة العزم الثاني، لا يمكن حساب العزوم بدقة، ولكن يمكن مع ذلك إثبات هذه المتباينة.

في هذا التطبيق تحديدًا، يمكن حساب هذه اللحظات. لكل قيمة محددة لـ v في T _n ، $${\displaystyle \Pr(v\in K)=p^{n}.}$$ منذ${\displaystyle |T_{n}|=2^{n}}$وبناءً على ذلك $${\displaystyle \operatorname {E} [X_{n}]=2^{n}\,p^{n}}$$ وهذا هو العزم الأول. والآن يأتي حساب العزم الثاني. $${\displaystyle \operatorname {E} \!\left[X_{n}^{2}\right]=\operatorname {E} \!\left[\sum _{v\in T_{n}}\sum _{u\in T_{n}}1_{v\in K}\,1_{u\in K}\right]=\sum _{v\in T_{n}}\sum _{u\in T_{n}}\Pr(v,u\in K).}$$ لكل زوج v و u في Tⁿ ، _ليكن w ( v , u ) هو الرأس في T الأبعد عن الجذر والواقع على المسار البسيط في T المؤدي إلى كل من الرأسين v و u ، وليكن k ( v , u ) هو المسافة من w إلى الجذر. لكي يكون كل من v و u في K ، من الضروري والكافي أن تكون المسارات البسيطة الثلاثة من w ( v , u ) إلى v و u والجذر في K. بما أن عدد الحواف المكونة لاتحاد هذه المسارات الثلاثة هو 2ⁿ - k ( v , u ) ، فإننا نحصل على $${\displaystyle \Pr(v,u\in K)=p^{2n-k(v,u)}.}$$ عدد الأزواج ( v , u ) التي تحقق الشرط k ( v , u ) = s يساوي${\displaystyle 2^{s}\,2^{ns}\,2^{ns-1}=2^{2n-s-1}}$، ل${\displaystyle s=0,1,\dots ,n-1}$ويساوي${\displaystyle 2^{n}}$ل${\displaystyle s=n}$لذا، من أجل${\displaystyle p>{\frac {1}{2}}}$، $${\displaystyle \operatorname {E} [X_{n}^{2}]=(2p)^{n}+\sum _{s=0}^{n-1}2^{2n-s-1}p^{2n-s}={\frac {(2p)^{n+1}-2(2p)^{n}+(2p)^{2n+1}}{4p-2}},}$$ لهذا السبب. $${\displaystyle {\frac {(\operatorname {E} [X_{n}])^{2}}{\operatorname {E} [X_{n}^{2}]}}={\frac {4p-2}{(2p)^{1-n}-2(2p)^{-n}+2p}}\to 2-{\frac {1}{p}}>0,}$$ وهذا يكمل البرهان.

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

• كان اختيار المتغيرات العشوائية X_{_n} طبيعيًا إلى حد كبير في هذا السياق. أما في بعض التطبيقات الأكثر تعقيدًا لهذه الطريقة، فقد يتطلب الأمر بعض الإبداع لاختيار المتغيرات العشوائية X_{_n} التي يمكن تطبيق الحجة عليها.
• تُستخدم متباينة بالي-زيغموند أحيانًا بدلاً من متباينة كوشي -شفارتز ، وقد تعطي في بعض الأحيان نتائج أكثر دقة.
• بافتراض (غير صحيح) أن الحدثين v و u في K مستقلان دائمًا، يكون لدينا${\displaystyle \Pr(v,u\in K)=\Pr(v\in K)\,\Pr(u\in K)}$والعزم الثاني يساوي مربع العزم الأول. وتُستخدم طريقة العزم الثاني عادةً في الحالات التي تكون فيها الأحداث أو المتغيرات العشوائية المقابلة "مستقلة تقريبًا".
• في هذا التطبيق، تُعطى المتغيرات العشوائية X _{n على شكل مجاميع.}$${\displaystyle X_{n}=\sum _{v\in T_{n}}1_{v\in K}.}$$في تطبيقات أخرى، تكون المتغيرات العشوائية المفيدة المقابلة عبارة عن أعداد صحيحة.$${\displaystyle X_{n}=\int f_{n}(t)\,d\mu (t),}$$حيث تكون الدوال f _n عشوائية. في مثل هذه الحالة، يتم النظر في مقياس الضرب μ × μ ويتم حسابه.$${\displaystyle {\begin{aligned}\operatorname {E} \left[X_{n}^{2}\right]&=\operatorname {E} \left[\iint f_{n}(x)\,f_{n}(y)\,d\mu (x)\,d\mu (y)\right]\\&=\operatorname {E} \left[\iint \operatorname {E} \left[f_{n}(x)\,f_{n}(y)\right]\,d\mu (x)\,d\mu (y)\right],\end{aligned}}}$$حيث يتم تبرير الخطوة الأخيرة عادةً باستخدام نظرية فوبيني .