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.
Wynik o najmniejszym koszcie (100 identycznych prób)
-
- Użytkownik
- Posty: 20
- Rejestracja: 22 paź 2011, o 06:26
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 2 razy
-
- 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)
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.
\(\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.
-
- 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)
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ź
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ź