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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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ą -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 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 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ć , ż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 . Przyjmijmy dla uproszczenia, że wynik jest liczbą całkowitą. Aby zwiększyć prawdopodobieństwo uzyskania prawidłowej odpowiedzi wykonujemy algorytm -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 wystąpienia pojedynczej krawędzi.