Rachunek Prawdopodobieństwa i Statystyka (UW) Ćwiczenia 6

Zadanie 1

W zadaniu dotyczącym problemu kolekcjonera kuponów (zadanie 2 z ćwiczeń 5, część "Liniowość wartości oczekiwanej") oszacuj prawdopodobieństwo tego, że liczba gum, które trzeba kupić aby zdobyć wszystkie historyjki przekroczy swoją wartość oczekiwaną $c$-krotnie:

1. z nierówności Markowa,
2. z nierówności Czebyszewa,
3. obliczając dla pojedynczej historyjki prawdopodobieństwo tego, że ciągle jej nie mamy po kupieniu $cEX$ gum.

Porównaj uzyskane oszacowania.

Zadanie 2

W wyborach bierze udział dwóch kandydatów: A i B. Przeprowadzamy sondaż przedwyborczy. W ramach sondażu pytamy $n$ osób o to na którego kandydata zamierzają głosować. Zakładamy, że każda z pytanych osób została losowo i niezależnie od pozostałych wybrana ze zbioru osób uprawnionych do głosowania (w szczególności nie wykluczamy powtórzeń). Interesuje nas oszacowanie poparcia kandydata A? Oszacuj jak duże powinno być $n$, żeby prawdopodobieństwo popełnienia błędu względnego większego niż 1% było mniejsze niż 5%:

1. z nierówności Czebyszewa
2. z nierówności Chernoffa.

Zadanie 3

Dysponujemy algorytmem, który wypisuje prawidłową odpowiedź z prawdopodobieństwem $p>\frac{1}{2}$. Przyjmijmy dla uproszczenia, że wynik jest liczbą całkowitą. Aby zwiększyć prawdopodobieństwo uzyskania prawidłowej odpowiedzi wykonujemy algorytm $n$-krotnie i za odpowiedź uznajemy medianę z otrzymanych wyników. Oszacuj prawdopodobieństwo uzyskania prawidłowej odpowiedzi.

Zadanie 4

W zadaniu dotyczącym wierzchołków izolowanych (zadanie 4 z ćwiczeń 5, część "Liniowość wartości oczekiwanej") oszacuj prawdopodobieństwo tego, że w losowym grafie nie ma wierzchołków izolowanych. Zbadaj zależność otrzymanego wyniku od prawdopodobieństwa $p$ wystąpienia pojedynczej krawędzi.