Ćwiczenia

Ćwiczenia 1: Schemat klasyczny

Zadania elementarne

Zadanie 1

Losujemy 2 kule spośród \(c\) czerwonych i \(b\) białych. Jakie jest prawdopodobieństwo wylosowania kul różnych kolorów?

Zadanie 2

90-osobowy rocznik został podzielony losowo na 3 równoliczne potoki. Jakie jest prawdopodobieństwo, że Jaś i Małgosia znajdą się w tym samym potoku?

Zadanie 3

Jakie jest prawdopodobieństwo, że w losowym ustawieniu \(n\) wież na szachownicy \(n \times n \) żadne 2 wieże się nie atakują?

Zadanie 4

Rozdajemy 7 kart ze standardowej talii 52 kart. Jakie jest prawdopodobieństwo tego, że wśród tych kart są:

  1. dokładnie 3 asy?
  2. dokładnie 2 króle?
  3. dokładnie 3 asy lub dokładnie 2 króle?

Zadanie 5

Rzucamy trzema kostkami. Sumy 11 i 12 można uzyskać na tyle samo sposobów. Czy są one równie prawdopodobne?

Zadanie 6

Jaś i Małgosia rzucają monetami: Jaś rzuca \(n\) razy, a Małgosia \(n+1\) razy. Jakie jest prawdopodobieństwo tego, że Małgosi wypadnie więcej orłów niż Jasiowi?

Zadania trudniejsze i bardziej koncepcyjne

Zadanie 1

W klasie jest \(n\) osób. Obliczyć prawdopodobieństwo tego, że pewne dwie osoby mają urodziny tego samego dnia? Jak duże musi być \(n\), aby to prawdopodobieństwo było większe niż \(\frac{1}{2}\)?

Zadanie 2

10 osób wsiadło na parterze 10-piętrowego budynku do pustej windy. Jakie jest prawdopodobieństwo tego, że każda wysiądzie na innym piętrze? Zakładamy, że każdy układ wysiadających jest równie prawdopodobny)

Zadanie 3

\(n\) listów włożono losowo do \(n\) zaadresowanych kopert (każdy list ma swojego docelowego adresata; wszyscy adresaci są różni). Jakie jest prawdopodobieństwo tego, że:

  1. żaden list nie trafił do właściwej koperty?
  2. dokładnie \(k\) listów trafiło do właściwych kopert?

Zadanie 4 - optymalizacja wyboru żony (ew. męża)

Przyjmijmy, że mamy szansę spotkać w życiu \(n\) kobiet - potencjalnych kandydatek na żonę (ew. mężczyzn - kandydatów na męża). Każdą z kandydatek możemy porównać do każdej z wcześniejszych kandydatek (biorąc pod uwagę wiek, charakter, poczucie humoru, urodę etc). Jesli nie wybierzemy danej kandydatki to już więcej jej nie zobaczymy. Naszym celem jest opracowanie strategii, która maksymalizuje prawdopodobieństwo wyboru najlepszej kandydatki. Ograniczymy się przy tym do strategii następującej postaci:

  1. odrzuć \(k-1\) pierwszych kandydatek, a następnie
  2. wybierz pierwszą kandydatkę lepszą od wszystkich wcześniejszych.

W tym zadaniu nie musisz dowodzić, że optymalna strategia ma taką właśnie postać, choć z pewnością warto się nad tym zastanowić.
Twoim zadaniem jest ustalenie:

  1. Jakie prawdopodobieństwo sukcesu gwarantuje ta strategia?
  2. Jaka jest optymalna wartość parametru \(k\) i jakie prawdopodobieństwo sukcesu odpowiada tej wartości?

Zadanie 5

Co jest bardziej prawdopodobne:

  • uzyskanie co najmniej 1 szóstki w 6 rzutach?
  • uzyskanie co najmniej 2 szóstek w 12 rzutach?
  • uzyskanie co najmniej 3 szóstek w 18 rzutach?

    Ćwiczenia 2: Prawdopodobieństwo warunkowe

    Prawdopodobieństwo warunkowe, wzór iloczynowy

    Zadanie 1

    Wybrano losowo jedną z trzech kartek, pomalowanych z obu stron: czarno-czarnej, czarno-białej i biało-białej, a następnie wybrano losowo jedną z jej stron. Jeśli ta strona jest czarna, to jakie jest prawdopodobieństwo tego, że druga też jest czarna?

    Zadanie 2

    Wybieramy losowo numer z książki telefonicznej i pod niego dzwonimy. Osobę, która odbierze pytamy o to, czy ma dwójkę dzieci, a jeśli okaże się, że tak, to:

    1. pytamy, czy ma syna. Jeśli okaże się, że tak, to jakie jest prawdopodobieństwo tego, że drugie dziecko też jest synem?
    2. pytamy, czy któreś z dzieci ma na imię Jaś. Jeśli okaże się, że tak, to jakie jest prawdopodobieństwo tego, że drugie dziecko też jest synem?

    Uwaga: W tym zadaniu trzeba oczywiście przyjąć pewne założenia co do częstości urodzin chłopców/dziewczynek oraz sposobu w jaki nadawane są im imiona.

    Zadanie 3

    Na inżynierii oprogramowania 16 studentów ma być podzielonych na 4 zespoły. Wśród nich jest 4 pracujących, z doświadczeniem w projektowaniu dużych systemów. Jakie jest prawdopodobieństwo, że każdy z nich trafi do innej grupy?
    Uwaga: Nie rozwiązuj tego zadania wprost ze schematu klasycznego. Zamiast tego użyj pojęcia prawdopodobieństwa warunkowego.

    Zadanie 4

    W 3-osobowym pojedynku trzech kawalerów A, B, C strzela do wybranego przez siebie celu w kolejności A, B, C cyklicznie, aż zostanie tylko jeden z nich. Przypuśćmy, że A trafia z prawdopodobieństwem 0.3, B trafia zawsze, a C z prawdopodobieństwem 0.5. Jaką strategię powinien przyjąć A?
    Uwaga: Zakładamy, że pozostali strzelcy postępują racjonalnie, tzn. tak aby maksymalizować swoje szanse przeżycia.

    Wzór na prawdopodobieństwo całkowite

    Zadanie 1

    Grasz w turnieju szachowym, w którym z 50% graczy masz szansę wygrania 30%, z 25% graczy szansę 40% i z 25% graczy szansę 50%. Pierwszą partię rozgrywasz z losowym przeciwnikiem. Jakie sa twoje szanse wygrania?

    Zadanie 2 - model urnowy Polyi

    W urnie są dwie kule: biała i czarna. \((n-2)\)-krotnie losujemy kulę z urny, po czym wrzucamy ją z powrotem wraz z drugą kulą tego samego koloru. Jakie jest prawdopodobieństwo tego, że po zakończeniu losowań wśród \(n\) kul dokładnie \(k\) jest białych?

    Zadanie 3

    Mamy \(n\) urn. W \(i\)-tej urnie znajduje się \(i-1\) kul białych i \(n-i\) kul czarnych. Wybieramy losowo urnę, a następnie losujemy z niej dwie kule. Oblicz prawdopodobieństwo tego, że są to kule różnych kolorów jeśli losujemy:

    1. bez zwracania,
    2. ze zwracaniem.

    Twierdzenie Bayesa

    Zadanie 1 - problem Monty Halla

    Gracz w teleturnieju wybiera jedną z 3 zasłon. Za jedną z zasłon jest ukryty samochód, za pozostałymi nic nie ma. Prowadzący odsłania jedną z pozostałych dwóch zasłon i pokazuje, że niczego za nią nie ma, po czym daje graczowi szansę na zmianę wyboru.

    • Czy gracz powinien zmienić swój wybór?
    • Jakie maksymalne prawdopodobieństwo sukcesu może uzyskać?
    • Jak zmieni się sytuacja, jeśli zasłon jest 100, a prowadzący odsłania wszystkie poza wskazaną przez gracza i jedną inną?

    Uwaga: Przeanalizowanie konkretnej sytuacji opisanej w zadaniu jest istotnie bardziej skomplikowane niż porównanie strategii "zawsze zmieniaj" ze strategią "nigdy nie zmieniaj". Czy widzisz dlaczego?

    Zadanie 2 - dylemat więźnia

    Trzech więźniów A,B,C oczekuje na wykonanie kary śmierci. Więzień A dowiedział się, że dwóch więźniów zostanie ułaskawionych, ale nie wie o których więźniów chodzi. Chciałby o to zapytać strażnika, ale ponieważ ten odmawia udzielania informacji dotyczących jego losu, prosi go o ujawnienie jednego z ułaskawionych więźniów spośród B,C. Strażnik ponownie odmawia twierdząc, że w ten sposób zmniejszyłby szansę A na ułaskawienie z 2/3 do 1/2, a nie chce tego robić, bo lubi A. Czy strażnik słusznie odmawia?

    Zadanie 3 - kontynuacja zadania 1 z poprzedniej serii

    Przypuśćmy, że udało ci sie wygrać pierwsza partię. Jakie jest prawdopodobieństwo, że grałeś z graczem 3-go rodzaju?

    Zadanie 4

    Mamy do dyspozycji 3 telefony. Wiemy, że jeden z nich zawsze działa, drugi nigdy nie działa (ale zjada monety), a trzeci działa z prawdopodobieństwem \(p=\frac{1}{2}\) (w pozostałych przypadkach zjada monety). Próbujemy zadzwonić z jednego z automatów i zjada on monetę. Zmieniamy automat i udaje nam się zadzwonić. Próbujemy raz jeszcze (nie zmieniając telefonu) i znów się udaje. Jakie jest prawdopodobieństwo tego, że telefon z którego zadzwoniliśmy 2 razy jest tym, który zawsze działa? Czy odpowiedź zmieniłaby się, gdyby nie było w zadaniu pierwszej (nieudanej) próby?

    Zadanie 5

    W sejmie mamy dwie partie. Posłowie partii A nigdy nie zmieniają zdania na żaden temat, a każdy z posłów partii B zmiena zdanie pomiędzy na temat głosowanej ustawy pomiędzy dwoma jej głosowaniami z prawdopodobieństwem \(p\). Wiadomo, że posłowie partii A stanowią frakcję \(f\) wszystkich posłów, pozostali pochodzą z partii B. Obserwujemy losowego posła i głosuje on w ten sam sposób w dwóch kolejnych głosowaniach. Jakie jest prawdopodobieństwo tego, że pochodzi on z partii A?

    Zadanie 6

    Dane są dwie urny. W pierwszej urnie znajdują się 2 czerwone kule i 1 czarna, w drugiej 101 czerwonych i 100 czarnych. Ktoś wybiera losowo urnę (nie wiemy którą), z wybranej urny losuje kulę i mówi nam jakiego jest ona koloru. Następnie z tej samej urny losowana jest druga kula, przy czym możemy zażądać, aby uprzednio pierwsza kula wróciła do urny. Naszym zadaniem jest zgadnięcie z której urny są losowane kule. Jak wygląda optymalna strategia?
    Uwaga: To zadanie jest dość pracochłonne.

    Zadanie 7 - doświadczenie Laplace'a

    Danych jest \(N+1\) urn. W \(i\)-tej urnie znajduje się \(i\) kul białych i \(N-i\) kul czerwonych, dla \(i=0,...,N\). Wybieramy losowo urnę, a następnie \(n\)-krotnie losujemy z wybranej urny jedną kulę ze zwracaniem. Przypuśćmy, że za każdym razem była to kula czerwona. Jakie jest prawdopodobieństwo tego, że kolejna kula wylosowana z tej urny też będzie czerwona?
    Uwaga: Laplace użył tego rozumowania do argumentowania na temat prawdopodobieństwa tego, że słońce następnego dnia wzejdzie na podstawie tego, że wzeszło odpowiednio wiele razy wcześniej. Co sądzisz o tym "zastosowaniu"?

    Ćwiczenia 3: Niezależność zdarzeń

    Zadanie 1

    Pokazać, że skończona rodzina zdarzeń niezależnych, każde o prawdopodobieństwie mniejszym niż 1, nie może pokryć całej przestrzeni zdarzeń.

    Zadanie 2

    Obiecującej tenisistce ojciec obiecuje nagrodę, jeśli ta wygra 2 kolejne mecze z 3 rozegranych na przemian z nim samym oraz mistrzem klubu. Szanse na wygranie pojedynczego meczu z mistrzem są mniejsze, niż z ojcem. Zawodniczka może sama zdecydować, z którym przeciwnikiem zmierzy się jako pierwszym. Którego powinna wybrać?

    Zadanie 3

    Ekspert podejmuje prawidłową decyzję z prawdopodobieństwem \(p_e>\frac{1}{2}\), ignorant podejmuje ją z prawdopodobieństwem \(p_i=\frac{1}{2}\).
    Jaka komisja częściej podejmuje prawidłowe decyzje:

    • składająca się z pojedynczego eksperta, czy
    • składająca się z dwóch ekspertów i jednego ignoranta,
      • jeśli decyzje podejmowane są metodą większościową?
        Uwaga: W rozwiązaniu możesz założyć, że członkowie komisji popełniają błędy niezależnie. Wyjaśnij dlaczego to założenie nie zawsze ma sens.

        Zadanie 4 (dla bardzo bardzo chętnych)

        \(N=100\) więźniów otrzymuje następującą propozycję: W specjalnym pokoju na stole stoi 100 pudełek. Do pudełek wrzucono losowo karteczki z liczbami \(1\ldots 100\), do każdego pudełka jedną. Więźniowie są ponumerowani \(1 \ldots 100\) i wchodzą do pokoju jeden po drugim: najpierw więzień 1, potem 2, itd. Każdy z więźniów może otworzyć dowolnych 50 pudełek i obejrzeć znajdujące się w nich kartki. Pudełka wolno oglądać jedno po drugim, tzn. w decyzji o tym, które pudełko obejrzeć można uwględnić karteczki obejrzane w uprzednio otworzonych pudełkach. Przed wyjściem więzień musi zostawić wszystko tak jak zastał, nie może zostawiać żadnych znaków, zmieniać kolejności pudełek itp. Więźniowie którzy już byli w pokoju nie mogą się kontaktować z tymi, którzy jeszcze tam nie byli. Każdy z więźniów ma za zadanie znaleźć (tj. zobaczyć) kartkę ze swoim numerem. Jeśli wszystkim (!!!) więźniom się to uda, to wszyscy są wolni, wpp żaden. Jakie prawdopodobieństwo sukcesu można uzyskać?
        Przy niezależnym otwieraniu pudełek prawdopodobieństwo sukcesu wynosi \(2^{-100}\), a da się uzyskać ponad 30% - w tym celu trzeba mocno "uzależnić" od siebie sukcesy więźniów. Spróbuj skonstruować dla strategie więźniów w taki sposób, aby wszyscy odnieśli sukces jeśli permutacja kartek w pudełkach spełnia pewien warunek kombinatoryczny.

    Ćwiczenia 4: Dyskretne zmienne losowe

    Rozkład dwumianowy i Poissona

    Zadanie 1 (Kształt rozkładu dwumianowego)

    Rozważmy zmienną \(X \sim \textrm{Binom}(n,p)\). Niech \(K = \lfloor (n+1)p \rfloor\). Pokazać, że \( P(X=k) \) jest funkcją niemalejącą dla \(k \le K\), oraz malejącą dla \(k \ge K\).

    Zadanie 2 (Kształt rozkładu Poissona)

    Rozważmy zmienną \(X \sim \textrm{Pois}(\lambda) \). Niech \(K = \lfloor \lambda \rfloor\). Pokazać, że \( P(X=k) \) jest funkcją rosnącą dla \( k \le K\), oraz malejącą dla \(k \ge K\).

    Zadanie 3 (Rozkład Poissona jako granica rozkładów dwumianowych)

    Pokazać, że jeśli \(n_i \rightarrow \infty\) oraz \(n_i p_i \rightarrow \lambda\) (a zatem \(p_i \rightarrow 0\) ) to rozkłady \(\textrm{Binom}(n_i,p_i)\) zbiegają do rozkładu \(\textrm{Pois}(\lambda)\).

    Uwaga: Chodzi tu o zbieżność punktową, tzn. zbieżność prawdopodobieństw przyjęcia każdej konkretnej wartości.

    Zadanie 4

    Idziemy na przyjęcie na którym jest 500 osób. Jakie jest prawdopodobieństwo tego, że dokładnie dwie osoby będą miały tę samą datę urodzin (tj. miesiąc/dzień) co my? Rozwiązać na dwa sposoby:

    • użyć rozkładu dwumianowego,
    • przybliżyć rozkładem Poissona.

    Zadanie 5 (trudne)

    Gramy serię gier (mecz) z przeciwnikiem od którego jesteśmy słabsi, tzn. nasze prawdopodobieństwo wygrania pojedynczej gry jest równe \(p < 0.5\). Mecz składa się z parzystej liczby gier, wygrywamy jeśli wygramy więcej niż połowę gier. Możemy wybrać liczbę gier w meczu: 0, 2,4,6, itd. Jaką liczbę powinniśmy wybrać, aby zmaksymalizować prawdopodobieństwo zwycięstwa?

    Zadanie 6 (Zapałki Banacha)

    Palący matematyk nosi po jednym pudełku zapałek w lewej i prawej kieszeni spodni. Za każdym razem, gdy chce zapalić, wyciąga pudełko z losowej kieszeni. Jakie jest prawdopodobieństwo tego, że gdy wyciągnie w końcu puste pudełko, w drugim jest dokładnie \(k\) zapałek? Zakładamy, że zabawa zaczyna się z dwoma pudełkami po \(n\) zapałek każde.
    Uwaga: Uzyskany rozkład prawdopodobieństwa nazywa się ujemnym rozkładem dwumianowym. Czy widzisz dlaczego?

    Rozkład geometryczny

    Zadanie 1 (Własność braku pamięci)

    Pokazać, że zmienna o rozkładzie geometrycznym "nie ma pamięci", tzn. dla dowolnych \(0\le m < n\) zachodzi \( P(X = n| X > m) = P( X = n-m) \). Nieco mniej formalnie: jeśli czekamy na orła i wypadło już \(m\) kolejnych reszek, to prawdopodobieństwo tego, że pierwszy orzeł wypadnie za \(n-m\) rzutów jest takie samo jak gdyby całej przeszłości (t.j. \(m\) reszek) nie było. Wiele osób sądzi, że \(P(X=n| X>m) > P(X=n-m) \) - orzeł niejako "należy się".

    Zadanie 2 (Brak pamięci definiuje rozkład geometryczny)

    Pokaż, że każda zmienna przyjmująca wartości \(1,2,\ldots\) i nie mająca pamięci (zobacz poprzednie zadanie) ma rozkład geometryczny. Jest to więc własność definiująca rozkład geometryczny.

    Zadanie 3

    Rzucamy monetą do momentu, kiedy wypadnie drugi orzeł. Pokazać, że jeśli ten drugi orzeł wypada w \(n\)-tym rzucie, prawdopodobieństwo wypadnięcia pierwszego orła w \(i\)-tym rzucie (\(i=1,\ldots,n-1\))jest takie samo dla każdego \(i\).

    Niezależność zmiennych losowych

    Zadanie 1 (Stabilność rozkładu dwumianowego i Poissona)

    Jaki rozkład ma suma dwóch niezależnych zmiennych losowych o rozkładzie dwumianowym z tym samym \(p\)? Jaki rozkład ma suma dwóch niezależnych zmiennych losowych o rozkładzie Poissona?

    Zadanie 2

    Pokazać, że jeśli \(X\) i \(Y\) są niezależne i \(f,g: \mathbb{R} \rightarrow \mathbb{R}\), to \(f(X)\) i \(g(Y)\) są niezależne.

    Zadanie 3 ("Dwumianowe przerzedzanie" rozkładu Poissona)

    Jaki jest rozkład liczności potomstwa owada, u którego liczba złożonych jaj ma rozkład Poissona, i z każdego z jaj niezależnie wykluwa się młode z prawdopodobieństwem p?

    Zadanie 4

    W sytuacji jak w poprzednim zadaniu pokazać, że zmienne losowe opisujące wyklute i niewyklute jaja są niezależne.

    Zadanie 5

    Niech \(X, Y\) będą niezależne o rozkładzie Poissona. Pokazać, że rozkład \(X | X+Y=n\) jest dwumianowy, t.j. \( P(X=k|X+Y=n) = P(Z=k)\) dla pewnej zmiennej \(Z\) o rozkładzie dwumianowym.

    Zadanie 6

    Pokazać, że jeśli \(X,Y\) są niezależnymi zmiennymi o rozkładzie geometrycznym, to \(\min(X,Y)\) też ma rozkład geometryczny.

    Ćwiczenia 5: Wartość oczekiwana i wariancja

    Wartość oczekiwana i wariancja

    Zadanie 1

    Obliczyć wartość oczekiwaną i wariancję rozkładu geometrycznego.

    Zadanie 2

    Obliczyć wartość oczekiwaną i wariancję rozkładu Poissona.

    Zadanie 3

    Jan ma przyjaciela, który jest nałogowym hazardzistą i uwielbia grać w ruletkę. Za każdym razem stawia wtedy 10zł na liczbę 13, i jeśli ta liczba wypada (a jest ona jedną z 38 liczb na kole ruletki), wygrywa z powrotem swoje 10zł oraz dodatkowe 350zł, w przeciwnym przypadku traci postawione 10zł. Jan postanawia wyleczyć go z nałogu. Przed każdą wizytą w kasynie zakłada się z przyjacielem o to, że po 36 obstawieniach będzie na minusie. Stawka zakładu wynosi 200zł. Jak dobrze działa takie lekarstwo?

    Zadanie 4

    Gramy w następującą grę: Ktoś rzuca monetą, aż do wypadnięcia pierwszego orła. Powiedzmy, że orzeł wypadł w \(i\)-tym rzucie. Następnie do dwóch kopert wkłada odpowiednio \(2^i\) i \(2^{i+1}\) zł. Dostajemy losowo wybraną kopertę i mamy zdecydować, czy chcemy wziąć tę drugą czy nie.

    1. Powiedzmy, że otrzymaliśmy kopertę z kwotą \(2^i\) zł. Obliczyć wartość oczekiwaną kwoty w drugiej kopercie i porównać z \(2^i\).
    2. Dlaczego wynik z poprzedniego punktu wydaje się nie mieć sensu?
    3. Jak to się stało, że otrzymaliśmy tak absurdalny wynik? Wyjaśnij.
    4. Jeśli nie sądzisz, że te wyniki są absurdalne, to spróbuj z \(3^i\) i \(3^{i+1}\) zamiast \(2^i\) i \(2^{i+1}\).

    Zadanie 5 (Paradoks petersburski)

    Kasyno oferuje następującą grę: Krupier rzuca monetą do momentu wypadnięcia pierwszego orła. Jeśli pierwszy orzeł wypada w \(i\)-tym rzucie, wygrywamy
    \(2^i\) zł. Ile warto zapłacić za granie w tę grę? Zastanów się nad praktycznym sensem tego wyniku.

    Liniowość wartości oczekiwanej

    Zadanie 1

    Na kinowy seans "dla singli" spóźniło się 15 singli: 8 mężczyzn i 7 kobiet. Ponieważ jest już ciemno, a spóźnialscy nie chcą przeszkadzać innym, siadają wszyscy losowo w pierwszym rzędzie, który ma 16 miejsc (czyli o jedno za dużo). Ile będzie średnio par mężczyzna-kobieta siedzących obok siebie?

    Zadanie 2 (Kolekcjoner kuponów)

    Kupujemy gumy do żucia, w każdej znajduje się jedna z \(n\) historyjek. Ile gum trzeba średnio kupić, żeby zebrać wszystkie historyjki? Jaka jest wariancja tej wielkości? Zakładamy, że historyjki znajdujące się w kolejno kupowanych gumach są losowe (każda równie prawdopodobna) i niezależne od siebie.

    Zadanie 3

    Wrzucamy losowo \(n\) kul do \(n\) urn. Oblicz wartość oczekiwaną i wariancję liczby niepustych urn.

    Zadanie 4

    W \(n\)-wierzchołkowym grafie losowym \(G\) każda krawędź istnieje z prawdopodobieństwem \(p\) niezależnie od pozostałych krawędzi. Oblicz wartość oczekiwaną liczby wierzchołków izolowanych i wariancję tej wielkości.

    Funkcje tworzące prawdopodobieństwa

    Zadanie 1

    Oblicz wartość oczekiwaną i wariancję rozkładu Poissona korzystając z funkcji tworzących prawdopodobieństwa.

    Zadanie 2

    Oblicz wartość oczekiwaną i wariancję rozkładu geometrycznego korzystając z funkcji tworzących prawdopodobieństwa.

    Ćwiczenia 6: Nierówności

    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

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

    • z nierówności Czebyszewa
    • 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.

    Ćwiczenia 7: Ciągłe zmienne losowe

    Zadanie 1

    Zakładając, że potrafimy próbkować z rozkładem jednostajnym z odcinka \([0,1]\), w jaki sposób można próbkować z dowolnego rozkładu mając daną jego dystrybuantę?

    Zadanie 2

    Oblicz wariancję rozkładu wykładniczego.

    Zadanie 3

    Uzasadnij nieformalne stwierdzenie, że rozkład wykładniczy jest "ciągłą wersją" rozkładu geometrycznego. W tym celu porównaj dystrybuanty tych rozkładów.

    Zadanie 4 (brak pamięci)

    Pokaż, że zmienna losowa \(X\) o wartościach nieujemnych spełnia warunek \(P( X > s+t | X>t ) = P( X > s )\) dla wszystkich rzeczywistych \(s, t \ge 0\) wtw, gdy \(X\) ma rozkład wykładniczy.

    Zadanie 5

    Oblicz wariancję rozkładu normalnego.

    Zadanie 6 (wyścig zmiennych wykładniczych)

    Niech \(X_1,...,X_n\) niezależne zmienne o rozkładzie wykładniczym, \(X_i \sim \textrm{Exp}(\theta_i)\). Pokaż, że \(X=\min{X_i}\) ma rozkład wykładniczy z parametrem \(\theta_1+..+\theta_n\). Niech \(I\) będzie indeksem zmiennej o najmniejszej wartości. Pokaż, że \(P(I=k) = \theta_k/(\theta_1+...+\theta_n)\). Pokaż też, że zmienne \(X\) i \(I\) są niezależne.

    Ćwiczenia 8: Łańcuchy Markowa

    Zadanie 1

    Oblicz średnie czasy powrotu dla wszystkich stanów łańcucha Markowa o macierzy przejścia
    \(P = \left(\begin{array}{cc} \frac{1}{4} & \frac{3}{4} \\ \frac{2}{3} & \frac{1}{3}\\ \end{array}\right)\)
    wprost oraz korzystając z twierdzenia ergodycznego.

    Zadanie 2

    Dwóch graczy rzuca symetryczną monetą. Jeden obstawia, że najpierw pojawi się ciąg OOR, drugi - że ROO. Jakie prawdopodobieństwo wygranej ma każdy z graczy i jaki jest oczekiwany czas gry?

    Zadanie 3

    Na szalce \(2\times2\) hodujemy bakterie. Każde pole może zawierać jedną bakterię. Początkowo kolonia składa się z jednej bakterii. Co sekundę (jednocześnie) każda bakteria umiera z prawdopodobieństwem \(\frac{1}{2}\), a na każdym z pustych pól sąsiadujących w poprzedniej sekundzie z co najmniej jedną bakterią z prawdopodobieństwem \(\frac{1}{2}\) pojawia się nowa bakteria. Oblicz oczekiwany czas życia kolonii i prawdopodobieństwo tego, że kolonia kiedykolwiek zapełni całą szalkę.

    Zadanie 4

    Dwaj gracze rzucają na przemian symetryczną monetą. Wygrywa ten, który wyrzuci orła bezpośrednio po orle wyrzuconym przez poprzednika. Jakie jest prawdopodobieństwo tego, że wygra pierwszy gracz? Jaka jest oczekiwana liczba rzutów w całej grze?

    Zadanie 5

    Cztery mrówki znajdują się w jednym wierzchołku czworościanu. Co sekundę każda z nich z prawdopodobieństwem \(\frac{1}{4}\) przechodzi do sąsiedniego wierzchołka lub pozostaje na miejscu. Jaka jest oczekiwana liczba zajętych przez mrówki wierzchołków po upływie 1 sekundy? Jaki jest oczekiwany czas pierwszego zajęcia wszystkich wierzchołków jednocześnie?

    Zadanie 6

    Dwie cząstki znajdują się w przeciwległych wierzchołkach sześcianu. Co sekundę każda z nich z prawdopodobieństwem \(\frac{1}{4}\) przechodzi do sąsiedniego wierzchołka lub pozostaje na miejscu. Jaki jest oczekiwany czas kolizji cząstek (tzn. spotkania cząstek w jednym wierzchołku)?

    Zadanie 7

    Przy okrągłym stole siedzi trzech graczy \(A, B, C\), każdy z jednym żetonem. W każdym kroku gry, jednocześnie każdy gracz z co najmniej jednym żetonem z prawdopodobieństwem \(\frac{1}{2}\) przekazuje żeton graczowi po prawej. Grę wygrywa gracz, który zgromadzi wszystkie żetony. Ile wynosi oczekiwany czas gry?

    Zadanie 8 (Problem ruiny gracza)

    Gracz rozpoczyna grę z kapitałem \(k\) zł. W każdym kroku gry wygrywa 1zł z prawdopodobieństwem \(p = \frac{1}{2}\), i z tym samym prawdopodobieństwem \(1-p = \frac{1}{2}\) przegrywa 1zł. Gracz kończy grę, gdy albo wygra fortunę (= \(n\) zł) albo zbankrutuje. Oblicz:

    1. prawdopodobieństwo wygrania fortuny, oraz
    2. średnią liczbę kroków do zakończenia gry.

    Zadanie 9 (Model Ehrenfestów)

    W dwóch komorach znajdują się cząstki, w jednej \(k\), w drugiej \(n-k\). W każdym kroku jedna losowo wybrana cząstka zmienia komorę. Oblicz graniczny rozkład liczby cząstek w pierwszej komorze (t.j. rozkład stacjonarny odpowiedniego łańcucha Markowa). Jaki jest średni czas powrotu dla stanu w którym wszystkie cząstki są w pierwszej komorze?