I can’t call this pseudorandom since it relies on randomness, but the sequences generated are not equally likely over the set of all possible orderings of integers from 1 to N.
To generate the sequence of length N:
-
Make a list of numbers 1 to N.
-
Choose a random[sup]*[/sup] number from 1 to N. (I’ll call this “rolling” to suggest rolling dice and to distinguish it).
-
If the number is on the list, choose it.
If it is not on the list, choose the next available number on the list, rolling around to the front of the list if necessary. -
Add the chosen number to the sequence and cross it off the list.
-
Repeat until the list is empty.
Example:
Say your list is 100 numbers long. You roll a 67. If 67 is already crossed off, use 68. If 68-74 is chosen, use 75. If 68-100 have been chosen, use 1, or the whatever the first available number is. Whatever number used is crossed off the list.
Certainly the resulting sequence is not in random order. Shifted sequences (e.g. [1,2,3…100] or [4,5,6…100,1,2,3]) are the most likely result. But it is the case (I believe) that for any particular position in the sequence, any number is equally likely to appear in that spot as any other. So it’s got some quality of randomness, but I’m not sure what.
One thing I’m trying to figure out is the distribution of the sequences. After the shifted sequences, the ones with just a few numbers out of place seem likely. But I’m not sure how to characterize those.
For example, here’s what the sequences are for N=4. On the right are a given set of sequences (each written as four-digit numbers). The number to the left is the number of times one of those sequences will result from three random rolls. (The last roll doesn’t affect the outcome, so it can be ignored).
6 [1234, 2341, 3412, 4123]
3 [2134, 3241, 4312, 1423]
2 [1243,1324,1342, 2314,2431,2413, 3421,3142,3124, 4132,4213,4231]
1 [1432, 2143, 3214, 4321]
I’ve grouped them so they all follow the same pattern of ‘rearrangement’ from the top row. For instance, 1234=>1243 by swapping the last two, and 3412=>3421 in the same manner.
The bottom row makes sense. If you start with a number, you can’t find more than two numbers in order as you go around the list. (Example: Take 4321; start with 2: 2-3 is in order, 2-4 is in order, but no others once you circle back to 2).
What I can’t figure out is the middle rows. For one thing, it seems strange that not all shifted sequences are equivalent - 2134 is more likely than 1342. The only distinguishing thing is that from the first to second row, only the first two numbers are swapped.
I don’t know a lot about pseudorandomness and what tests are used on it, so I’m curious about the properties of something like this, especially the noted one about numbers equally likely to be in a given spot, and if it’s familiar to anyone.
[sup]*[/sup] Assume this to be perfect. For example, rolling a perfect die.