P(x \in X) = P(y \in Y) = \frac 1 2 (zmienne są i.i.d. parami)
P(X \subseteq Y) = P(\forall_{x \in \{1, \dots, n\}} x \in X ⇒ x \in Y) = P(\bigcap_{x \in \{1, \dots, n\}} (x \in X ⇒ x \in Y)) = \prod_{x \in \{1, \dots, n\}} P(x \in X ⇒ x \in Y) = \prod_{x \in \{1, \dots, n\}} \frac 3 4 = (\frac 3 4)^n
P(X \cup Y = \{1, \dots, n\}) = P(\forall_{x \in \{1, \dots, n\}} x \in X \vee x \in Y) = \prod_{x \in \{1, \dots, n\}} P(x \in X \vee x \in Y) = (\frac 3 4)^n
P(\varepsilon_1) = \prod_{i=1}^1 P(\varepsilon_i | \bigcap_{j=1}^{i-1} \varepsilon_j)
P(\bigcap_{i=1}^k \varepsilon_i) = P(\bigcap_{i=1}^{k-1} \varepsilon_i \cap \varepsilon_k) = P(\bigcap_{i=1}^{k-1} \varepsilon_i) P(\varepsilon_k|\bigcap_{i=1}^{k-1} \varepsilon_i) = \prod_{i=1}^{k-1} P(\varepsilon_i | \bigcap_{j=1}^{i-1} \varepsilon_j) P(\varepsilon_k|\bigcap_{i=1}^{k-1} \varepsilon_i) = \prod_{i=1}^k P(\varepsilon_i | \bigcap_{j=1}^{i-1} \varepsilon_j)
alternatywnie:
P(\varepsilon_1) \cdot P(\varepsilon_2|\varepsilon_1) \cdot P(\varepsilon_3|\varepsilon_1 \cap \varepsilon_2) \cdots P(\varepsilon_k|\bigcap_{i=1}^{k-1} \varepsilon_i) = P(\varepsilon_1) \cdot \frac {P(\varepsilon_2 \cap \varepsilon_1)} {P(\varepsilon_1)} \cdot \frac {P(\varepsilon_3 \cap \varepsilon_1 \cap \varepsilon_2)} {P(\varepsilon_2 \cap \varepsilon_1)} \cdots \frac {P(\bigcap_{i=1}^{k} \varepsilon_i)} {P(\bigcap_{i=1}^{k-1}\varepsilon_i)} = P(\bigcap_{i=1}^k \varepsilon_i)
h(X_1, \dots, X_k) = \sum_{i=1}^k a_iX_i + b
E(h(X_1, \dots, X_k)) = E(\sum_{i=1}^k a_iX_i + b) = \sum_{i=1}^k a_iE(X_i) + b = h(E(X_1), \dots, E(X_k))
las_vegas(args): while true: a = monte_carlo(args) if a is correct: return
X - success
P(X) = 1 - \epsilon_1
(1-P(X))^k \leq \epsilon_2 ⇒ \epsilon_1^k \leq \epsilon_2 ⇒ k \geq \log_{\epsilon_1}(\epsilon_2)
Na początku, każdy wierzchołek leży na co najmniej |C| krawędziach (bo inaczej istniałby mniejszy cut). Zatem liczba krawędzi w grafie jest nie mniejsza niż \frac {|C|n} 2.
Zatem prawdopodobieństwo nie wylosowania krawędzi z C (P(\varepsilon_1)) jest nie mniejsze niż 1 - \frac{2|C|}{|C|n} = 1 - \frac 2 n
W i-tej iteracji dostajemy graf z n-(i-1) wierzchołkami, więc P(\varepsilon_i | \bigcap_{j=1}^{i-1} \epsilon_j) = 1 - \frac 2 {n-i+1}
Pierwsza metoda:
X - sukces w jeden próbie zwykłego algorytmu
P(X) = P(\bigcap_i^{n-2} \varepsilon_i) = \prod_{i=1}^{n-2} P(\varepsilon_i | \bigcap_{j=1}^{i-1} \varepsilon_j) \geq (1 - \frac 2 {n})(1 - \frac 2 {n-1})\cdots(1 - \frac 2 {3}) = \frac {n-2} n \frac {n-3} {n-1} \frac {n-4} {n-2} \cdots \frac 1 3 = \frac 2 {n(n-1)}
Zatem po dwóch niezależnych próbach P \geq 1 - (1 - P(X))^2 = 1 - (\frac {n(n-1)-2} {n(n-1)})^2 = 1 - \frac {(n-2)^2(n+1)^2}{n^2(n-1)^2} = \frac {n^2(n-1)^2 - (n-2)^2(n+1)^2} {n^2(n-1)^2} = \frac {4(n^2-n-1)}{(n-1)^2n^2}
Druga metoda:
\prod_{i=1}^k P(\varepsilon_i | \bigcap_{j=1}^{i-1} \varepsilon_j) (1 - (1 - \prod_{i=k+1}^{n-2} P(\varepsilon_i | \bigcap_{j=1}^{i-1} \varepsilon_j))^{\frac{2n-4-k}{n-2-k}}) = (1 - \frac 2 {n})(1 - \frac 2 {n-1})\cdots(1 - \frac 2 {n-k+1}) (1 - (1 - (1 - \frac 2 {n-k})(1 - \frac 2 {n-k-1})\cdots(1 - \frac 2 {3}))^{\frac{2n-4-k}{n-2-k}}) =
= \frac {(n-k)(n-k-1)}{n(n-1)}(1 - (1 - \frac {2}{(n-k)(n-k-1)})^{\frac{2n-4-k}{n-2-k}})