Переупаковка энтропии

Question

Я перебираю концептуальную идею для машины (как в машине Тьюринга) и Мне интересно, была ли проделана какая-либо работа по этой или смежным темам.

Идея - это машина, которая принимает энтропийный поток и выдает случайные символы в любом диапазоне без потери энтропии.

Пожалуй, это далеко не точное описание, поэтому приведу пример: скажем, у меня есть генератор случайных символов в диапазоне от 1 до n, и я хочу иметь возможность запросить символы в любом заданном диапазоне, сначала от 1 до 12, а затем от 1 до 1234. (Чтобы это было практически осуществимо, я рассмотрю только детерминированные машины, где при одинаковом входном потоке и запросах он всегда будет выдавать один и тот же выход.) Одно из необходимых ограничений заключается в том, что выходные данные содержат как минимум столько же энтропии, что и входные. Однако, ограничение, которое меня больше всего интересует, заключается в том, что машина считывает столько энтропии, сколько выплевывает.

например. если запросить токены в диапазоне от 1 до S1, S2, S3, ... Sm, он будет потреблять только ceiling(sum(i = 1 to m, log(Si))/log(n)) входных токенов.

Этот вопрос задает вопрос о том, как выполнить это преобразование, удовлетворяя при этом первому ограничению, но очень плохо сказывается на втором.

Answer 1

Мой текущий проход на этом:

Если добавить следующее ограничение: вы заранее знаете, какова последовательность диапазонов {S1, S2, S3, ..., Sn}, чем сработает базовый перевод с непостоянной базой:

1. Найти Sp = S1 * S2 * S3 * ... * Sn
2. Извлечение m=cealing(log(Sp)/log(n)) членов из ввода {R1, R2, R3, ..., Rm}
3. Найти X = R1 + R2*n + R3*n^2 + ... + Rm*n^(m-1)
4. Реформа X как O1 + S1*O2 + S1*S2*O3 + ... Sn*On + x, где 1 <= Oi <= Si

Это может быть преобразовано в решение, которое работает для одного значения за один раз, нажав x обратно во входной поток. Однако я не могу убедить себя, что даже известная форма диапазона выходных сигналов является звуком, так что ...

Answer 2

Хорошо, я все еще не уверен, что следую тому, что вы хотите. Похоже, вы хотите функцию

f : I & rarr; O

где входные данные представляют собой строго случайную (равномерное распределение и т. Д.) Последовательность символов в алфавите I = {1 .. n }. (Таким образом, серия случайных натуральных чисел ≤ n .) Выходными данными является другая последовательность на O = {1 .. m }, и вы хотите, чтобы эта последовательность имела столько энтропии, сколько входы.

Хорошо, если я правильно понял, прежде всего, если m , вы не можете. Если m , то lg m n , поэтому энтропия набора выходных символов меньше.

Если m ≥ n , вы можете сделать это тривиально, просто выбрав i ^th элемента {1 .. м }. Энтропия будет одинаковой, так как количество возможных выходных символов одинаково. Они не будут «случайными» в том смысле, что они будут равномерно распределены по всему набору {1 .. m }, хотя, потому что обязательно (принцип голубя) некоторые символы не будут выбраны в все.

Если, с другой стороны, вы будете удовлетворены случайной последовательностью {1 .. m }, то вы можете сделать это, выбрав подходящий генератор псевдослучайных чисел, используя ваш вход из случайный источник как семя.