Генерация случайного двоичного числа с переменной пропорцией «1» битов

Question

Мне нужна функция для генерации случайных целых чисел. (предположим тип Java long на данный момент, но позже он будет расширен до BigInteger или BitSet.)

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

Если P = 0,5, тогда мы можем просто использовать стандартный генератор случайных чисел. Некоторые другие значения P также легко реализуются. Вот неполный пример:

Random random = new Random();

// ...

long nextLong(float p) {
    if      (p == 0.0f)   return 0L;
    else if (p == 1.0f)   return -1L;
    else if (p == 0.5f)   return random.nextLong();
    else if (p == 0.25f)  return nextLong(0.5f) & nextLong(0.5f);
    else if (p == 0.75f)  return nextLong(0.5f) | nextLong(0.5f);
    else if (p == 0.375f) return nextLong(0.5f) & nextLong(0.75f); // etc
    else {
      // What goes here??
      String message = String.format("P=%f not implemented yet!", p);
      throw new IllegalArgumentException(message);
    }
}

Есть ли способ обобщить это для любого значения P от 0,0 до 1,0?

Answer 1

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

Определите x и y - биты с вероятностью, равной 1 из X = p (x = 1), Y = p (y = 1) соответственно. Тогда у нас есть это

 p( x & y = 1) = X Y
 p( x | y = 1) = 1 - (1-X) (1-Y)
 p( x ^ y = 1) = X (1 - Y) + Y (1 - X)

Теперь, если мы допустим Y = 1/2, мы получим

P( x & y ) = X/2
P( x | y ) = (X+1)/2

Теперь установите RHS на желаемую вероятность, и у нас есть два случая, которые мы можем решить для X

X = 2 p        // if we use &
X = 2 p - 1    // if we use |

Далее мы предполагаем, что можем использовать это снова, чтобы получить X в терминах другой переменной Z ... И затем мы продолжаем итерацию, пока не сделаем «достаточно».

Это немного неясно, но рассмотрим р = 0,375

0.375 * 2 = 0.75  < 1.0 so our first operation is &
0.75 * 2 = 1.5 > 1.0 so our second operation is |
0.5 is something we know so we stop.

Таким образом, мы можем получить переменную с p = 0,375 на X1 & (X2 | X3)

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

0.333 *2 = 0.666 < 1.0 so our first operation is &
0.666 *2 = 1.333 > 1.0 so our second operation is |
0.333 *2 = 0.666 < 1.0 so our third operation is &
etc...

, поэтому p = 0,333 можно сгенерировать с помощью

X1 & ( X2 | (X3 & (X4 | ( ... ) ) ) )

Теперь я подозреваю, что использование достаточного количества терминов в серии даст вам достаточно точности, и это можно записать как рекурсивную функцию. Однако, возможно, есть и лучший способ, что это тоже ... Я думаю, что порядок операций связан с двоичным представлением p, я просто не уверен, как именно ... и у меня нет времени думать об этом глубже.

В любом случае, вот какой-то непроверенный код C ++, который делает это. Вы должны быть в состоянии легко javaify это.

uint bitsWithProbability( float p )
{
   return bitsWithProbabilityHelper( p, 0.001, 0, 10 );
}

uint bitsWithProbabilityHelper( float p, float tol, int cur_depth, int max_depth )
{
   uint X = randbits();
   if( cur_depth >= max_depth) return X;
   if( p<0.5-tol)
   {
     return X & bitsWithProbabilityHelper( 2*p, 0.001, cur_depth+1, max_depth );
   }
   if(p>0.5+tol)
   {
     return X | bitsWithProbabilityHelper( 2*p-1, 0.001, cur_depth+1, max_depth );
   }
   return X;
}

Answer 2

Распределить пропорциональное количество бит по количеству. Псевдокод:

long generateNumber( double probability ){
  int bitCount = 64 * probability;
  byte[] data = new byte[64]; // 0-filled

  long indexes = getRandomLong();

  for 0 to bitCount-1 {
    do { 
      // distribute this bit to some postition with 0.
      int index = indexes & 64;
      indexes >> 6;
      if( indexes == 0 ) indexes = getRandomLong();
    } while ( data[index] == 0 );
    data[index] = 1;
  }

  return bytesToLong( data );
}    

Я надеюсь, вы понимаете, о чем я. Возможно, byte[] можно заменить на long и битовые операции, чтобы сделать его быстрее.

Answer 3

Вот еще один вариант ответа Майкла Андерсона

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

class BitsWithProbabilityHelper {
    public BitsWithProbabilityHelper(float prob, Random rnd) {
        if (Float.isNaN(prob)) throw new IllegalArgumentException();

        this.rnd = rnd;

        if (prob <= 0f) {
            zero = true;
            return;
        }

        // Decode IEEE float
        int probBits = Float.floatToIntBits(prob);
        mantissa = probBits & 0x7FFFFF;
        exponent = probBits >>> 23;

        // Restore the implicit leading 1 (except for denormals)
        if (exponent > 0) mantissa |= 0x800000;
        exponent -= 150;

        // Force mantissa to be odd
        int ntz = Integer.numberOfTrailingZeros(mantissa);
        mantissa >>= ntz;
        exponent += ntz;
    }

    /** Determine how many random words we need from the system RNG to
     *  generate one output word with probability P.
     **/
    public int iterationCount() {
        return - exponent;
    }

    /** Generate a random number with the desired probability */
    public long nextLong() {
        if (zero) return 0L;

        long acc = -1L;
        int shiftReg = mantissa - 1;
        for (int bit = exponent; bit < 0; ++ bit) {
            if ((shiftReg & 1) == 0) {
                acc &= rnd.nextLong();
            } else {
                acc |= rnd.nextLong();
            }
            shiftReg >>= 1;
        }
        return acc;
    }

    /** Value of <code>prob</code>, represented as m * 2**e where m is always odd. */
    private int exponent;  
    private int mantissa;

    /** Random data source */
    private final Random rnd;

    /** Zero flag (special case) */
    private boolean zero;
}

Answer 4

Вот как я решил это в конце.

1. Генерирует целое число N между 0..16, следуя биномиальному распределению. Это дает количество битов «1» в 16-битном частичном результате.
2. Произвольно сгенерировать индекс в справочной таблице, которая содержит 16-битные целые числа, содержащие желаемое количество битов «1».
3. Повторите 4 раза, чтобы получить четыре 16-разрядных целых числа.
4. Соедините эти четыре 16-разрядных целых числа вместе, чтобы получить 64-разрядное целое число.

Это было частично вдохновлено ответом Ондры Жижки.

Преимущество заключается в том, что оно уменьшает количество вызовов до Random.nextLong() до 8 вызовов на 64 бита вывода. Для сравнения, прокатка для каждого отдельного бита потребует 64 вызовов. Битовое И / ИЛИ использует от 2 до 32 вызовов в зависимости от значения P

Конечно, вычисление биномиальных вероятностей столь же дорого, поэтому они идут в другой справочной таблице.

Код много, но окупается с точки зрения производительности.

---

Обновление - объединено с побитовым решением И / ИЛИ. Теперь он использует этот метод, если догадывается, что он будет более эффективным (с точки зрения вызовов Random.next().)

Answer 5

Если вы ищете применение некоторого распределения, где с вероятностью P вы получаете 1, а с вероятностью 1-P вы получаете 0 при любом конкретном бите, ваша лучшая ставка - просто генерировать каждый бит независимо с вероятностью P того, чтобы быть 1 (это звучит как рекурсивное определение, я знаю).

Вот решение, я пройдусь по нему ниже:

public class MyRandomBitGenerator
{

    Random pgen = new Random();

    // assumed p is well conditioned (0 < p < 1)
    public boolean nextBitIsOne(double p){
        return pgen.nextDouble() < p ? true : false;
    }

    // assumed p is well conditioned (0 < p < 1)
    public long nextLong(double p){
        long nxt = 0;
        for(int i = 0; i < 64; i++){
           if(nextBitIsOne(p)){
               nxt += 1 << i;
           }
        }
        return nxt;
    }

}

По сути, сначала мы определяем, как сгенерировать значение 1 с вероятностью P: pgen.nextDouble() генерирует число от 0 до 1 с одинаковой вероятностью, спрашивая, меньше ли оно p, мы выбираем это распределение так, мы ожидаем увидеть p 1s, когда будем вызывать эту функцию бесконечно.

Answer 6

Используйте генератор случайных чисел, который генерирует равномерное число с плавающей точкой r между 0 и 1. Если r> p, тогда установите бит в 0, в противном случае установите его в 1

Answer 7

Предположим, размер битового массива равен L. Если L = 1, вероятность того, что 1-й бит равен 1, будет P, а значение 0 будет 1-P. Для L = 2 вероятность получения 00 составляет (1-P) ² , 01 или 10 - это P (1-P) каждый, а 11 - P ² . Расширяя эту логику, мы можем сначала определить первый бит, сравнивая случайное число с P, а затем масштабировать случайное число так, чтобы мы снова могли получить что-нибудь между 0 и 1. Пример кода JavaScript:

function getRandomBitArray(maxBits,probabilityOf1) {
    var randomSeed = Math.random();
    bitArray = new Array();
    for(var currentBit=0;currentBit<maxBits;currentBit++){
        if(randomSeed<probabilityOf1){
            //fill 0 at current bit
            bitArray.push(0);
            //scale the sample space of the random no from [0,1)
            //to [0.probabilityOf1)
            randomSeed=randomSeed/probabilityOf1;
        }
        else{
            //fill 1 at current bit
            bitArray.push(1);
            //scale the sample space to [probabilityOf1,1)
            randomSeed = (randomSeed-probabilityOf1)/(1-probabilityOf1);
        }
    }
}

EDIT: Этот код генерирует совершенно случайные биты. Я попытаюсь объяснить алгоритм лучше.

Каждая битовая строка имеет определенную вероятность появления. Предположим, что строка имеет вероятность появления p ; мы хотим выбрать эту строку, если наше случайное число падает на некоторый интервал длины p. Начальная точка интервала должна быть фиксированной, но ее значение не будет иметь большого значения. Предположим, мы правильно выбрали до k бит. Затем для следующего бита мы делим интервал, соответствующий этой битовой строке длиной k, на две части размеров в соотношении P: 1 - P (здесь P - вероятность получения 1). Мы говорим, что следующий бит будет равен 1, если случайное число находится в первой части, и 0, если оно находится во второй части. Это гарантирует, что вероятности строк длины k + 1 также остаются правильными.

Java-код:

public ArrayList<Boolean> getRandomBitArray(int maxBits, double probabilityOf1) {
    double randomSeed = Math.random();
    ArrayList<Boolean> bitArray = new ArrayList<Boolean>();
    for(int currentBit=0;currentBit<maxBits;currentBit++){
        if(randomSeed<probabilityOf1){
            //fill 0 at current bit
            bitArray.add(false);
            //scale the sample space of the random no from [0,1)
            //to [0.probabilityOf1)
            randomSeed=randomSeed/probabilityOf1;
        }
        else{
            //fill 1 at current bit
            bitArray.add(true);
            //scale the sample space to [probabilityOf1,1)
            randomSeed = (randomSeed-probabilityOf1)/(1-probabilityOf1);
        }
    }
    return  bitArray;
}