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:
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%:
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.
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.