Генерация последовательности случайных чисел с определенной энтропией - PullRequest
Новая
       58

Генерация последовательности случайных чисел с определенной энтропией

3 голосов
/ 12 марта 2019

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

Например, если бы я передавал сгенерированные данные в gzip, он мог бы сжать их.И на самом деле, это было бы точное приложение для кода, тестирующее компрессоры данных.

Я программирую это на C ++, и первая мысль, которая пришла мне в голову, - инициализировать группу PRDGs std :: mt19937.со случайным семенем и выберите один случайным образом и сделайте случайный образец длины с ним.Std :: mt19937 сбрасывается каждый раз с одним и тем же начальным числом, так что он всегда генерирует один и тот же шаблон: 

#include <iostream>
#include <random>
#include <vector>

int main() {

    std::random_device rd;
    std::vector<std::mt19937> rngs;
    std::vector<int> seeds;

    std::uniform_int_distribution<int> patternrg(0,31);
    std::uniform_int_distribution<int> lenghtrg(1,64);
    std::uniform_int_distribution<int> valuerg(0,255);

    for(int i = 0; i < 32; ++i) {
        seeds.push_back(rd());
        rngs.emplace_back(seeds.back());
    }

    for(;;) {
        // Choose generator and pattern lenght randomly.
        auto gen = patternrg(rd);
        auto len = lenghtrg(rd);
        rngs[gen].seed(seeds[gen]);
        for(int i = 0; i < len; ++i) {
            std::cout << valuerg( rngs[gen] )<<"\n";
        }
    }
}

Выше код отвечает первому требованию генерации сжимаемой случайности, но второе сложнее: как контролировать уровеньэнтропия / случайность?

Ответы [ 2 ]

1 голос
/ 14 марта 2019

Позвольте мне написать несколько предложений, которые вы могли бы найти полезными.Предположим, мы хотим сэмплировать один бит с заданной энтропией.Таким образом, это либо 0, либо 1, и требуемая энтропия равна e.

H (10 | p) = -p log 2 (p) - (1 - p) log 2 (1 - p), где p - вероятность получить 1. Простой тест - в случае p = 1/2 можно получить энтропию 1 - максимальную энтропию.Таким образом, вы выбираете e равным некоторому значению ниже 1, решаете уравнение

-p log 2 (p) - (1 - p) log 2 (1- p) = e

и получить обратно p, и тогда вы можете начать выборку, используя распределение Бернулли .Простая демонстрация здесь .А в C ++ можно использовать стандартную библиотечную процедуру .

Хорошо, предположим, что вы хотите сэмплировать один байт с заданной энтропией.Он имеет 256 значений и энтропию

H (байт | \ vec {p}) = -Sum (1 ... 256) p i log 2 (p i ).

Опять же, если все комбинации равновероятны (p i = 1/256), вы получите -256/256 log 2 (1/256) = 8, что является максимальной энтропией.Если вы теперь исправите свою энтропию (скажем, я хочу, чтобы она равнялась 7), то для p i было бы бесконечное число решений, единой уникальной реализации данной энтропии не было бы.

Вы могли бы немного упростить задачу - давайте снова рассмотрим случай с одним параметром, где вероятность найти 1 равна p, а вероятность найти 0 равна (1-p).Таким образом, из 256 результатов мы получили 9 из них - 00000000, 00000001, 00000011, 00000111, 00001111, 00011111, 00111111, 01111111, 11111111. Для каждого из этих случаев мы могли бы написать вероятность, вычислить энтропию, присвоить ее как угодно ирешите обратно, чтобы найти p.

Выборка будет относительно простой - первым шагом будет выборка из 9 комбинаций с помощью дискретного распределения , а вторым шагом будут биты тасования внутри байтаиспользуя Fisher-Yates shuffle .

Тот же подход можно использовать, скажем, для 32-битных или 64-битных - у вас есть 33 или 65 случаев, построить энтропию, назначить на что угодно, найти p, сэмплируйте один из них и затем перетасуйте биты в выборочном значении.

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

ОБНОВЛЕНИЕ

Имейте в виду еще одно своеобразное свойство фиксирующей энтропии.Даже для простого случая одиночного бита, если вы попытаетесь решить

-p log 2 (p) - (1 - p) log 2 (1 -p) = e

для данного e, вы получите два ответа, и легко понять, почему - уравнение симметрично относительно p и 1-p (или замену 0 на 1 и1 с 0).Другими словами, для энтропии не имеет значения, если вы передаете информацию, используя в основном нули или в основном единицы.Это не относится к таким вещам, как естественный текст.

0 голосов
/ 14 марта 2019

Коэффициент энтропии (в терминах выходных значений байт , а не читаемых человеком символов) вашей конструкции имеет несколько сложностей, но (для ряда генераторов гораздо меньшечем 256) это хорошее приближение, чтобы сказать, что это энтропия каждого выбора (5 бит для выбора последовательности плюс 6 для ее длины), деленная на среднюю длину подпоследовательностей (65/2), или 0,338 бита из возможных 8 на байт.(Это значительно ниже, чем обычный текст на английском языке.) Вы можете увеличить коэффициент энтропии, задав больше последовательностей или , уменьшив типичную длину подпоследовательности, взятой из каждой.(Если подпоследовательность часто составляет всего один символ или число последовательностей в сотнях, столкновения обязательно уменьшат скорость энтропии ниже этой оценки и ограничат ее до 8 битов на байт.)

Другой легко настраиваемый класс последовательности включаетполучение одного байта из [0, n ] с вероятностью p <1 / (<em> n + 1) для 0 и другихс равной вероятностью.Это дает коэффициент энтропии H = (1- p ) ln ( n / (1- p )) - p ln p , который лежит на [ln n , ln ( n + 1)), поэтому любой желаемый тариф можетвыберите n , а затем p соответственно.(Не забудьте использовать lg вместо ln, если вы хотите бит энтропии.)

...