Статистическая вероятность N смежных истинных битов в последовательности битов? - PullRequest
Новая
       74

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

1 голос
/ 30 января 2020

Давайте предположим, что у меня есть N-битный поток сгенерированных битов. (В моем случае 64 килобит.)

Какова вероятность нахождения последовательности из X «всех истинных» битов, содержащихся в потоке из N битов. Где X = (от 2 до 16) и N = (от 16 до 1000000), а X

Например: если N = 16 и X = 5, какова вероятность нахождения 11111 в пределах 16 -битное число.

Как этот псевдокод: 

int N = 1<<16; // (64KB)
int X = 5;
int Count = 0;
for (int i = 0; i < N; i++) {
    int ThisCount = ContiguousBitsDiscovered(i, X);
    Count += ThisCount;
}
return Count;

То есть, если мы выполнили целое число в al oop от 0 до 64K-1 ... сколько раз в этих числах появилось бы 11111.

Дополнительное правило: 1111110000000000 не считается, потому что в нем 6 истинных значений подряд, а не 5. Итак: 

1111110000000000 = 0x // because its 6 contiguous true bits, not 5.
1111100000000000 = 1x
0111110000000000 = 1x
0011111000000000 = 1x
1111101111100000 = 2x

Я пытаюсь выполнить некоторую работу, включающую физическую генерацию случайных чисел и обнаружение «насколько случайны» числа. Вот для чего это.

...

Это было бы легко решить, если бы N было меньше 32 или около того, я мог бы просто "запустить al oop" от 0 до 4 ГБ. , затем посчитайте, сколько смежных битов было обнаружено после завершения l oop. Тогда я мог бы сохранить число и использовать его позже.

Учитывая, что значение X варьируется от 2 до 16, мне буквально нужно было бы хранить только 15 чисел, каждое из которых меньше 32 бит! (если N = 32)!

НО в моем случае N = 65,536. Поэтому мне нужно запустить al oop, для 2 ^ 65 536 итераций. В принципе невозможно:)

Нет способа "экспериментально рассчитать значения для данного X, если N = 65 536". В общем, мне нужна математика.

Ответы [ 2 ]

2 голосов
/ 30 января 2020

Fix X и N, явно с X < N. У вас есть 2^N возможных значений комбинаций 0 и 1 в вашем номере бита, и у вас есть N-X +1 возможных последовательностей 1*X (в этой части я только ищу 1's вместе), содержащихся в вашем номере бита , Рассмотрим, например, N = 5 и X = 2, это возможный допустимый битовый номер 01011, поэтому для фиксированных двух последних символов (последних двух 1's) у вас есть 2^2 возможных комбинаций для этой последовательности 1*X. Тогда у вас есть два случая:

Пограничный случай : Ваш 1*X находится на границе, тогда у вас есть (2^(N -X -1))*2 возможных комбинаций

Внутренний случай : у вас есть (2^(N -X -2))*(N-X-1) возможных комбинаций.

Итак, вероятность составляет (border + inner )/2^N

Примеры:

  • 1) N = 3, X =2 , тогда вероятность составляет 2/2^3

  • 2) N = 4, X = 2, тогда вероятность составляет 5/16

1 голос
/ 30 января 2020

Немного грубой силы, но я бы сделал что-то подобное, чтобы не попасться в статистическую теорию:

  • Умножить вероятности (1 бит = 0,5, 2 бита = 0,5 * 0,5 и т. Д. c) во время цикла
  • Следите за каждым X и, когда у вас есть произведение битов X, переверните его и продолжайте
  • Начните с небольшого примера (N = 5, X = 1 - 5) чтобы убедиться в правильности краевых наблюдений, сравните с методом грубой силы.

Это, вероятно, можно выразить как что-то вроде Sum (Sum 0.5 ^ x (x = 1 -> 16) (для n = 1 - 65536), но необходимо учитывать крайние случаи (т. е. 7 бит не подходят, вероятность сброса), что вызывает у меня небольшую головную боль.: -)

...