Informatyka MIMUW

Szacowanie ogonów

Zdefiniowane w poprzednim wykładzie pojęcia wartości oczekiwanej umożliwia sformułowanie w języku rachunku prawdopodobieństwa następujących naturalnych pytań

• Ile średnio wypada orłów w $N$ rzutach symetryczną monetą?
• Ile średnio urn będzie pustych, jeśli wrzucimy losowo $N$ kul do $N$ urn?
• Jak długo średnio działa algorytm Quicksort dla losowej permutacji? (ew. jak duża może być ta średnia dla konkretnej permutacji jeśli element dzielący jest wybierany losowo)

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:

• z nierówności Markowa,
• z nierówności Czebyszewa,
• obliczając dla pojedynczej historyjki prawdopodobieństwo tego, że ciągle jej nie mamy po kupieniu $cEX$ gum.
  Porównaj uzyskane oszacowania.

Zadanie 2