Test for randomness of a permutation

For the discussion of math. Duh.

Moderators: gmalivuk, Prelates, Moderators General

Test for randomness of a permutation

Postby spdqbr » Tue Apr 22, 2008 4:18 am UTC

Hey guys,

It'd been a while since stats. I'm looking for a test to determine how well a pseudorandom permutation generator approximates true randomness.

example:
The algorithm will take a list of (not necessarily distinct) digits: {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4} and permute the elements using pseudorandom number generator: {3, 4, 1, 4, 1, 3, 2, 1, 3, 4, 2, 2}. Note that if any number occurs n times, all digits occur n times.

I would like to know a way to determine if this gives a good long term approximation of a truly random process, like labeling index cards and putting them in a tumble drier for a few days, then pulling them out and stacking them up with your eyes closed. The actual lists I'm permuting will have anywhere from 2.56x1055 to 1.54x10191 possible permutations, and there's a cookie in it for you if you can figure out where those numbers come from.

My theory is this:
Run several trials (say, 1 million or more need help determining an appropriate amount) using the randomizer. For each trial, log how often number x shows up in position n. If the scramble is a good approximation of random, there should be roughly the same number of occurrences of each number in each position (since each number occurs the same number of times). Am I correct in assuming that for a truly random permutation generator, the standard deviation of this particular frequency list should be approximately zero? So therefor if my generator's frequency list has an approximately zero standard deviation, it could considered approximately random?

There are a few other complications that arise, such as certain permutations not being legal (hint for the cookie), but I think I can deal with them once I understand how to compare something that is pseudorandom to true random.

Thanks everyone!
In questions of science, the authority of a thousand is not worth the humble reasoning of a single individual.

Galileo
User avatar
spdqbr
 
Posts: 171
Joined: Sat Mar 08, 2008 1:41 am UTC
Location: A shaker of salt

Re: Test for randomness of a permutation

Postby evilbeanfiend » Tue Apr 22, 2008 11:29 am UTC

practical or theoretical? also how long is the sequence? trying to compress it using a good compression algorithm is a good quick way of weeding out poor randomisation. for more rigorous testing you should do things like plot the distribution of values per position or look at correlations between different sections of the sequence.

note that your scheme alone just tests that the distribution is flat, there are an awful lot of low entropy sequences that will match this. also it is possible for a random process to have a non-flat distribution e.g. a lot of physical random processes have normal distributions. however the distribution may well be important to you.

what do you need it for?
in ur beanz makin u eveel
User avatar
evilbeanfiend
 
Posts: 2650
Joined: Tue Mar 13, 2007 7:05 am UTC
Location: the old world

Re: Test for randomness of a permutation

Postby spdqbr » Tue Apr 22, 2008 2:44 pm UTC

Practical, I do actually plan on implementing it. There are two sequences I'm concerned about, one is 6 digits repeated 8 times each, on is 12 digits repeated 10 times each.

The purpose
Spoiler:
I'm trying to compare different scramble generators for the Rubik's cube and the megminx respectively. I'd like to know how many twists for which generator are sufficient and various other parameters of the scramble as well.
In questions of science, the authority of a thousand is not worth the humble reasoning of a single individual.

Galileo
User avatar
spdqbr
 
Posts: 171
Joined: Sat Mar 08, 2008 1:41 am UTC
Location: A shaker of salt

Re: Test for randomness of a permutation

Postby evilbeanfiend » Tue Apr 22, 2008 3:14 pm UTC

hmm i'd try to start with using a compression algo (assuming you have a library to do one) on the sequence after each twist and stopping when the algo can't get any improvement in compression compared with the last. not sure what compression techniques are good for very short sequences though so this still might mean you need to write your own entropy measuring function.
in ur beanz makin u eveel
User avatar
evilbeanfiend
 
Posts: 2650
Joined: Tue Mar 13, 2007 7:05 am UTC
Location: the old world

Re: Test for randomness of a permutation

Postby Tinyboss » Tue Apr 22, 2008 5:02 pm UTC

The standard deviation test alone won't guarantee randomness, since if you just shifted the sequence to the right by one element over and over, you'd get a perfect distribution, but no randomness.

I propose that the fact of repeated digits is actually irrelevant, and that you should just choose randomly a permutation out of the space of all permutations on N letters (the size of which is N!). Just choose a random integer in that space (paying attention to the implementation of your PRNG!), construct the permutation that belongs to that number, then apply it to your sequence.

Then you reduce the question of a random permutation to the easier one of randomly choosing 0<k<N!.
User avatar
Tinyboss
 
Posts: 16
Joined: Sat Apr 19, 2008 8:13 pm UTC

Re: Test for randomness of a permutation

Postby spdqbr » Wed Apr 23, 2008 1:25 am UTC

@evilbeanfiend: I'm not sure I understand the underlying principle at work here. Are you suggesting that the when two things are roughly equally random, the compression algorithm should be able to compress the sequence roughly equally well?

@Tinyboss: I did consider this method but discarded it for a few reasons. 1. I'm not entirely sure how to map an integer to a permutation, 2. Even if I could, generating a reasonable length sequence of twists to get to that permutation is non-trivial. For the cube it's not so bad (23+ move twists can be found in less than a second for any permutation), but for the megaminx it's a bit more difficult. However, if I could find a 1 to 1 function to map a permutation to an integer (seems intuitively easier than the other direction to me), could I then generate many scrambles with my generator and compare the distribution to what I would expect for a random distribution from the range [0,size_of_space]?

The big question is would the mapping f:<permutations>-[0,size_of_space] need to map similar permutations to nearby numbers? If one permutation maps to 190938461 would the mapping need to place a permutation with exactly two elements swapped nearby for the analysis to work?

I really appreciate the help guys! Thank you.
In questions of science, the authority of a thousand is not worth the humble reasoning of a single individual.

Galileo
User avatar
spdqbr
 
Posts: 171
Joined: Sat Mar 08, 2008 1:41 am UTC
Location: A shaker of salt

Re: Test for randomness of a permutation

Postby Cosmologicon » Wed Apr 23, 2008 2:30 am UTC

You won't be able to prove that your PRNG is good with a statistical test. But, if you try your best at proving it's bad and fail, that's a good sign. Here's my recommendation as to how to go about doing that. Any function from the set of permutations to a (relatively small) set of values can be analyzed with the chi-square test. You just need to be able to come up with the theoretical probabilities of each function value.

For instance, in the example of permuting {1,1,1,2,2,2,3,3,3,4,4,4}, one possible function just returns the number in the 5th slot. This obviously has 1/4 chance of being 1, 1/4 chance of being 2, and so on. You then do this N = 1,000,000 times, like you said, and log the number of times each value comes up. You'll get an average of N/4 for each value, but there will be a scatter about that, and you should not assume that it's 0. Instead, compute the chi-squared test statistic for this table, then convert that to a p-value for a chi-square with 3 degrees of freedom. What you normally do at this point is run the whole test over 1000 times and keep track of the p-values, then plot a histogram of them and see if they appear to follow a uniform distribution.

The chi-square test with this simple example function will show something suspicious if you consistently get too close to N/4, so it will be able to tell you that Tinyboss's counterexample is indeed not random.

The other thing it's got going for it is that it's easy to apply to more sophisticated functions than just looking in the 5th element. For instance, you could count the number of 1's that are in even positions. As long as you can work out the probability of the outcomes, you can apply the chi-square test.
User avatar
Cosmologicon
 
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA

Re: Test for randomness of a permutation

Postby NathanielJ » Wed Apr 23, 2008 3:24 am UTC

Cosmologicon wrote:Instead, compute the chi-squared test statistic for this table, then convert that to a p-value for a chi-square with 3 degrees of freedom. What you normally do at this point is run the whole test over 1000 times and keep track of the p-values, then plot a histogram of them and see if they appear to follow a uniform distribution.


I assume here that you don't mean the uniform distribution on [0,1] but rather just that there's no significant "clumping" of p-values, correct? If so, then this indeed seems to be the way to go.
Homepage: http://www.njohnston.ca
Conway's Game of Life: http://www.conwaylife.com
User avatar
NathanielJ
 
Posts: 880
Joined: Sun Jan 13, 2008 9:04 pm UTC

Re: Test for randomness of a permutation

Postby spdqbr » Wed Apr 23, 2008 3:40 am UTC

Cosmologicon, you have jarred something loose in my brain that got trapped there a few years ago in statistics. I definitely recall hypothesis testing with the chi squared distribution, and I have dusted off my stats book to page 410 and am knee deep in probability density function glory. Thanks!

The rough part is that some of the restrictions inherent in the puzzles make it somewhat difficult to find a good function for permutation to integer. The fact that I'm only considering even permutations is simple enough, but things like a 1 in position n will make a 1 in position m impossible. But the gears are turning, and I'm thinking instead of operating solely on the stickers (as you would for scramble tracking) to operating on the pieces. This simplifies the problem greatly as there are two independent subgroups, the corners (8 pieces) and the edges (12 pieces) which can be examined separately. I still have to account for the orientation of the pieces, but I have plans... I've begun to ramble.

Thanks again!
In questions of science, the authority of a thousand is not worth the humble reasoning of a single individual.

Galileo
User avatar
spdqbr
 
Posts: 171
Joined: Sat Mar 08, 2008 1:41 am UTC
Location: A shaker of salt

Re: Test for randomness of a permutation

Postby Tinyboss » Wed Apr 23, 2008 4:09 am UTC

spdqbr wrote:@Tinyboss: I did consider this method but discarded it for a few reasons. 1. I'm not entirely sure how to map an integer to a permutation, 2. Even if I could, generating a reasonable length sequence of twists to get to that permutation is non-trivial. For the cube it's not so bad (23+ move twists can be found in less than a second for any permutation), but for the megaminx it's a bit more difficult. However, if I could find a 1 to 1 function to map a permutation to an integer (seems intuitively easier than the other direction to me), could I then generate many scrambles with my generator and compare the distribution to what I would expect for a random distribution from the range [0,size_of_space]?


I wrote a permutation class in Python to run through some experiments in my abstract algebra course. I'm sure it's been done better and before, but it was a fun exercise. Here's a recursive function (actually not part of the class itself) that returns the nth permutation on a list L:
Code: Select all
def nth_list_permutation(n, L):
    """Return the nth permutation of the list L"""
    if len(L) < 2:
        return L
    f = fac(len(L)-1)
    k, n = divmod(n, f)
    return [L[k]] + nth_list_permutation(n, L[:k]+L[k+1:])


Where "fac" is the factorial, and "q, r = divmod(n, d)" implies that q*d + r = n (integer division with remainder). The last line isn't very clear if you're not familiar with Python, but it's just pulling out the kth element, then calling itself recursively on the remaining list of N-1 items, with the remainder of the division of n by (N-1)!.

You could map the other direction pretty easily, but with repeated elements, it's no longer a single-valued function. Your distribution might be skewed that way--but I can't intuitively see exactly how that would look.
User avatar
Tinyboss
 
Posts: 16
Joined: Sat Apr 19, 2008 8:13 pm UTC

Re: Test for randomness of a permutation

Postby evilbeanfiend » Wed Apr 23, 2008 10:34 am UTC

spdqbr wrote:@evilbeanfiend: I'm not sure I understand the underlying principle at work here. Are you suggesting that the when two things are roughly equally random, the compression algorithm should be able to compress the sequence roughly equally well?


short answer, yes.

in information theory the amount you can compress a sequence without loss is related to the information entropy (approx. the randomness), now obviously any actual compression algo isn't going to be perfect but it should be good enough that this approach will stop when you have reasonably high entropy (assuming you have a half decent compression algo) as the algorithm will find it harder to compress.
in ur beanz makin u eveel
User avatar
evilbeanfiend
 
Posts: 2650
Joined: Tue Mar 13, 2007 7:05 am UTC
Location: the old world

Re: Test for randomness of a permutation

Postby Cosmologicon » Wed Apr 23, 2008 2:23 pm UTC

spdqbr wrote:The rough part is that some of the restrictions inherent in the puzzles make it somewhat difficult to find a good function for permutation to integer.

Your function doesn't have to be that sophisticated for you to get started. For the cube, I believe that even if you restrict yourself to even permutations, there are 24 possible equally-likely pairs of colors that you'd get on any given edge piece (that is, 12 different pieces in each of 2 orientations). So right there is an easy mapping from the permutation to the numbers 1-24.

Another thing you can easily look for is correlations between consecutive permutations. Instead of generating one permutation, generate two, and map each of them to an integer, and use that as an (x,y) pair. In this example, that will give you 576 possible outcomes, each of which should be equally likely. But if consecutive permutations are correlated, they won't appear that way.
User avatar
Cosmologicon
 
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA

Re: Test for randomness of a permutation

Postby McHell » Sat Apr 26, 2008 6:01 pm UTC

Except for testing a single position (as mentioned, "e.g. the fifth"), it's also interesting to test consecutive numbers, e.g. "is a 1 followed by 1, 2, 3 en 4 with the same probability?".

This is for example famously the trick of Rupert Sheldrake to convince you that people can sense whether they're being observed: he gives a sequence of 1/0 (watch/don't) numbers that indeed neatly average .5, but a 0 follows a 1 more than 50% (so "say the opposite of what the last result was" is a strategy that gives you a "supernatural" score, and that people quickly yet subconsciously pick up; humans are pattern spotters, so they see Jesus in crisps, pancakes and clouds).
User avatar
McHell
 
Posts: 318
Joined: Fri Jun 22, 2007 12:52 pm UTC
Location: Ellowen Deeowen

Re: Test for randomness of a permutation

Postby Cosmologicon » Sat Apr 26, 2008 9:29 pm UTC

McHell wrote:This is for example famously the trick of Rupert Sheldrake to convince you that people can sense whether they're being observed: he gives a sequence of 1/0 (watch/don't) numbers that indeed neatly average .5, but a 0 follows a 1 more than 50% (so "say the opposite of what the last result was" is a strategy that gives you a "supernatural" score, and that people quickly yet subconsciously pick up; humans are pattern spotters, so they see Jesus in crisps, pancakes and clouds).

Hmmm, maybe that's the right conclusion to draw from that experiment, but it's not the one I would draw at first. When people are asked to generate sequences of random bits, they tend to avoid strings of consecutive identical bits too often. So maybe they're really just trying to guess randomly and doing a bad job, rather than picking up on the pattern in the data. I wonder, in that experiment, whether people's guesses significantly improve as the experiment proceeds, or whether they do equally well when the pattern is different (say consecutive bits are positively rather than negatively correlated).
User avatar
Cosmologicon
 
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA

Re: Test for randomness of a permutation

Postby dosboot » Sun Apr 27, 2008 3:36 am UTC

McHell wrote:This is for example famously the trick of Rupert Sheldrake to convince you that people can sense whether they're being observed: he gives a sequence of 1/0 (watch/don't) numbers that indeed neatly average .5, but a 0 follows a 1 more than 50% (so "say the opposite of what the last result was" is a strategy that gives you a "supernatural" score, and that people quickly yet subconsciously pick up; humans are pattern spotters, so they see Jesus in crisps, pancakes and clouds).


What?
dosboot
 
Posts: 143
Joined: Sun Jul 01, 2007 5:26 am UTC

Re: Test for randomness of a permutation

Postby spdqbr » Thu May 01, 2008 2:29 pm UTC

I have completed my preliminary analysis and posted it here. I shall recreate the post below. I'm eager to hear suggestions and corrections!

Post:

I am NOT a statastician, but I do have a strong math background. If
you notice any errors in my reasoning or methodology, please tell me.

After busting out the stats book and talking to some of the smart folk
at the xkcd message boards, I developed a rudimentary test for
comparing the effectiveness of scramblers. I have since conducted a
few experiments to compare the WCA megaminx scrambler and a scrambler
which behaves a little differently. (Also tested a standard 3x3x3
scrambler). I will explain the methodology first, so if you just want
the results, skip to the end.

The test I conducted was the simplest I could imagine, I applied
scrambles to the puzzle and kept track of how often each color landed
in each position. The assumption: Given a scramble algorithm
generator that generates an n move scrambling algorithms, if we take a
large number of solved puzzles and apply those algorithms, each
position should end up with each color a roughly equal number of times.

That is if an n move scramble from a generator truly approximates
random, all colors should have equal probability of showing up in all
locations. Essentially this is a test for how flat the distribution
of colors over locations is.

Methodology: Apply many scrambles to a cube and track how often each
color shows up in each position. The standard deviation of this list
should tell us approximately how well the scrambles approximate true
random.
So a list would look like this for 10 scrambles on a cube:
Position | R O G B Y W
0 | 3 2 1 2 2 0
1 | 4 1 4 0 0 1
....
47 | 1 1 2 1 3 2

Ignore the position column and take the standard deviation of the
rest. Centers are ignored as well since they are always the same
after scrambling. On the megaminx, after a scramble was applied, the
puzzle was reoriented so that the same center color was on top and the
same was on the front face every time, this prevents puzzle rotations
skewing the results.

The expected standard deviations which are used as a baseline were NOT
calculated directly, as I could not figure out how. Instead, they
were taken from an average of very long scramble algorithms which were
presumed to be random based on the data at hand. This bugs me, so if
you can figure out how to directly calculate the expected stdDev,
please let me know.

On to the results:
Each of these cases is conducted with 1 million (10^6) trials. Turns
is the number of non-puzzle rotating turns (except in the WCA megaminx
scrambler case, where puzzle rotations are counted). StdDev is the
observed standard deviation. Expected std dev is the standard
deviation which a truly random scramble generator should give.
Confidence is the % confidence that this scrambler / length
combination approximates true random in the long term (essentially the
ratio of expected stdDev to observed.) The standard practice I
believe is to take 95% confidence as the threshold for rejecting the
null hypotheses that sigma = s. Thus if the confidence is less than
95%, by convention we can assume the scramble is not truly random. In
practice, I would be willing to go as low as 93% or so. The custom
3x3x3 and megaminx scramblers are the same as from the excel sheet
generator I posted a few days ago.

3x3x3 Cube, generic scrambler (avoids redundant turns, etc):
Code: Select all
Turns | Std Dev | Expected Std Dev | Confidence
1 |264953.60| 360 | 0.1%
10 | 26320.07| 360 | 1.4%
20 | 4274.47| 360 | 8.4%
30 | 794.28| 360 | 45.3%
35 | 514.75| 360 | 69.9%
40 | 387.39| 360 | 92.9%
45 | 347.40| 360 | 96.5%
50 | 341.04| 360 | 94.7%
75 | 350.58| 360 | 97.4%
100 | 372.78| 360 | 96.6%
500 | 347.09| 360 | 96.4%
1000 | 355.14| 360 | 98.7%


When a range for the length was used, the results were pretty
miserable. I have been converted to an advocate for fixed length
scrambles. when allowed to range from 30-40 moves, the CI was only 73.1%!

Based on these results my scrambles for practice will always be at
least 40 moves, and I'd rather use 45.


On to the megaminx. It should be noted that the entirety of the
testing I did was in Java, and as such I had to modify the code from
the wca scrambler to java code. I'm not 100% familiar with
javascript, but I do think that my conversion is accurate. All code
used in this project is available on request.

Megaminx:
WCA Scrambler
Code: Select all
Turns | Std Dev | Expected Std Dev | Confidence
10 |108483.94| 279 | 0.3%
50 | 21986.84| 279 | 0.9%
70 | 12559.95| 279 | 1.7% *official scramble length
100 | 5546.20| 279 | 5.0%
150 | 1451.23| 279 | 19.2%
200 | 469.90| 279 | 59.4%
210 | 398.26| 279 | 70.1%
220 | 351.96| 279 | 79.3%
230 | 312.99| 279 | 89.2%
240 | 307.22| 279 | 90.9%
250 | 294.32| 279 | 94.8%
260 | 285.37| 279 | 97.8%
270 | 280.47| 279 | 99.5%
300 | 278.30| 279 | 99.7%
400 | 275.66| 279 | 98.7%
500 | 269.56| 279 | 96.6%
1000 | 264.62| 279 | 94.8%

This is the heart of why I'm posting. Based on this analysis the
official wca scrambler does not appear to be random until you reach
250 turns or more. And the official scramble length of 70 turns gives
a feeble 1.7% confidence of randomness.

Now lets examine a different scramble generator the big difference is
that puzzle rotations are randomly interspersed and do not count
against the move count. So a 10 move scramble may in fact be 15 moves
long. As such, for a scramble of length n, there will be at least
n/10 more non-puzzle rotating moves than in an n move wca scramble.
So an 80 move scramble here should only be compared to 88 or more move
wca scrambles. Also 1/5 twists are allowed as opposed to just 2/5:
Code: Select all
Turns | Std Dev | Expected Std Dev | Confidence
10 | 91955.36| 279 | 0.3%
50 | 5529.65| 279 | 5.0%
70 | 1572.39| 279 | 17.8%
100 | 380.54| 279 | 73.4%
110 | 315.88| 279 | 88.4%
115 | 287.75| 279 | 97.0%
120 | 291.12| 279 | 95.9%
125 | 279.61| 279 | 99.8%
150 | 273.86| 279 | 98.1%
200 | 282.68| 279 | 98.8%
500 | 279.16| 279 |100.0%
1000 | 286.71| 279 | 97.4%

Clearly this converges toward random much more quickly, in fact around
twice as quickly. I would put 115 moves as the bare minimum and will
probably henceforth use 125 moves myself. I suspect the difference
comes from having so many extra puzzle rotations, not from having 1/5
and 2/5 turns included, though I have not yet tested this.

There you have it. I will probably be posting this to the wca boards
sometime soon, as the megaminx situation concerns me a bit.

I will consider in the future analyzing the wca scramble lengths /
generators for the 4x4x4 and 5x5x5 cubes as well, but writing the
scramble tracking code is mind numbingly tedious and my wife is
complaining about me spending too much time on this ;) . As I
mentioned, if you are better at stats than I am (not hard to do) and
there is any error in my assumptions or methodology, please LET ME
KNOW! All source code used is available upon request.

I'm going to bed now, cheers.
-Daniel
In questions of science, the authority of a thousand is not worth the humble reasoning of a single individual.

Galileo
User avatar
spdqbr
 
Posts: 171
Joined: Sat Mar 08, 2008 1:41 am UTC
Location: A shaker of salt


Return to Mathematics

Who is online

Users browsing this forum: No registered users and 3 guests