Janson ojämlikhet

I den matematiska sannolikhetsteorin är Jansons ojämlikhet en samling relaterade ojämlikheter som ger en exponentiell gräns för sannolikheten för att många relaterade händelser ska inträffa samtidigt genom deras parvisa beroende . Informellt innebär Jansons ojämlikhet att man tar ett urval av många oberoende slumpmässiga binära variabler och en uppsättning delmängder av dessa variabler och begränsar sannolikheten att urvalet kommer att innehålla någon av dessa delmängder genom deras parvisa korrelation.

Påstående

Låt $\Gamma$ vara vår uppsättning variabler. Vi avser att sampla dessa variabler enligt sannolikheter $p=(p_{i}\in [0,1]:i\in \Gamma )$ . Låt $\Gamma _{p}\subseteq \Gamma$ vara den slumpmässiga variabeln för delmängden $\Gamma$ som inkluderar $i\in \Gamma$ med sannolikhet $p_{i}$ . Det vill säga, oberoende, för varje $i\in \Gamma :\Pr[i\in \Gamma _{p}]=p_{i}$ .

Låt $S$ vara en familj av delmängder av $\Gamma$ . Vi vill binda sannolikheten för att någon $A\in S$ är en delmängd av $\Gamma _{p}$ . Vi kommer att binda det med förväntan på antalet $A\in S$ så att ${\displaystyle A\subseteq \Gamma _{p}} ,$ som vi kallar $\ lambda$ , och en term från den parvisa sannolikheten att vara i ${\displaystyle \Gamma _{p}} ,$ som vi kallar $\Delta$ .

För $A\in S$ , låt $I_{A}$ vara den slumpmässiga variabeln som är en om $A\subseteq \Gamma _{p}$ och noll annars. Låt $X$ vara de slumpmässiga variablerna för antalet uppsättningar i $S$ som finns inuti $\Gamma _{p}$ : $X=\summa _{A\in S}I_{A}$ . Sedan definierar vi följande variabler:

$\lambda =\operatörsnamn {E} \left[\summa _{A\in S}I_{A}\right]=\ operatornamn {E} [X]$

${\displaystyle \Delta ={\frac {1}{2}}\summa _{ A\neq B,A\cap B\neq \emptyset }\operatörsnamn {E} [I_{A}I_{B}]} Δ ¯ = λ + 2$

${\Delta }}=\ lambda +2\Delta }$

Då är Janson-ojämlikheten:

$\Pr[X=0]=\Pr[\forall A\in S:A\not \subset \Gamma _{p}]\leq e^{-\lambda +\Delta }$

och

$\Pr[X=0]=\Pr[\forall A\in S:A\not \ delmängd \Gamma _{p}]\leq e^{-{\frac {\lambda ^{2}}{\bar {\Delta }}}}$

Svans bunden

Janson utökade senare detta resultat för att ge en svans bunden av sannolikheten för att endast ett fåtal uppsättningar skulle vara delmängder. Låt $0\leq t\leq \lambda$ ge avståndet från det förväntade antalet delmängder. Låt $\phi (x)=(1+x)\ln(1+x)-x$ . Då har vi

$\Pr(X\leq \lambda -t)\leq e^{-\varphi (-t/\lambda )\lambda ^{2}/{\bar {\Delta }}}\leq e^{-t^{2}/\left(2{\bar {\ Delta }}\right)}$

Används

Jansons Ojämlikhet har använts i pseudoslumpmässighet för gränser på kretsar med konstant djup . Forskning som ledde till dessa ojämlikheter motiverades ursprungligen av att uppskatta kromatiska antal slumpmässiga grafer .