Złożoność algorytmu z prawdopodobieństwem

Question

Cześć.
Dzięki za naprowadzenie z poprzednim problemem, jednakże znów muszę prosić o pomoc w innym zadaniu. Nie proszę o rozwiązanie, a raczej o jakieś wskazówki. Potrzebuję pomocy z obliczeniem złożoności algorytmu z zmienną losową. Doszedłem do tego, jak można zobrazować problem za pomocą grafu lecz nic poza tym. W wierzchołkach znajdują się wartości, natomiast krawędzie symbolizują prawdopodobieństwo z jakim może zostać wybrany następny wierzchołek:

Problem pojawia się, ponieważ istnieje prawdopodobieństwo, że algorytm "cofnie" się o 1, gdyby tego nie było, obliczenie złożoności obliczeniowej tego algorytmu byłoby w miarę proste. Nie pytam też o odpowiedź, a raczej o jakieś wskazówki jak do niej dojść.

 

Edit: myślałem też, zeby przedstawić to jako przeszukiwanie stringa i znajdowanie podciągu w którym będzie o n więcej 1 niż 0. Tylko to też niezbyt mi pomaga. 

Comments

https://en.wikipedia.org/wiki/Probabilistic_Turing_machine

https://en.wikipedia.org/wiki/Randomized_algorithm#Computational_complexity

W mojej ocenie problem podchodzi pod klasę Probabilistic Polynomial. Co daje średni czas wielomianowy od n. 

---

Mógłbym prosić o jeszcze jakieś Wskazówki, nie jestem wstanie tylko z tym rozwiązać problem (ze względu na zmianę wartości losowej).

Answer 1

To jest klasyczny przykład na łańcuch markowa, w szczególności popatrz na twierdzenia 8.11 i 8.12. Obliczenie wartości oczekiwanej liczby kroków wykonanych podczas przejścia z stanu i do stanu n da się sprowadzić do poniższego układu równań:

1. x(n) =0
2. x(1) = x(2) + 1
3. x(i) = 0.5(x(i-1) + x(i+1)) + 1 dla i  {2, 3, .., n-1}

 

Answer 2

W przypadku algorytmów z rachunkiem prawdopodobieństwa liczy się wartość oczekiwaną zmiennej losowej.

Zobacz na dowód złożoności oczekiwanej QuickSorta w Cormenie (co prawda tam nie ma explicit zmiennej losowej ale problem lustrzany)

Comments

No właśnie jestem wstanie sobie poradzić z Algorytmami z prawdopodobieństwem, gdy nie zmienia się zmienna losowa. Mógłbym prosić o jeszcze jakieś wskazówki?