74
правки
Изменения
Нет описания правки
== Доказательство корректности ==
{{Лемма
|statement=Вероятность получить в процессе работы алгоритма некоторый префикс <tex> P </tex> равна <tex> \dfrac{S(P)\over}{C(n)} </tex>, где <tex> C(n) </tex> {{---}} число различных комбинаторных объектов данного типа длины <tex> n </tex>, а <tex> S(P) </tex> {{---}} число различных комбинаторных обьектов длины <tex> n </tex> с таким префиксом.
|proof=Докажем по [[Математическая индукция|индукции]]:
'''База:''' Заметим, что любой комбинаторный объект имеет пустой префикс (<tex> \varnothing </tex>), следовательно <tex> S(\varnothing)=C(n) </tex>.
Вероятность получить некоторый префикс <tex> P </tex> длины <tex> 1 </tex> равна <tex> \dfrac{S(P)\over}{S(\varnothing)} </tex>, что равно <tex> \dfrac{S(P)\over}{C(n)} </tex> .
'''Переход:''' Пусть вероятность получить префикс <tex> P </tex> длины <tex> l </tex> равна <tex> \dfrac{S(P)\over}{C(n)} </tex>. Вероятность получить из <tex> P </tex> некоторый префикс <tex> P' </tex> длины <tex> l+1 </tex> равна <tex> \dfrac{S(P')\over}{S(P)} </tex> , следовательно вероятность получить префикс <tex> P' </tex> равна <tex> \dfrac{S(P)\over}{C(n)} </tex><tex>\cdot</tex><tex> \dfrac{S(P')\over}{S(P)} </tex> что равно <tex> \dfrac{S(P')\over}{C(n)} </tex>.
Следовательно предположение индукции верно для всех возможных префиксов любой длины.
{{Утверждение
|statement=Результатом работы данного алгоритма является случайный комбинаторный объект размера <tex> n </tex>, причем вероятность получения одинакова для каждого результата.
|proof=Заметим, что результатом работы данного алгоритма является любой из возможных префиксов размера <tex> n </tex>. Любой такой префикс является комбинаторным объектом размера <tex> n </tex> и наоборот, следовательно число объектов с таким префиксом равно <tex> 1 </tex>. Из чего по доказанной лемме следует, что вероятность получения одинакова для всех различных результатов и равна <tex> \dfrac{1\over}{C(n)} </tex>.
}}
