Non-repeating stream of pseudo-random numbers with 'clumping'

Cascade multiple LFSRs with periods less than you need, concatenating them to produce a result such as the fastest changing register drives the least significant values. So, if you have L1 with period 3, L2 with period 15, and L3 with some longer period, N = L1 (n) + 3 * L2 (n / 3) + 45 * L3 (n / 45). This will obviously generate 3 thickening values ​​and then jump over and total 3 more thickening values. Use something other than multiplication (for example, mixing some bits of higher period registers) or different periods so that the spread of the clusters is wider than the period of the first register. It won't be particularly smoothly random, but it will be lumpy and non-repetitive.

Perhaps you can create a random sequence and then do some strategic element replacement to get the property you want.

For example, if you find 3 values ​​a, b, c in a sequence, such that a> b and a> c, then with some probability you can swap elements a and b or elements a and c.

EDIT in response to comment:

Yes, you can have a buffer in the stream of whatever size you like. Swap rules can be deterministic or based on another known reproducible pseudo-random sequence.

One way to get lumpy numbers is to use the normal distribution.

You run a random list with your "initial" random value, then generate a random number with the mean of the previous random value and constant variance, and repeat as needed. The overall variance of the entire list of random numbers should be approximately constant, but the "running average" of your numbers will drift randomly without any particular bias.

>>> 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]

      

        
        
        
      

    

I know it's hard to tell by looking at the numbers, but you can see that the numbers are piling up a bit - 5X at the end and 0.X on the second line.

If you only want integers, you can just use a very large mean and variance, and truncate / divide to get an integer output. Regular distributions are by definition a continuous distribution, which means that all real numbers are potential outputs - this is not limited to integers.

Here's a quick scatter plot in Excel of 200 numbers (starting at 0, constant variance 1):

scatter data http://img178.imageshack.us/img178/8677/48855312.png

I am not aware of an existing algorithm that would do this, but it seems difficult to roll your own (depending on how stringent the "limited state" requirement is). For example:

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

      

        
        
        
      

    

It's a little rudimentary, but would something like this satisfy your needs?

How about (psuedo code)

// 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);

      

        
        
        
      

    

In the range [0, 10], the following should give an even distribution. random()

gives a (pseudo) random number r

c 0 <= r < 1

.

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

      

        
        
        
      

    

You can get the behavior you want by delinearizing random()

- for example, it random()^k

will skew towards small numbers for k > 1

. A possible function might be as follows, but you will have to try some exponents to find the distribution you want. And keep the exponent odd if you use the following function ...;)

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

      

        
        
        
      

    

Is there a sequence like 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 (mod. 100) look good?

This is the result of a small ruby ​​program (explained below):

#!/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(', ')

      

        
        
        
      

    

The idea is to start with the sequence 0..n-1 and break the order by going k times over the sequence (more passes means less condensation). Each pass first considers pairs of numbers at positions 0 and 1, 2 and 3, 4 and 5, etc. (Common: 2i and 2i + 1) and flips a coin for each pair. Heads (= 1) means swapping numbers in a pair, tails (= 0) means they do not swap them. Then the same is done for pairs in positions 1 and 2, 3 and 4, etc. (General: 2i + 1 and 2i + 2). Since you mentioned that your sequence is mod 10, I have additionally swapped positions 0 and n-1 if the coin for that pair dictates so.

One number x can be displayed modulo n after k goes to any number in the segment [xk, x + k] and is approximately binomially distributed around x. Pairs (x, x + 1) of numbers do not change independently.

As a pseudo-random generator, I only used the last of the 128 output bits of the MD5 hash function, pick whichever function you want. Thanks to clumping, one will not get a "safe" (= unpredictable) random sequence.