Zasadniczo wiążą się z tym trzy pytania.
Wiem, że mi( Xk) = ( nk) ⋅str( k2)) , ale jak to udowodnić?
Korzystasz z liniowości oczekiwań i sprytnego przepisywania. Przede wszystkim zwróć uwagę, że
Teraz, biorąc pod uwagę oczekiwanie na , można po prostu wyciągnąć sumę (z powodu liniowości) i uzyskać
Wyciągając sumę, wyeliminowaliśmy wszystkie możliwe zależności między podzbiorami węzłów. Jakie jest zatem prawdopodobieństwo, że jest kliką? Cóż, bez względu na to, z czego składa się , wszystkie prawdopodobieństwa krawędzi są równe. DlategoXkE(Xk)= ∑ T ⊆ V ,
Xk= ∑T.⊆ V.,| T.| =k1 [T jest klika ] .
XkTTPr[T to klika]=p ( kE ( Xk) = ∑T.⊆ V.,| T.| =kmi ( 1 [ T jest klika ] ) = ∑T.⊆ V.,| T.| = kP. r [T jest klika ]
TT TE(Xk)=p ( kPr[T is clique]=p(k2), ponieważ wszystkie krawędzie tego podgrafu muszą być obecne. I wtedy wewnętrzny warunek sumy nie zależy już od , pozostawiając nam .
TE(Xk)=p(k2)∑T⊆V,|T|=k1=(nk)⋅p(k2)
Jak to pokazać dla :E ( X log 2 n ) ≥ 1n→∞E(Xlog2n)≥1
Nie jestem do końca pewien, czy jest to w ogóle poprawne. Stosując ograniczenie do współczynnika dwumianowego, otrzymujemy
E(Xlogn)=(nlogn)⋅p(logn2)≤⎛⎝nep(logn)4logn⎞⎠logn=(ne⋅n(logp)/4logn)logn.
(Zauważ, że z grubsza górną granicę przez .) Jednak teraz można wybrać i uzyskać to , co powoduje, że cały termin przechodzi do dla dużej . Czy może brakuje Ci niektórych założeń dotyczących ?
p−1+logn2plogn4p=0.001log20.001≈−9.960np