7.6. Алгоритм рандомизированной СИФ

Прежде чем завершить рассмотрение темы отображения символьного пространства S на аттрактор, обратим внимание на то, почему же собственно работает алгоритм РСИФ рандомизированной системы итерированных функций. Пусть СИФ задана сжатиями , причем Е — аттрактор, — коэффициенты сжатия, Алгоритм 4.2.2, который реализует РСИФ, известен также как игра «Хаос» (упр. 1 из п. 4.1) и заключается в выборе произвольной начальной точки и итерировании

причем каждый индекс выбирается случайным образом, так что вероятность того, что равна . Естественно, полагаем, что

Теорема 7.6.16. Пусть и положим . Тогда, почти наверное, существует такая точка получаемая алгоритмом РСИФ, что

Доказательство. Так как (см. (7.5)) является отображением на, то существует по меньшей мере одна точка

для которой . Выберем такое, что если то

Пусть — аттрактор СИФ с множеством сгущения (см. доказательство теоремы 4.3.3). Рассмотрим множества

Эти множества вложены друг в друга в порядке убывания, а их диаметры удовлетворяют неравенству

Пусть — достаточно большая величина. Тогда

Теперь зафисируем . Рассмотрим достаточно длинную последовательность итераций РСИФ, скажем, длины L, такую, что индексы

соответствуют индексам

Тогда

и

Появление этих индексов (почти наверное) имеет место, так как вероятность этого события равна положительному числу: