Niezależne wykonania algorytmu [twierdzenie de Moivre'a-Laplace'a?]

[dawid98103]

Mam do zrealizowania zadanie z następującą treścią:

Załóżmy, że prawdopodobieństwo zwrócenia rozwiązania optymalnego (o minimalnym koszcie) przez pewien algorytm wynosi 0.05. Algorytm ten został wykonany 100krotnie, 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?.

Zastanawiam się z jakiej strony mógłbym je ugryźć. Słyszałem o twierdzeniu de Moivre'a-Laplace'a które mogłoby znaleźć tutaj zastosowanie. Pytanie brzmi w jaki sposób mógłbym zastosować tutaj wzór żeby otrzymać poprawny rezultat?

[Dasio11]

Jeśli wolno założyć, że zdarzenia polegające na zwróceniu optymalnego wyniku w \(\displaystyle{ i}\)-tym przebiegu są niezależne dla \(\displaystyle{ i = 1, 2, \ldots, 100}\), to odpowiedzią jest \(\displaystyle{ 1-(1-0.05)^{100}}\) - aby bowiem ostatecznie uzyskany wynik był nieoptymalny, wszystkie sto przebiegów musi zwrócić nieoptymalne wyniki.