Wstęp do programowania

Metody Probabilistyczne

Egzamin

22.01.2007

Nazwisko:	
Imię:	
Nr indeksu:	
Pseudonim:	
1	2	3	4	5	6	7	8	

     
1.	W grupie 100 studentów  60 zdało egzamin z metod probabilistycznych a 45 z programowania.   Spośród tych co zdali metody probabilistyczne tylko 25 nie zdało programowania. 
a.	Jakie jest prawdopodobieństwo, że losowo wybrany student co najmniej jeden egzamin?
b.	Jakie jest prawdopodobieństwo, że grupie trzech losowo wybranych studentów, żaden nie zdał żadnego egzaminu?
c.	Jakie jest prawdopodobieństwo, że w grupie czterech losowo wybranych studentów jeden zdał programowanie, ale nie zdał metod probabilistycznych,  jeden nie zdał programowania, ale  zdał metody probabilistyczne, jeszcze inny zdał obydwa przedmioty, o ostatni nie zdał żadnego?

Najpierw krótka analiza (przepraszam za marny rysunek, ale po Word’em, to katorga):

60

35

10

Studenci, którzy zdali Programowanie

Studenci, którzy zdali Met. Probabilistyczne

•	Liczba osób, które zdały MetProb	 -	60
•	Liczba osób, które zdały Progr	-	45
•	Liczba osób, które zdały MetProb, ale nie zdały Progr	-	25
•	Liczba osób, które zdały zarówno MetProb jak i Progr	-	35
•	Liczba osób, które zdały Progr, ale nie zdały MetProb	-	10
•	Liczba osób, które nie zdały żadnego przedmiotu		-	30
•	Liczba osób, które zdały choć jeden przedmiot		-	70

Rozwiązanie a:	70/100

Rozwiązanie b:	Losujemy kolejno trzech studentów. To, że za pierwszym razem wylosujemy go  spośród 30, którzy nie zdali żadnego przedmiotu ma ppb’stwo=30/100.
Za drugim razem mamy już tylko 99 studentów, spośród których 29 nic nie zdało. Tak więc mamy ppb’stwo = 29/99. Za trzecim razem mamy ppb’stwo= 28/98.
Ostatecznie wynik wynosi (30/100)(29/99)(28/98).

Możemy też ten wynik osiągnąć inaczej. Otóż zdarzeniem sprzyjającym jest wylosowanie trzech osób spośród 30 (czyli jest ich 30 po 3), a wszystkich zdarzeń jest 100 po 3. jeśli podzielimy te liczby otrzymamy wynik.

Rozwiązanie c:  Podobnie jak powyżej można ten punkt rozwiązać na co najmniej dwa sposoby. Jeden z nich:
Zdarzeń sprzyjających jest 10 ∙ 25 ∙ 35 ∙ 30
Wszystkich zdarzeń jest 100 po 4.

Ostatecznie otrzymamy (10 ∙ 25 ∙ 35 ∙ 30)/(100 ∙ 99 ∙ 98 ∙ 97)

2.	Na dorocznym zawodach w sportach siłowych przeprowadzono badania współczynnika inteligencji (tzw. IQ) fanów poszczególnych atletów. Wyniki zestawiono w poniższej tabelce.

Siłacz 	Liczba fanów	Liczba fanów  o nieujemnym IQ	
Mięśniak	150	21	
Masa	125	13	
Packer	75	7	
Karczycho	100	9	

Jakie jest prawdopodobieństwo, że losowo wybrana z tej grupy osoba
a.	jest fanem Mięśniaka?
b.	ma nieujemny IQ?
Jakie jest prawdopodobieństwo, że w losowo wybranej grupie złożonej z jednego fana Mięśniaka, jednego fana Masy, jednego fana Packera i jednego fana Karczycha:
c.	wszyscy mają nieujemny IQ?
d.	dokładnie jedna osoba ma ujemny IQ?

Rozwiązanie a: Wszystkich osób jest 450, fanów Mięśniaka jest 21, więc odpowiedzią jest 21/450.

Rozwiązanie b:  Osób z nieujemnym IQ jest 50, więc odpowiedzią jest 50/450= 1/9.

Rozwiązanie c: Wiemy jaki jest skład grupy: 4-ech ludzi, po jednym fanie każdego siłacza. Naszą przestrzenią zdarzeń jest więc teraz zbiór 
={x, y, z, t: x jest Mięśniaka, y jest fanem Masy, z jest fanem Packera, t jest fanem Karczycha}

Szukamy prawdopodobieństwa zdarzenia(nazwijmy je A), że każdy fan z losowej czwórki z   ma nieujemne IQ. Zdarzenie to jest przekrojem czterech zdarzeń:
X= x ma nieujemne IQ; Y=y ma nieujemne IQ; Z= z ma nieujemne IQ;
T=t ma nieujemne IQ
Innymi słowy A=XYZT.
Ponieważ X, Y, Z i T są niezależne, więc Pr[A]=Pr[X] Pr[Y] Pr[Z] Pr[T]

Wiemy, że Pr[X]=21/150;  Pr[Y]=13/125;  Pr[Z]=7/75; Pr[T]=9/100.
Tak więc Pr[A] =21∙13∙7∙9/150 125∙75∙100∙

Każda z takich czwórek jest jednakowo prawdopodobna

Rozwiązanie d: 
Prawdopodobieństwo, że tą jedyną osobą z nieujemnym IQ jest Mięśniaka jest równe:
(21/150)(112/125)(68/75)(91/100)
Co bierze się z iloczyny prawdopodobieństw niezależnych zdarzeń, że fan Mięśniaka ma nieujemne IQ, a  fani pozostałych siłaczy mają ujemne IQ.
Podobnie obliczamy prawdopodobieństwo, tego że tą jedyną osobą z nieujemnym IQ są odpowiednio fani pozostałych siłaczy. Następne należy dodać te cztery prawdopodobieństwa.

Uwaga: oczywiście w rozwiązaniu powinniście podać to długie wyrażenie explicite.

3.	Spośród grupy fanów z poprzedniego zadania wybrano losowo jedną osobę. Okazało się, że ma ona nieujemne IQ. Jakie jest prawdopodobieństwo, że osoba ta nie jest fanem Masy?

Rozwiązanie:
Teraz naszą przestrzenią zdarzeń jest zbiór:
 ={s: s jest fanem jednego z powyższych siłaczy i s ma nieujemne IQ}
Jak łatwo widać ||=50, ponieważ tyle jest osób z nieujemnym IQ pośród rozważanej grupy fanów. Wśród tych 50 osób 29 nie jest fanami masy, tak więc odpowiedzią jest
29/50.

4.	Spośród tej samej grupy osób wybrano losowo grupę 11 osób: po czterech fanów Masy i Mięśniaka , dwóch  fanów Karczocha i jednego fana Packera.
a.	Jakie jest prawdopodobieństwo, że cała jedenastka ma nieujemny IQ?
b.	Teraz spośród tych jedenastu osób wybrano losowo jedną.. Jakie jest prawdopodobieństwo, że ta osoba ma nieujemny IQ?

Rozwiązanie a:
Grupa 11 osób w takim składzie może być wybrana na:
(150 po 4)∙(125 po 4)∙(100 po 2)∙(75 po 1)
sposobów.
Jeśli chcemy, by wszyscy mieli nieujemny IQ, musimy tworzyć tę grupę wybierając tylko z fanów o nieujemnych IQ. Możemy to zrobić na:
(21 po 4)∙(13 po 4)∙(9 po 2)∙(7 po 1)
sposobów. 
Odpowiedzią jest iloraz tych wielkości.

Rozwiązanie b:
Trzeba przypomnieć sobie wzór na ppb’stwo całkowite (pamiętacie może zadania o wadliwych produktach pochodzących z różnych fabryk). Określmy następujące zdarzenia:
X= wylosowana osoba ma nieujemny IQ
A= wylosowana osoba jest fanem Mięśniaka
B= wylosowana osoba jest fanem Masy
C= wylosowana osoba jest fanem Packera
D= wylosowana osoba jest fanem Karczocha.
Wiemy, że Pr[X]=Pr[X|A]Pr[A]+Pr[X|B]Pr[B]+Pr[X|C]Pr[C]+Pr[X|D]Pr[D].
Pozostaje określić prawdopodobieństwa występujące w tym wzorze. My ograniczymy się tylko do dwóch pierwszych. Resztę określa się analogicznie.
Jeśli wiemy, że wylosowana osoba jest fanem Mięśniaka, to ppb’stwo tego, że ma ona nieujemne IQ jest równa stosunkowi liczby fanów Mięśniaka o nieujemnym IQ do liczby wszystkich fanów Mięśniaka a więc Pr[X|A]=21/150.
Ponieważ losujemy z grupy 11 osób, z których 4 są fanami Mięśniaka, więc Pr[A]=4/11.

5.	W czasie pewnej gry gracze rzucają trzy razy kostką i przesuwają pionki o liczbę pól równą maksimum z liczby uzyskanych oczek. liczbie wyrzuconych oczek.. Niech X będzie zmienną losową równą liczbie pól, o które zostanie przesunięty pionek. 
a.	Podaj (np. w tabelce) rozkład zmiennej losowej X.

Zbiór wartości zmiennej losowej X jest równy {1,2,3,4,5,6}.
Zdarzenie: „maksimum z trzech rzutów jest równe 1” jest równoważne zdarzeniu:
„w każdym z trzech rzutów wypadła 1”. Ponieważ wyniki poszczególnych rzutów są niezależne
Pr[X=1]= (1/6)3
Pr[X=2] możemy określić jako różnicę Pr[X2]-Pr[X=1]
Prawdopodobieństwo tego, że maksimum z trzech rzutów jest nie większe od 2, jest równe temu, że w każdym rzucie wypadło 1 lub 2. Stąd Pr[X2]=(2/6)3. Tak więc 
Pr[X=2]= (2/6)3 - (1/6)3= (23-1)/63
Teraz Pr[X=3]= Pr[X3]-Pr[X2]; Pr[X=4]= Pr[X4]-Pr[X3]; itd…
Ostatecznie

k	1	2	3	4	5	6	
Pr[X=k]	1/63	(23-1)/63	(33-23)/63	(43-33)/63	(53-43)/63	(63-53)/63	

b.	Podaj dystrybuantę zmiennej losowej X,

k	1	2	3	4	5	6	
F[X]	1/63	23/63	33/63	43/63	53/63	1	

6.	Pewne doświadczenie polega na wykonaniu 10000 prób, z których każda kończy się sukcesem z prawdopodobieństwem równym 0,25. Chcesz obliczyć prawdopodobieństwo tego, że liczba sukcesów w tych próbach będzie pomiędzy 2400 a 2600. Z jakich wartości dystrybuanty rozkładu normalnego (tj. w jakich punktach) skorzystasz w swoich obliczeniach? Odpowiedź uzasadnij.

Mamy do czynienia ze schematem Bernoulliego (czyli powtarzane, niezależne próby z takim samym prawdopodobieństwem sukcesu). 
Liczba prób n=10000
Ppb’stwo sukcesu =0,25
Ppb’stwo porażki = 0,75
Niech Xn będzie zmienną losową równą liczbie sukcesów.
E[Xn] = np= 2500
Odchylenie standardowen  zmiennej Xn = pierwiastek kwadratowy z npq= pierwiastek z 1875  43.

Chcemy obliczyć Pr[2400liczba sukcesów2600] to jest równe Fn(2600)-Fn(2399), 
gdzie Fn jest dystrybuantą zmiennej Xn. Wartości Fn(k) przybliżamy wartościami dystrybuanty rozkładu normalnego w punktach (k-E[Xn])/n. Tak więc w tym przypadku są to punkty (2600- 2500)/43 oraz (2399-2500)/43.
1

7.	Dane są niezależne zmienne losowe X i Y o następujących rozkładach:

x	-2	-1	0	2	
P(X=x)	0.2	0.1	0.4	0.3	

x	0	1	
P(Y=x)	0.7	0.3	
a.	Oblicz  rozkłady zmiennych losowych X+Y oraz XY
b.	Dla zmiennej X+Y  z poprzedniego zadania oblicz:
•	wartość oczekiwaną,
•	wariancję,
c.	
 Zbiór wartości zmiennej X+Y jest równy {-2, -1, 0, 1, 2, 3}. 

Możemy dla wygody zrobić tabliczkę dodawania:
Y                 X	-2	-1	0	2	
0	-2      0,14	-1        0,07	0           0,28   	2         0,21	
1	-1      0,06	0          0,03	1           0,12	3         0,09	

Zielonym kolorem zapisałem wartości zmiennej X+Y, a czerwonym odpowiednie prawdopodobieństwa, np. 0,14 jest prawdopodobieństwem tego, że X+Y przyjmie wartość z tego powodu, że X będzie równy -2 a Y będzie równy 0  (wymnażamy w tym celu Pr[X= -2]  Pr [Y= 0]= 0,2  0,7. 

Teraz wystarczy popatrzeć kiedy X+Y przyjmuje poszczególne wartości i zsumować odpowiadające prawdopodobieństwa, np. -1 przymowane jest w dwóch przypadkach, więc musimy zsumować prawdopodobieństwa tych przypadków. Ostatecznie rozkład tej zmiennej jest następujący:
k	-2	-1	0	1	2	3	
Pr[X+Y=k]	0,14	0,13	0,31	0,12	0,21	0,09	

Wartość oczekiwana X+Y wynosi: 
(-2)∙(0,14)+(-1)∙(0,13)+0∙(0,31)+1∙(0,12)+2∙(0,21)+3∙(0,09) =0,4
Aby obliczyć wariancję korzystamy ze wzoru 
V[Z]=E[Z2]-(E[Z])2.
Wystarczy więc obliczyć E[(X+Y)2].
Zaczynamy od rozkładu zmiennej Z=(X+Y)2

k	0	1	4	9	
Pr[(X=Y)2=k]	0,31	0,25	0,35	0,09	

Stąd E[(X+Y)2]= 0∙(0,31)+1∙(0,25)+4∙0,35+9∙(0,09)=2,46

i wariancja równa się V[X+Y]=2,46-(0,4)2=2,3, o ile nie zrobiłem błędu w rachunkach.:-)

8.	Oszacuj prawdopodobieństwo, że w 400 rzutach monetą liczba orłów będzie większa 250. Skorzystaj z nierówności Czebyszewa..

Musimy przypomnieć sobie nierówność Czebyszewa:

Pr[ |X-E[X]|a] V[X]/a2 .

Niech X – zmienna losowa równa liczbie orłów w 400 rzutach.
Potrzebujemy wartości oczekiwanej i wariancji zmiennej X. Ponieważ X jest zmienną rozkładu dwumianowego (albo jak ktoś woli Bernoulliego), więc znamy wzory na te wielkości:
E[X]= n∙p=400∙(1/2)=200
V[X]= n∙p∙q= 400 ∙(1/2) ∙(1/2)=100

Chcemy policzyć Pr[X>250], co równe jest Pr[X-200>50]. We nierówności Czebyszewa mamy jednak wartość bezwzględną i słabą nierówność. Musimy X-200>51 zastąpić przez X-20051.
Jeśli jednak obliczymy Pr[ |X-200|51], to policzymy trochę za dużo. Jest to bowiem prawdopodobieństwo tego, że liczba orłów będzie większa od 250 plus prawdopodobieństwo tego, że będzie ona mniejsza od 150. Ale to drugie oznacza, że wówczas liczba reszek będzie większa od 250. Ponieważ moneta jest symetryczna, więc prawdopodobieństwo tego, że liczba orłów będzie większa od 250 jest równe prawdopodobieństwu tego, że liczba reszek będzie większa od  250. 

Czyli 
Pr[X>250] = ½ ∙ Pr[ |X-200|51]

Z nierówności  Czebyszewa Pr[ |X-200|51]100/5121/25.
Stąd mamy oszacowanie Pr[X>250]1/50.