Екінші сәт әдісі - Second moment method

Математикада екінші сәт әдісі - бұл қолданылатын әдіс ықтималдықтар теориясы және талдау екенін көрсету үшін а кездейсоқ шама оң болу ықтималдығы бар. Көбінесе «момент әдісі» кездейсоқ шаманың орташадан алыс ауытқу ықтималдығын оның моменттерін қолдану арқылы шектеуінен тұрады.^[1]

Әдіс көбінесе сандық болып табылады, өйткені кездейсоқ шаманың күткеннен бірнеше есе үлкен болатындығының ықтималдығының төменгі шекарасын анықтауға болады. Әдіс екіншісін салыстыруды қамтиды сәт бірінші моменттің квадратына дейінгі кездейсоқ шамалар.

Бірінші сәттік әдіс

Бірінші сәттік әдіс - қарапайым қолдану Марковтың теңсіздігі бүтін мәнді айнымалылар үшін. Үшін теріс емес, бүтін мән кездейсоқ шама X, біз мұны дәлелдегіміз келеді X = 0 үлкен ықтималдықпен. P үшін жоғарғы шекараны алу үшін (X > 0), және P үшін төменгі шек (X = 0), біз біріншіден бастап екенін ескереміз X тек бүтін мәндерді алады, P (X > 0) = P (X ≥ 1). Бастап X теріс емес, біз қазір қолдана аламыз Марковтың теңсіздігі алу үшін P (X ≥ 1) ≤ E [X]. Оларды біріктіре отырып, бізде P (X > 0) ≤ E [X]; бірінші сәт әдісі - бұл теңсіздікті қолдану.

Екінші сәт әдісі

Басқа бағытта E [X] «үлкен» болу тікелей P (X = 0) аз. Алайда, біз осындай тұжырым жасау үшін екінші сәтті жиі қолдана аламыз Коши-Шварц теңсіздігі.

Теорема: Егер X ≥ 0 - а кездейсоқ шама шексіз дисперсиямен, содан кейін

${ displaystyle operatorname {P} (X> 0) geq { frac {( operatorname {E} [X]) ^ {2}} { operatorname {E} [X ^ {2}]}}. }$

Дәлел: Пайдалану Коши-Шварц теңсіздігі, Бізде бар

${ displaystyle operatorname {E} [X] = operatorname {E} [X , mathbf {1} _ { {X> 0 }}] leq operatorname {E} [X ^ {2} ] ^ {1/2} оператор атауы {P} (X> 0) ^ {1/2}.}$

Шешу ${ displaystyle operatorname {P} (X> 0)}$, содан кейін қажетті теңсіздік шығады. ∎

Әдісті кездейсоқ шамалардың үлестіру шектерінде де қолдануға болады. Сонымен қатар, алдыңғы теореманы бағалау деп аталатын тәсіл арқылы нақтылауға болады Пейли-Зигмунд теңсіздігі. Айталық X_n - бұл теріс емес нақты бағаланатын кездейсоқ шамалардың тізбегі, ол заңға жақындау кездейсоқ шамаға X. Егер шекті оң константалар болса c₁, c₂ осындай

${ displaystyle operatorname {E} left [X_ {n} ^ {2} right] leq c_ {1} operatorname {E} [X_ {n}] ^ {2}}$

${ displaystyle operatorname {E} left [X_ {n} right] geq c_ {2}}$

әрқайсысы үшін ұстаңыз n, содан кейін Пейли-Зигмунд теңсіздігі бұл әрқайсысы үшін n және θ in (0, 1)

${ displaystyle operatorname {P} (X_ {n} geq c_ {2} theta) geq { frac {(1- theta) ^ {2}} {c_ {1}}}.}$

Демек, бірдей теңсіздік қанағаттандырылады X.

Әдісті қолдану мысалы

Мәселені орнату

The Бернулли байланысының перколяциясы подограф график G параметр бойынша б - алынған кездейсоқ подграф G әр шетін жою арқылы G 1− ықтималдықпенб, Дербес. The шексіз толық екілік ағаш Т шексіз ағаш мұнда бір шыңның (түбір деп аталады) екі көршісі, ал қалған шыңның үш көршісі болады. Екінші момент әдісін әр параметрде көрсету үшін қолдануға болады б 1/ (1/2, 1] оң ықтималдығы бар түбірдің жалғанған компоненті перколяция подграфында Т шексіз.

Әдісті қолдану

Келіңіздер Қ түбірдің перколяциялық компоненті болыңыз және рұқсат етіңіз Т_n шыңдарының жиынтығы болыңыз Т қашықтықта орналасқан n тамырдан. Келіңіздер X_n шыңдар саны Т_n ∩ Қ. Мұны дәлелдеу үшін Қ оң ықтималдықпен шексіз, мұны көрсету жеткілікті ${ displaystyle limsup _ {n to infty} 1_ {X_ {n}> 0}> 0}$ оң ықтималдықпен. Бойынша кері Фату леммасы, мұны көрсету жеткілікті ${ displaystyle inf _ {n to infty} P (X_ {n}> 0)> 0}$. The Коши-Шварц теңсіздігі береді

${ displaystyle E [X_ {n}] ^ {2} leq E [X_ {n} ^ {2}] , E left [(1_ {X_ {n}> 0}) ^ {2} right ] = E [X_ {n} ^ {2}] , P (X_ {n}> 0).}$

Сондықтан мұны көрсету жеткілікті

${ displaystyle inf _ {n} { frac {E left [X_ {n} right] ^ {2}} {E left [X_ {n} ^ {2} right]}}> 0 ,,}$

яғни екінші сәт жоғарыдан бірінші моменттің квадратына тұрақты уақытпен шектелген (және екеуі де нөлге тең емес). Екінші момент әдісінің көптеген қосымшаларында моменттерді дәл есептеу мүмкін емес, бірақ осы теңсіздікті орната алады.

Осы нақты қосымшада осы сәттерді есептеуге болады. Әр нақты үшін v жылы Т_n,

${ displaystyle P (v in K) = p ^ {n}.}$

Бастап ${ displaystyle | T_ {n} | = 2 ^ {n}}$, бұдан шығады

${ displaystyle E [X_ {n}] = 2 ^ {n} , p ^ {n}}$

бұл бірінші сәт. Енді екінші сәтті есептеу келеді.

${ displaystyle E ! left [X_ {n} ^ {2} right] = 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}} P (v, u in K).}$

Әр жұп үшін v, сен жылы Т_n рұқсат етіңіз w (v, u) шыңын белгілеңіз Т бұл тамырдан ең алыс және қарапайым жолда жатыр Т екі шыңның әрқайсысына v және сенжәне рұқсат етіңіз k (v, u) арақашықтықты белгілеңіз w тамырға дейін. Үшін v, сен екеуінде де болу керек Қ, бұл үш қарапайым жол үшін қажет және жеткілікті w (v, u) дейін v, сен және тамыр болу керек Қ. Осы үш жолдың бірігуіндегі жиектер саны 2 болғандықтанn − k (v, u), біз аламыз

${ displaystyle P (v, u in K) = p ^ {2n-k (v, u)}.}$

Жұптардың саны (v, u) осындай k (v, u) = с тең ${ displaystyle 2 ^ {s} , 2 ^ {n-s} , 2 ^ {n-s-1} = 2 ^ {2n-s-1}}$, үшін с = 0, 1, ..., n. Демек,

${ displaystyle E ! left [X_ {n} ^ {2} right] = sum _ {s = 0} ^ {n} 2 ^ {2n-s-1} p ^ {2n-s} = { frac {1} {2}} , (2p) ^ {n} sum _ {s = 0} ^ {n} (2p) ^ {s} = { frac {1} {2}} , (2p) ^ {n} , { frac {(2p) ^ {n + 1} -1} {2p-1}} leq { frac {p} {2p-1}} , E [ X_ {n}] ^ {2},}$

бұл дәлелдеуді аяқтайды.

Талқылау

• Кездейсоқ шамаларды таңдау X_n Бұл қондырғыда табиғи болды. Әдістің кейбір қиын қолданбаларында кездейсоқ шамаларды таңдау үшін тапқырлық қажет болуы мүмкін X_n ол үшін дәлел келтіруге болады.
• The Пейли-Зигмунд теңсіздігі кейде орнына қолданылады Коши-Шварц теңсіздігі және кейде неғұрлым нақтыланған нәтижелер беруі мүмкін.
• (Дұрыс емес) болжам бойынша, оқиғалар v, сен жылы Қ әрқашан тәуелсіз, біреуінде бар ${ displaystyle P (v, u in K) = P (v in K) , P (u in 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} E left [X_ {n} ^ {2} right] & = E left [ int int f_ {n} (x) , f_ {n} (y) , d mu (x) , d mu (y) right] & = E сол жақ [ int int E сол [f_ {n} (x) , f_ {n} (y) ) right] , d mu (x) , d mu (y) right], end {aligned}}}$

мұнда соңғы қадамды қолдану негізделеді Фубини теоремасы.

Әдебиеттер тізімі

• Берди, Кзиштоф; Адельман, Омер; Пемантл, Робин (1998), «Браундық қозғалысқа жол бермейтін жиынтықтар», Ықтималдық шежіресі, 26 (2): 429–464, arXiv:математика / 9701225, дои:10.1214 / aop / 1022855639, hdl:1773/2194
• Лионс, Рассел (1992), «Кездейсоқ серуендеу, сыйымдылық және ағаштардағы перколяция», Ықтималдық шежіресі, 20 (4): 2043–2088, дои:10.1214 / aop / 1176989540
• Лион, Рассел; Перес, Юваль, Ағаштар мен желілердегі ықтималдылық