Неповторяющийся поток псевдослучайных чисел с «комкованием»

Question

Я ищу метод для генерации псевдослучайного потока с несколько странным свойством - я хочу сгустки соседних чисел.

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

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

Пример желаемой последовательности (мод 10): 1 3 9 8 2 7 5 6 4
Я подозреваю, что это было бы более очевидно с большим потоком, но трудно ввести вручную.

Обновление:
Я не понимаю, почему это невозможно, но да, я ищу, как подытожил Велбог:

• Неповторяющийся
• Не отслеживается
• "Скомкано"

Answer 1

Каскадируйте несколько LFSR с периодами, меньшими, чем вам нужно, комбинируя их, чтобы получить результат, такой как самый быстро меняющийся регистр, управляет наименее значимыми значениями. Так что если у вас есть L1 с периодом 3, L2 с периодом 15 и L3 с некоторым большим периодом, N = L1 (n) + 3 * L2 (n / 3) + 45 * L3 (n / 45). Это, очевидно, сгенерирует 3 сгруппированных значения, затем перейдет к другим 3 сгруппированным значениям. Используйте что-то иное, чем умножение (например, смешивание некоторых битов регистров с более высоким периодом) или другие периоды, чтобы сгусток распространился шире, чем период первого регистра. Это не будет особенно гладко случайным, но оно будет комковатым и неповторяющимся.

Answer 2

Для справки, я нахожусь в лагере "10000 *" "неповторяющееся, не случайное, не отслеживающее - смертельная комбинация", и я надеюсь, что некоторые простые эксперименты хотя бы пролят свет. Это не формальное доказательство какими-либо средствами. Возможно, кто-то поддержит это.

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

Учитывая x_i, x_ (i + 1) ~ U (x_i, r), где r> x_i.

Например:

если x_i = 6, x_ (i + 1) - случайный выбор из (6 + epsilon, some_other_real> 6). Это гарантирует неповторение, но за счет того, что распределение монотонно увеличивается.

Без какого-либо условия (например, монотонности), присущего последовательности самих генерируемых чисел, как еще вы можете гарантировать уникальность без несущего состояния?

Редактировать : Итак, после исследования утверждения RBarryYoung о " линейных конгруэнтных генераторах " (не дифференцирующих ... это то, что имел в виду RBY), и ясно, Я был неправ! Эти последовательности существуют, и по необходимости любой PRNG, следующий номер которого зависит только от текущего номера и некоторого глобального неизменяемого состояния, не может иметь повторений в течение цикла (после некоторого начального периода записи).

Answer 3

Может быть, вы можете соединить 2 или более LCG аналогичным образом, как описано для LSFR, описанных здесь. Внедрите наименее значимую LCG с начальным значением в полном цикле, увеличивайте следующую LCG. Вам нужно только хранить семена для каждого LCG. Затем вы можете взвесить каждую часть и сложить ее вместе. Чтобы избежать повторений в «сгруппированной» части LstSig, вы можете случайным образом повторно заполнять LCG на каждом полном цикле.

Answer 4

Имеет ли последовательность, как 0, 94, 5, 1, 3, 4, 14, 8, 10, 9, 11, 6, 12, 7, 16, 15, 17, 19, 22, 21, 20, 13 , 18, 25, 24, 26, 29, 28, 31, 23, 36, 27, 42, 41, 30, 33, 34, 37, 35, 32, 39, 47, 44, 46, 40, 38, 50 , 43, 45, 48, 52, 49, 55, 54, 57, 56, 64, 51, 60, 53, 59, 62, 61, 69, 68, 63, 58, 65, 71, 70, 66, 73 , 67, 72, 79, 74, 81, 77, 76, 75, 78, 83, 82, 85, 80, 87, 84, 90, 89, 86, 96, 93, 98, 88, 92, 99, 95 , 97, 2, 91 (мод 100) хорошо выглядеть?

Это вывод небольшой программы ruby ​​(пояснения приведены ниже):

#!/usr/bin/env ruby

require 'digest/md5'

$seed = 'Kind of a password'
$n = 100 # size of sequence
$k = 10  # mixing factor (higher means less clumping)
def pseudo_random_bit(k, n)
  Digest::MD5.hexdigest($seed + "#{k}|#{n}")[-1] & 1
end

def sequence(x)
  h = $n/2
  $k.times do |k|
    # maybe exchange 1st with 2nd, 3rd with 4th, etc
    x ^= pseudo_random_bit(k, x >> 1) if x < 2*h
    # maybe exchange 1st with last
    if [0, $n-1].include? x
      x ^= ($n-1)*pseudo_random_bit(k, 2*h)
    end
    # move 1st to end
    x = (x - 1) % $n
    # maybe exchange 1st with 2nd, 3rd with 4th, etc
    # (corresponds to 2nd with 3rd, 4th with 5th, etc)
    x ^= pseudo_random_bit(k, h+(x >> 1)) if x < 2*(($n-1)/2)
    # move 1st to front
    x = (x + 1) % $n
  end
  x
end

puts (0..99).map {|x| sequence(x)}.join(', ')

Идея в основном состоит в том, чтобы начать с последовательности 0..n-1 и нарушить порядок, пропустив k раз по последовательности (чем больше проходов, тем меньше комкование). В каждом проходе один сначала смотрит на пары чисел в позициях 0 и 1, 2 и 3, 4 и 5 и т. Д. (Общие: 2i и 2i + 1) и подбрасывает монету для каждой пары. Головки (= 1) означают обмен номерами в паре, хвосты (= 0) означают, что не обмениваются ими. Затем вы делаете то же самое для пар в позициях 1 и 2, 3 и 4 и т. Д. (Общие: 2i + 1 и 2i + 2). Поскольку вы упомянули, что ваша последовательность - мод 10, я дополнительно обменял позиции 0 и n-1, если монета для этой пары диктует это.

Одно число x может быть отображено по модулю n после того, как k проходит к любому числу интервала [x- k , x + k ] и составляет приблизительно бином, распределенный вокруг х. Пары (x, x + 1) чисел не модифицируются независимо.

В качестве генератора псевдослучайных данных я использовал только последний из 128 выходных битов хеш-функции MD5, вместо этого выберите любую функцию, которую вы хотите. Благодаря скоплению нельзя получить «безопасную» (= непредсказуемую) случайную последовательность.

Answer 5

В диапазоне [0, 10] следующее должно давать равномерное распределение. random() возвращает (псевдо) случайное число r с 0 <= r < 1.

x(n + 1) = (x(n) + 5 * (2 * random() - 1)) mod 10

Вы можете получить желаемое поведение, разделив random() - например, random()^k будет перекошено в сторону небольших чисел для k > 1. Возможная функция может быть следующей, но вам придется попробовать некоторые показатели, чтобы найти желаемое распределение. И оставляйте показатель степени нечетным, если вы используете следующую функцию ...;)

x(n + 1) = (x(n) + 5 * (2 * random() - 1)^3) mod 10

Answer 6

Как насчет (псевдо-код)

// clumpiness static in that value retained between calls
static float clumpiness = 0.0f; // from 0 to 1.0        
method getNextvalue(int lastValue)
   float r = rand();  // float from 0 to 1

   int change = MAXCHANGE * (r - 0.5) * (1 - clumpiness); 

   clumpiness += 0.1 * rand() ;
   if (clumpiness >= 1.0) clumpiness -= 1.0;
   // -----------------------------------------
   return Round(lastValue + change);

Answer 7

Я не знаю ни одного существующего алгоритма, который бы это делал, но, кажется, не сложно свернуть свой собственный (в зависимости от того, насколько строгим является требование "ограниченного количества состояний") Например:

RANGE = (1..1000)
CLUMP_ODDS = .5
CLUMP_DIST = 10

last = rand(RANGE)
while still_want_numbers
  if rand(CLUMP_ODDS)   # clump!
    next = last + rand(CLUMP_DIST) - (CLUMP_DIST / 2)  # do some boundary checking here
  else   # don't clump!
    next = rand(RANGE)
  end
  print next
  last = next
end

Это немного зачаточно, но подойдет ли что-то подобное вашим потребностям?

Answer 8

Один из способов получить «комковатые» числа - использовать нормальное распределение.

Вы начинаете случайный список со своего «начального» случайного значения, затем генерируете случайное число со средним значением предыдущего случайного значения и постоянной дисперсией и повторяете при необходимости. Общая дисперсия всего вашего списка случайных чисел должна быть приблизительно постоянной, но «скользящее среднее» ваших чисел будет меняться случайным образом без какого-либо особого смещения.

>>> r = [1]
>>> for x in range(20):
    r.append(random.normalvariate(r[-1], 1))
>>> r
[1, 0.84583267252801408, 0.18585962715584259, 0.063850022580489857, 1.2892164299497422, 
0.019381814281494991, 0.16043424295472472, 0.78446377124854461, 0.064401889591144235, 
0.91845494342245126, 0.20196939102054179, -1.6521524237203531, -1.5373703928440983, 
-2.1442902977248215, 0.27655425357702956, 0.44417440706703393, 1.3128647361934616, 
2.7402744740729705, 5.1420432435119352, 5.9326297626477125, 5.1547981880261782]

Я знаю, что это трудно понять, посмотрев на цифры, но вы можете вроде увидеть, что числа немного слипаются - 5.X в конце и 0.X вкл. второй ряд.

Если вам нужны только целые числа, вы можете просто использовать очень большое среднее значение и дисперсию и усекать / делить для получения целочисленного вывода. Нормальные распределения по определению являются непрерывным распределением, то есть все действительные числа являются потенциальными выходными данными - оно не ограничено целыми числами.

Вот график быстрого разброса в Excel 200 чисел, сгенерированных таким образом (начиная с 0, постоянная дисперсия 1):

данные разброса http://img178.imageshack.us/img178/8677/48855312.png

---

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

Answer 9

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

Например, если вы найдете 3 значения a, b, c в такой последовательности, что a > b и a > c , тогда с некоторой вероятностью вы можете поменять местами элементы a и b или элементы a и c .

РЕДАКТИРОВАТЬ в ответ на комментарий:

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

Answer 10

Определяя «особенности сгущения» в терминах распределения вероятностей его размера и распределения вероятностей его диапазона, вы можете затем использовать простые случайные генераторы с базовым распределением и создавать последовательности.