Сложность и асимптотически оптимальные алгоритмы моделирования абсолютно непрерывных распределений

В работе Кнута и Яо (Кибернет. сб., 1983, вып. 19) поставлен вопрос о том, какая “промежуточная” модель ПР-алгоритмов (преобразующих равнораспределенные случайные биты в случайные величины с произвольными распределениями) наиболее соответствует практически важным распределениям. Целью настоящей работы является изучение одной из таких моделей для абсолютно непрерывных распределений, которая, по-видимому, включает в себя как конечные, так и общие ПР-алгоритмы.