-1

I want to generate an endless series of quasi random numbers to the following specification:-

  • Source of numbers is uniformly distributed and random, ranging 0 through 255 inclusive. It's an existing hardware device.
  • Required output range is 1 through 8 inclusive.
  • Two consecutive output numbers are never the same. For example 5 will never follow 5, but you can have 5,2,5.
  • Exactly one output number is required for every single source number. Rejection sampling therefore cannot be used. And while() loops, shuffles etc. can't be used.

It's this last stipulation that's vexing me. The source generator can only supply random bytes at a constant 1 /s and I want output at a constant 1 /s. Typically you'd simply reject a generated number if it was equal to the previous one, and generate another. In my case you only get one shot at each output. I think that it's some sort of random selection process, but this requirement has me going around in circles as I'm a bad programmer. An algorithm, flowchart or picture will do, but I'll be implementing in Java.

Apologies for the semi generic title, but I couldn't really think of anything more accurate yet concise.

Paul Uszak
  • 377
  • 4
  • 18
  • If I understand you correctly, you're only using 3 out of every 8 random input bits? – Oliver Charlesworth Jul 16 '17 at 23:59
  • Either way, why can't you just do something like X+1 if the value is the same as previous? – Oliver Charlesworth Jul 17 '17 at 00:00
  • 1
    @OliverCharlesworth X+1 isn't random is it? And X + RANDOM won't work as you only get one shot each time and X + RANDOM could = X. Tricky. – Paul Uszak Jul 17 '17 at 00:03
  • Possible duplicate of [Generate non repeating random number within range in Java](https://stackoverflow.com/questions/13862430/generate-non-repeating-random-number-within-range-in-java) –  Jul 17 '17 at 00:04
  • @hwdbc Nope. They use rejection sampling and shuffle() which I can't do with only one number per attempt... – Paul Uszak Jul 17 '17 at 00:08
  • Then it's not truly random if you have the bias of a number not repeating what came previously. – Tim Biegeleisen Jul 17 '17 at 00:09
  • @TimBiegeleisen Hence 4th word in title. – Paul Uszak Jul 17 '17 at 00:10
  • As output distribution is not specified, you could just "mod 8" sum the numbers and increment the result by one (mod 8 again) if it collides with the last one. (This will generate numbers between 0...7, so add 1 at the very end) – tevemadar Jul 17 '17 at 00:12
  • I retracted the flag. –  Jul 17 '17 at 00:13

2 Answers2

1

If I understand the problem correctly, the first random number will be chosen randomly from among 8 different numbers (1 to 8), while every successive random number will be chosen from 7 different possibilities (1 to 8 excluding the previous one). Thus, your range of 256 values will need to be divided into 7 possibilities. It won't come out even, but that's the best you can do. So you need something like

public class RandomClass {
    public RandomClass(HardwareSource source) {
        this.source = source;
        first = true;
    }
    pubic int nextRandom() {
        int sourceValue = source.read();
        int value;
        if (first) {
            value = sourceValue % 8 + 1;
            prev = value;
        } else {
            value = sourceValue % 7 + 1;
            if (value >= prev) {
                value++;
            }
        prev = value;
        first = false;
        return value;
    }
}

Suppose the first call generates 5. The second time you call it, value is first computed to be a number from 1 to 7; by incrementing it if the value is >= 5, the range of possible outputs becomes 1, 2, 3, 4, 6, 7, 8. The output will be almost evenly distributed between those two values. Since 256 is not divisible by 7, the distribution isn't quite even, and there will be a slight bias toward the lower numbers. You could fix it so that the bias will shift on each call and even out over the entire sequence; I believe one way is

 value = (sourceValue + countGenerated) % 7 + 1;

where you keep track of how many numbers you've generated.

I think this is better than solutions that take the input modulo 8 and add 1 if the number equals the previous one. Those solutions will generate prev + 1 with twice the probability of generating other numbers, so it's more skewed than necessary.

ajb
  • 31,309
  • 3
  • 58
  • 84
  • Yes, I need to perform a Chi2 test on the algorithm's output. It's important that the numbers are uniformly distributed and not biased in the long run. So after 8 billion outputs, there should be ~1 billion of each 1 to 8 value. – Paul Uszak Jul 17 '17 at 00:57
  • Then my first solution won't work, but making the change I suggested later in the post should do it. P.S. I'd highly recommend doing a test with a fake `HardwareSource` first, and do your statistical analysis on the output. – ajb Jul 17 '17 at 01:02
  • Thought: Is the uniformity problem due to having 8 possible outputs and therefore choosing from an odd number (1-7)? If I had 7 possibles, so had to choose from 6 (even), would the bias be easier to overcome? – Paul Uszak Jul 17 '17 at 13:55
  • @PaulUszak - In this particular case, the "amount" of bias is identical. (256 - 4) == (7*36) == (6*42). So 4 values will be chosen slightly more often in both cases. – Oliver Charlesworth Jul 17 '17 at 17:29
  • @PaulUszak if changing the number of leds is an option, go for (2^n)+1. Nearest ones to the original (8) are 9, then 5, then 17. Largest one with the current generator is 257. – tevemadar Jul 20 '17 at 14:22
0
int sum=0;
int prev=-1;
int next(int input){
  sum=(sum+input)%8;
  if(sum==prev)sum=(sum+1)%8;
  prev=sum;
  return sum+1;
}

(As I interpret even with the new bold emphasis, it is not required to always generate the same output value for the same input value - that would make the task impossible to solve)

tevemadar
  • 12,389
  • 3
  • 21
  • 49
  • I hadn't thought of it in those terms, but yes you're absolutely right. Very elegant. It's for an art display illustrating true randomness using flashing lights. Hence two consecutive identical numbers wouldn't cause a change of lit bulb. – Paul Uszak Jul 17 '17 at 00:28