Wynik o najmniejszym koszcie (100 identycznych prób)

Definicja klasyczna. Prawdopodobieństwo warunkowe i całkowite. Zmienne losowe i ich parametry. Niezależność. Prawa wielkich liczb oraz centralne twierdzenia graniczne i ich zastosowania.
ktosztlumu
Użytkownik
Użytkownik
Posty: 20
Rejestracja: 22 paź 2011, o 06:26
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 2 razy

Wynik o najmniejszym koszcie (100 identycznych prób)

Post autor: ktosztlumu »

Załóżmy, że prawdopodobieństwo zwrócenia rozwiązania optymalnego ( o minimalnym koszcie ) przez pewien algorytm wynosi 0.05. Algorytm ten został wykonany 100 krotnie, a następnie jako wynik podano rozwiązanie o najmniejszym koszcie spośród 100 uzyskanych rozwiązań.


Jakie jest prawdopodobieństwo, że tak uzyskany wynik jest optymalny?


No właśnie jak ugryźć to zadanie ? Myślałem nad tym, aby obliczyć prawdopodobieństwo tego, że podczas losowania nie zwrócony zostanie wynik optymalny ani razu, czyli zdarzenie przeciwne. Jednak ani schemat Bernouliego ani też rozkład Poissona nie skutkują z powodu bardzo nie wygodnych liczb.
Lider Artur
Użytkownik
Użytkownik
Posty: 692
Rejestracja: 19 cze 2011, o 23:29
Płeć: Mężczyzna
Lokalizacja: Warszawa
Pomógł: 107 razy

Wynik o najmniejszym koszcie (100 identycznych prób)

Post autor: Lider Artur »

Wprowadźmy zmienną losową \(\displaystyle{ X}\).
\(\displaystyle{ X=0}\) - algorytm podał rozwiązanie nieoptymalne, \(\displaystyle{ P(X=0)=0,95}\)
\(\displaystyle{ X=1}\) - algorytm podał rozwiązanie optymalne, \(\displaystyle{ P(X=1)=0,05}\)
Zatem nasza zmienna losowa \(\displaystyle{ X}\) ma rozkład dyskretny, dwupunktowy
Chcemy obliczyć: \(\displaystyle{ P( \sum_{i=1}^{100}X_i >0 )}\).
Wystarczy skorzystać z centralnego twierdzenia granicznego.
ktosztlumu
Użytkownik
Użytkownik
Posty: 20
Rejestracja: 22 paź 2011, o 06:26
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 2 razy

Wynik o najmniejszym koszcie (100 identycznych prób)

Post autor: ktosztlumu »

Jeszcze jedno pytanie czy można w tym zadania użyć twierdzenia de Moivre'a-Laplace'a ?

Ponieważ jeśli liczę zdarzenie przeciwne czyli, że algorytm ani razu nie zwróci optymalnego wyniku to w dystrybuancie mam liczbę ujemną

Z góry dziękuję za odpowiedź
ODPOWIEDZ