====== Algorytmy probabilistyczne - Lista 1. ======

===== Zadanie 1 =====
http://en.wikipedia.org/wiki/Monty_Hall_problem

===== Zadanie 2 =====

$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$

===== Zadanie 3 =====

$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)$

===== Zadanie 4 =====

$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))$

===== Zadanie 5 =====

<code python>
las_vegas(args):
  while true:
    a = monte_carlo(args)
    if a is correct: return
</code>

[[http://www.wolframalpha.com/input/?i=+Z+%3D+y%28T%2Bt%29+%2B+%281-y%29%28T%2Bt%2BZ%29|Równanie na wartość oczekiwaną]]

===== Zadanie 6 =====

$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)$

===== Zadanie 7 =====

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}$

===== Zadanie 8 =====

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}})$