Wartość oczekiwana
Mariusz Marszałkowski
Rzucamy N-ścienną kostką dopóki nie wypadnie jedna
ze ścianek, ile razy będziemy przeciętnie rzucać?
Sumujemy po i od 1 do nieskończoności
(N-1)^(i-1) / N^i * i
co (o ile pamiętam) daje N
Zadanie można skomplikować. Do każdej ścianki przypisujemy
prawdopodobieństwo wylosowania pw(x) i prawdopodobieństwo
zakończenia rzucania pz(x). W poprzednim zadaniu prawdopodobieństwo
zakończenia wynosiło dla wszystkich ścianek poza jedną 0%, a dla
owej jednej 100%.
W wyniku takiego losowania powstaje drzewo. Po pierwszym rzucie
mamy N gałęzi. Prawdopodobieństwo pójścia gałęzią x wynosi pw(x).
Prawdopodobieństwo dalszego losowania po gałęzi x wynosi 1-pz(z).
Jaki będzie wzór na przeciętną ilość rzutów taką kostką?
Z góry dziękuję za pomoc
--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/
Łukasz Kalbarczyk
> Witam
>
> Rzucamy N-ścienną kostką dopóki nie wypadnie jedna
> ze ścianek, ile razy będziemy przeciętnie rzucać?
> Sumujemy po i od 1 do nieskończoności
>
> (N-1)^(i-1) / N^i * i
>
> co (o ile pamiętam) daje N
>
> Zadanie można skomplikować. Do każdej ścianki przypisujemy
> prawdopodobieństwo wylosowania pw(x) i prawdopodobieństwo
> zakończenia rzucania pz(x). W poprzednim zadaniu prawdopodobieństwo
> zakończenia wynosiło dla wszystkich ścianek poza jedną 0%, a dla
> owej jednej 100%.
>
> W wyniku takiego losowania powstaje drzewo. Po pierwszym rzucie
> mamy N gałęzi. Prawdopodobieństwo pójścia gałęzią x wynosi pw(x).
> Prawdopodobieństwo dalszego losowania po gałęzi x wynosi 1-pz(z).
> Jaki będzie wzór na przeciętną ilość rzutów taką kostką?
Jakieś funkcje tworzące i/lub Łańcuchy Markowa mogą pomóc.
--
ŁK (2009-04-24 00:29:52)
Maciek
Użytkownik "Mariusz Marszałkowski" <brodacz1...@gazeta.pl>
napisał w wiadomości news:gsppcj$sh9$1...@inews.gazeta.pl...
> Witam
>
> Rzucamy N-ścienną kostką dopóki nie wypadnie jedna
> ze ścianek, ile razy będziemy przeciętnie rzucać?
> Sumujemy po i od 1 do nieskończoności
>
> (N-1)^(i-1) / N^i * i
Czyli (1 - 1/N)^(i-1) * 1/N * i, prawda?
>
> co (o ile pamiętam) daje N
>
> Zadanie można skomplikować. Do każdej ścianki przypisujemy
> prawdopodobieństwo wylosowania pw(x) i prawdopodobieństwo
> zakończenia rzucania pz(x). W poprzednim zadaniu prawdopodobieństwo
> zakończenia wynosiło dla wszystkich ścianek poza jedną 0%, a dla
> owej jednej 100%.
>
> W wyniku takiego losowania powstaje drzewo. Po pierwszym rzucie
> mamy N gałęzi. Prawdopodobieństwo pójścia gałęzią x wynosi pw(x).
> Prawdopodobieństwo dalszego losowania po gałęzi x wynosi 1-pz(z).
> Jaki będzie wzór na przeciętną ilość rzutów taką kostką?
Prawdop. zakończenia w jednym rzucie będzie teraz:
p = \sum_{x \in zbiórścian} pw(x) * pz(x)
zamiast poprzedniego 1/N,
więc prawobodobieństwo zakończenia w i-tym rzucie:
(1 - p)^(i-1) * p
zamiast
(1 - 1/N)^(i-1) * 1/N
i oczekiwana długość serii wyraża się sumą
\sum_{i=1}^\infty (1 - p)^(i-1) * p * i
Dalej funkcją tworzącą, jak podpowiedział Łukasz.
Maciek
Maciek
Użytkownik "Maciek" <mac...@elkomtech.com.pl.nospam>
napisał w wiadomości news:gsrmn0$pgc$1...@opal.futuro.pl...
>
> Użytkownik "Mariusz Marszałkowski" <brodacz1...@gazeta.pl>
> napisał w wiadomości news:gsppcj$sh9$1...@inews.gazeta.pl...
>> Witam
>>
>> Rzucamy N-ścienną kostką dopóki nie wypadnie jedna
>> ze ścianek, ile razy będziemy przeciętnie rzucać?
>> (o ile pamiętam) daje N
>>
>> Zadanie można skomplikować. Do każdej ścianki przypisujemy
>> prawdopodobieństwo wylosowania pw(x) i prawdopodobieństwo
>> zakończenia rzucania pz(x).
>> Jaki będzie wzór na przeciętną ilość rzutów taką kostką?
>
> Prawdop. zakończenia w jednym rzucie będzie teraz:
>
> p = \sum_{x \in zbiórścian} pw(x) * pz(x)
>
> zamiast poprzedniego 1/N,
> więc prawobodobieństwo zakończenia w i-tym rzucie:
>
> (1 - p)^(i-1) * p
>
>
> \sum_{i=1}^\infty (1 - p)^(i-1) * p * i
... i (jeśli nie rąbnąłem się w rachunkach) wychodzi 1/p,
co jest zgodne z Twoim wynikiem dla oryginalnego zadania
(wynik N dla p = 1/N).
Maciek
Mariusz Marszałkowski
> > \sum_{i=1}^\infty (1 - p)^(i-1) * p * i
>
> co jest zgodne z Twoim wynikiem dla oryginalnego zadania
> (wynik N dla p = 1/N).
>
>
> Maciek
>
Dziękuję, nie wiem dlaczego nie wpadłem sam na to żeby wymnożyć i zsumować
prawdopodobieństwa a tym samym zadanie sprowadzić do pierwszej prostej
postaci :) Napisałem w C symulator i kilka wyników teoretycznych zgadzało
się z średnią symulacji, więc chyba jest dobrze.
Sposobu rozwiązania tego szeregu już nie pamiętam, ale pamiętam z wykładów
że rozwiązanie właśnie wynosi N dla p = 1/N :)
Zdrowia
M
> Maciek <mac...@elkomtech.com.pl.nospam> napisał(a):
>>> \sum_{i=1}^\infty (1 - p)^(i-1) * p * i
>> .... i (jeśli nie rąbnąłem się w rachunkach) wychodzi 1/p,
>> co jest zgodne z Twoim wynikiem dla oryginalnego zadania
>> (wynik N dla p = 1/N).
>>
>>
>> Maciek
>>
>
> Dziękuję, nie wiem dlaczego nie wpadłem sam na to żeby wymnożyć i zsumować
> prawdopodobieństwa a tym samym zadanie sprowadzić do pierwszej prostej
> postaci :) Napisałem w C symulator i kilka wyników teoretycznych zgadzało
> się z średnią symulacji, więc chyba jest dobrze.
>
> Sposobu rozwiązania tego szeregu już nie pamiętam, ale pamiętam z wykładów
> że rozwiązanie właśnie wynosi N dla p = 1/N :)
Sumujesz dwa razy, tzn. masz ciągi geometryczne, których sumy tworzą
ciąg geometryczny.
S= x+ 2x^2 +3x^3 + ...=
= x + x^2 + x^3 + ...
+ x^2 + x^3 + ...
+ x^3 + ...
...
M.
Maciek
U�ytkownik "Mariusz Marsza�kowski" <brodacz1...@gazeta.pl>
napisa� w wiadomo�ci news:gssu08$jn8$1...@inews.gazeta.pl...
> Maciek <mac...@elkomtech.com.pl.nospam> napisaďż˝(a):
>> >
>> > \sum_{i=1}^\infty (1 - p)^(i-1) * p * i
>>
>>
>
> Dzi�kuj�, (.......)
>
> Sposobu rozwi�zania tego szeregu ju� nie pami�tam, ale pami�tam
> z wyk�ad�w �e rozwi�zanie w�a�nie wynosi N dla p = 1/N :)
Oznaczmy szukan� sum� przez S. Upraszczamy zapis oznaczaj�c
q = (1-p):
S = \sum_{i=1)^\inf i * p * q^(i-1)
Wy��czamy z sumy pierwszy sk�adnik:
S = p * 1 * q^0 + \sum_{i=2)^\inf i * p * q^(i-1)
S - p = \sum_{i=2)^\inf i * p * q^(i-1)
Wy��czamy z sumy szereg geometryczny, co zmniejsza
o jedno�� czynnik "i" w ka�dym wyrazie:
S - p = \sum_{i=2)^\inf [p*q^(i-1) + (i-1)*p*q^(i-1)]
S - p = \sum_{i=2)^\inf p*q^(i-1) + \sum (i-1)*p*q^(i-1)
S - p = pq/(1 - q) + \sum_{i=2)^\inf (i-1)*p*q^(i-1)
Przesuwamy numeracj� sumowanych wyraz�w:
S - p = pq/(1 - q) + \sum_{i=1)^\inf i * p * q^i
W pierwszym sk�adniku po prawej stronie podstawiamy 1-q=p,
za� w drugim wy��czamy z sumy wsp�lny czynnik "q":
S - p = pq/p + q * \sum_{i=1)^\inf i * p * q^(i-1)
S - p = q + q * S
(1 - q) * S = p + q
p * S = 1
S = 1 / p
To wszystko oczywi�cie pod warunkiem, �e S w og�le istnieje!
Pisz�c "oznaczmy szukan� sum� przez S" zak�adam to, bo tylko
z takim za�o�eniem powy�sze przekszta�cenia maj� sens. Jednak
rachunek ten NIE DOWODZI ISTNIENIA sumy - zbie�no�� szeregu S
trzeba wykazaďż˝ innymi metodami...
Maciek
M
> Pisz�c "oznaczmy szukan� sum� przez S" zak�adam to, bo tylko
> z takim za�o�eniem powy�sze przekszta�cenia maj� sens. Jednak
> rachunek ten NIE DOWODZI ISTNIENIA sumy - zbie�no�� szeregu S
> trzeba wykazaďż˝ innymi metodami...
No to podw�jna suma (jak pisa�em wy�ej)
S = \sum_{i=1}^\infty \sum_{j=i}^\infty x^j
warunek zbie�no�ci jest wtedy prosty
M.
Maciek
U�ytkownik "M" <M-no...@wp.pl> napisa�
w wiadomo�ci news:gt6g5d$61n$1...@node1.news.atman.pl...
Tak jest.
Pisa�em swoj� odpowied� "na raty", do tego troch� z dala
od sieci, i wys�a�em gdy by�a gotowa, nie patrz�c czy co�
nowego si� w tym w�tku pojawi�o.
Niemniej chyba dobrze si� sta�o - do tej samej odpowiedzi,
kt�ra wprost wynika z Twojego sposobu, doszed�em inn� drog�
(a �e okr�n�? ma�e zmartwienie), wi�c mamy wzajemne
sprawdzenie. :-)
Maciek