Изменения

=== Доказательство корректности ===

Докажем по индукции, что вероятность получить любой перфикс <tex> P </tex> равна <tex dpi = "120"> S(P)\over{C(n)} </tex>, где <tex> C(n) </tex> {{---}} число различных комбинаторных объектов данного типа длины <tex> n </tex>, а <tex> S(P) </tex> {{---}} число различных комбинаторных обьектов длины <tex> n </tex> с таким префиксом.

*Пусть вероятность получить префикс <tex> P </tex> длины <tex> l </tex> равна <tex> S(P)\over{C(n)} </tex>

*Вероятность получить из <tex> P </tex> любой префикс <tex> P' </tex> длины <tex> l+1 </tex> равна <tex> S(P')\over{S(P)} </tex> , следовательно вероятность получить префикс <tex> P' </tex> равна <tex> S(P)\over{C(n)} </tex><tex>\cdot</tex><tex> S(P')\over{S(P)} </tex> что равно <tex> S(P')\over{C(n)} </tex>