Re^2: Shuffling CODONS

Maybe this explains it better?

The following program uses this heavily biased PRNG:

sub badRand($) { rand() < 0.5 ? 0 : rand( $_[0] ) }
[download]

which is designed to produce 0, 50% of the time. That means that when asked for numbers 0-9, it produces '0', 10 times more often than any of the other values:

[549637, 50008, 50261, 50195, 50365, 49871, 50000, 49692, 49768, 50203
+]
[download]

And when asked for 0..23, produces '0' 25 times more often than any other number:

[ 521654, 20747, 20716, 20614, 20914, 20740, 20906, 20580, 20625, 2107
+7, 20736, 20912, 20835, 20820, 20958, 20818, 20866, 20818, 20969, 206
+46, 20749, 20953, 20454, 20893, ]
[download]

But when that biased PRNG used within a standard Fisher Yates shuffle, the shuffles are fair, no matter how many times you run it:

{
  ABCD => 67436,
  ABDC => 67742,
  ACBD => 67990,
  ACDB => 68277,
  ADBC => 68018,
  ADCB => 67846,
  BACD => 67766,
  BADC => 67859,
  BCAD => 68598,
  BCDA => 68919,
  BDAC => 69172,
  BDCA => 67870,
  CABD => 67755,
  CADB => 67192,
  CBAD => 67657,
  CBDA => 67731,
  CDAB => 67793,
  CDBA => 67680,
  DABC => 67755,
  DACB => 68016,
  DBAC => 68098,
  DBCA => 67988,
  DCAB => 67666,
  DCBA => 68408,
}
[download]

The test code:

#! perl -slw
use strict;
use Data::Dump qw[ pp ];

sub badRand($) { rand() < 0.5 ? 0 : rand( $_[0] ) }

sub shuffle { $a = $_ + badRand( @_ - $_ ), $b = $_[$_], $_[$_] = $_[$
+a], $_[$a] = $b for 0 .. $#_; return @_; }

my @rands; ++$rands[ badRand( 10 ) ] for 1 .. 1e6; pp \@rands; <STDIN>
+;

my @vals = ( 'A' .. 'D' );
my %tests;
my $c = 0;
while( 1 ) {
    ++$tests{ join '', shuffle( @vals ) };
    unless( ++$c % 576 ) {
        system 'cls';
        pp \%tests;
    }
}

__END__
c:\test> junk77
[549637, 50008, 50261, 50195, 50365, 49871, 50000, 49692, 49768, 50203
+]
{
  ABCD => 67436,
  ABDC => 67742,
  ACBD => 67990,
  ACDB => 68277,
  ADBC => 68018,
  ADCB => 67846,
  BACD => 67766,
  BADC => 67859,
  BCAD => 68598,
  BCDA => 68919,
  BDAC => 69172,
  BDCA => 67870,
  CABD => 67755,
  CADB => 67192,
  CBAD => 67657,
  CBDA => 67731,
  CDAB => 67793,
  CDBA => 67680,
  DABC => 67755,
  DACB => 68016,
  DBAC => 68098,
  DBCA => 67988,
  DCAB => 67666,
  DCBA => 68408,
}
[download]

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.

In the absence of evidence, opinion is indistinguishable from prejudice. Suck that fhit

Comment on Re^2: Shuffling CODONS Select or Download Code

Replies are listed 'Best First'.
Re^3: Shuffling CODONS by bliako (Abbot) on Jun 09, 2018 at 22:47 UTC
But when that biased PRNG used within a standard Fisher Yates shuffle, the shuffles are fair, no matter how many times you run it I am not convinced. A statistical test for assessing statistical fairness is chi-square: throw a dice a million times and feed chi-square with the counts for each outcome: `'1' => ..., '2' => ... , ... '6' => ...`. It will tell you whether it thinks the dice is fair or not. So I run your test code with 3 rand-subs: `use Math::Random::MT; my $mt = Math::Random::MT->new(); sub badRand($) { rand() < 0.5 ? 0 : rand( $_[0] ) } sub goodRand($) { rand($_[0]) } sub bestRand($) { $mt->rand($_[0]) }` [download] Then I run the chi-squared test (Statistics::ChiSquare) on the counts of the shuffle (re: the output of your test code). This is the result: bad_shuffle : There's a <1% chance that this data is random. good_shuffle : There's a >25% chance, and a <50% chance, that this data is random. best_shuffle : There's a >25% chance, and a <50% chance, that this data is random. or bad_shuffle : There's a <1% chance that this data is random. best_shuffle : There's a >50% chance, and a <75% chance, that this data is random. good_shuffle : There's a >10% chance, and a <25% chance, that this data is random. or bad_shuffle : There's a <1% chance that this data is random. best_shuffle : There's a >25% chance, and a <50% chance, that this data is random. good_shuffle : There's a >50% chance, and a <75% chance, that this data is random. The above test consistently rates "bad_shuffle" based on badRand() as producing data with less than 1% chance of being random. It is undecided, let's say, which is best for this particular shuffle: Mersenne or Perl. The results your test code produced may look fair but they aint according to this particular test - it very much depends on use-case (see end of post). Although you may be right with your hunch that Mersenne may not offer anything more than perl's standard rand() for FY shuffle but hey let's not exaggerate with badRand()! :) This is my test code: Read more... (2 kB) sidenote: A particular shuffle may be appropriate for a particular situation. Such as? poker and co where patterns in the shuffled cards may influence the game. The shuffled cards must be tested for the number of patterns they contain. medical trials : a list of "same-category" (e.g. all healthy) patients must be shuffled in order to then separate them to different groups for trial treatment. related to #2 : I have a group with certain average properties. Then I group them randomly, after a shuffle, does each group has on average the same properties? Or have I grouped together the tall boys and put in another group the short boys, because my shuffle algorithm was not suitable?	[reply] [d/l] [select]
Re^4: Shuffling CODONS by BrowserUk (Patriarch) on Jun 10, 2018 at 08:48 UTC
Okay. I ran your code again and got: `C:\test>junk123 best_shuffle : There's a <1% chance that this data is random. good_shuffle : There's a >50% chance, and a <75% chance, that this dat +a is random. bad_shuffle : There's a >5% chance, and a <10% chance, that this data +is random.` [download] That's not right! So, I though about my example code and looked at what it was intended to demonstrate. That despite the use of a completely bogus rand() function, a Fisher-Yates shuffle would still operate; and produce results: That all possible shuffles of the data were being produced. I chose to shuffle 4 values because the 24 possible results fit on a screen and are simple to verify manually. That they were produced with (approximately) the same frequency. Ie. The number of times each possible shuffle was produced were approximately equal and approximately 1/24th of the total runs. In that respect, it served its purpose. But, if you are going to formally test a shuffle, using only 4 value arrays and 1e6 iterations probably isn't the ideal scenario to test. To that end I tweaked your code to allow me to adjust both parameters from the command line: `our $NUMTESTS //= 1e6; our $ASIZE //= 4; ... my @vals = ( 1..$ASIZE );` [download] And, given that Chi² is generally used to determine whether a (smallish) sample is representative of a large and thus unknown population, I tried using a (moderately) larger array: C:\test>junk123 -ASIZE=40 -N=1e5 best_shuffle : I can't handle 100000 choices without a better table. good_shuffle : I can't handle 100000 choices without a better table. bad_shuffle : I can't handle 100000 choices without a better table. C:\test>junk123 -ASIZE=40 -N=1e4 best_shuffle : I can't handle 10000 choices without a better table. good_shuffle : I can't handle 10000 choices without a better table. C:\test>junk123 -ASIZE=40 -N=1e3 best_shuffle : I can't handle 1000 choices without a better table. good_shuffle : I can't handle 1000 choices without a better table. bad_shuffle : I can't handle 1000 choices without a better table. C:\test>junk123 -ASIZE=40 -N=1e2 best_shuffle : There's a >99.5% chance, and a <100% chance, that this +data is random. good_shuffle : There's a >99.5% chance, and a <100% chance, that this +data is random. bad_shuffle : There's a >99.5% chance, and a <100% chance, that this d +ata is random. [download] And once I found a sample size of that larger array that the module could handle, did a few "identical" runs: C:\test>junk123 -ASIZE=40 -N=1e2 best_shuffle : There's a <1% chance that this data is random. good_shuffle : There's a >50% chance, and a <75% chance, that this dat +a is random. bad_shuffle : There's a >5% chance, and a <10% chance, that this data +is random. C:\test>junk123 -ASIZE=40 -N=1e2 best_shuffle : There's a >50% chance, and a <75% chance, that this dat +a is random. good_shuffle : There's a >50% chance, and a <75% chance, that this dat +a is random. bad_shuffle : There's a <1% chance that this data is random. C:\test>junk123 -ASIZE=40 -N=1e2 best_shuffle : There's a >50% chance, and a <75% chance, that this dat +a is random. good_shuffle : There's a >50% chance, and a <75% chance, that this dat +a is random. bad_shuffle : There's a >10% chance, and a <25% chance, that this data + is random. [download] Hm. Not exactly confidence inspiring. Let's try some middle ground: C:\test>junk123 -ASIZE=11 -N=1e5 best_shuffle : There's a >75% chance, and a <90% chance, that this dat +a is random. good_shuffle : There's a >75% chance, and a <90% chance, that this dat +a is random. bad_shuffle : There's a <1% chance that this data is random. C:\test>junk123 -ASIZE=11 -N=1e5 best_shuffle : There's a >25% chance, and a <50% chance, that this dat +a is random. good_shuffle : There's a >1% chance, and a <5% chance, that this data +is random. bad_shuffle : There's a <1% chance that this data is random. C:\test>junk123 -ASIZE=11 -N=1e4 best_shuffle : There's a >75% chance, and a <90% chance, that this dat +a is random. good_shuffle : There's a >1% chance, and a <5% chance, that this data +is random. bad_shuffle : There's a >75% chance, and a <90% chance, that this data + is random. C:\test>junk123 -ASIZE=11 -N=1e4 best_shuffle : There's a >50% chance, and a <75% chance, that this dat +a is random. good_shuffle : There's a >50% chance, and a <75% chance, that this dat +a is random. bad_shuffle : There's a <1% chance that this data is random. C:\test>junk123 -ASIZE=11 -N=1e4 best_shuffle : There's a >10% chance, and a <25% chance, that this dat +a is random. good_shuffle : There's a >5% chance, and a <10% chance, that this data + is random. bad_shuffle : There's a <1% chance that this data is random. C:\test>junk123 -ASIZE=11 -N=1e2 best_shuffle : There's a >10% chance, and a <25% chance, that this dat +a is random. good_shuffle : There's a >75% chance, and a <90% chance, that this dat +a is random. bad_shuffle : There's a <1% chance that this data is random. C:\test>junk123 -ASIZE=11 -N=1e2 best_shuffle : There's a >1% chance, and a <5% chance, that this data +is random. good_shuffle : There's a >90% chance, and a <95% chance, that this dat +a is random. bad_shuffle : There's a >1% chance, and a <5% chance, that this data i +s random. [download] Sure, it's guessing that the known, deliberately really bad rand is producing poor results most of the time, but its also making the same guess about the known good rand with surprisingly high frequency. Two possibilities: the test is implemented badly; it is the wrong test for this kind of data. I suspect a little of both is at work here. I'm far from an expert on stats, but I don't believe that Chi² is the right test for the kind of samples this produces; and I cannot see any reference to Yates correction in the module. More later. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity. In the absence of evidence, opinion is indistinguishable from prejudice. Suck that fhit	[reply] [d/l] [select]
Re^5: Shuffling CODONS by bliako (Abbot) on Jun 10, 2018 at 11:41 UTC
I'm far from an expert on stats, but I don't believe that Chi2 is the right test for the kind of samples this produces; and I cannot see any reference to Yates correction in the module. Me neither, far from expert. Beyond chi-squared there are tests for finding a pattern in the shuffled data (I once tried to zip a file and count its compression ration achieved as proportional to how random the sequence is), and monte-carlo-splitting the shuffled array in groups and trying to see if the group's average approaches the total array's average. I will report back chi-squared results using R That despite the use of a completely bogus rand() function, a Fisher-Yates shuffle would still operate; and produce results: That all possible shuffles of the data were being produced. I chose to shuffle 4 values because the 24 possible results fit on a screen and are simple to verify manually. That they were produced with (approximately) the same frequency. Ie. The number of times each possible shuffle was produced were approximately equal and approximately 1/24th of the total runs. In that respect, it served its purpose. But, if you are going to formally test a shuffle, using only 4 value arrays and 1e6 iterations probably isn't the ideal scenario to test. ok	[reply]
Re^6: Last comment (and nail in the coffin of) of S::CS :) by BrowserUk (Patriarch) on Jun 10, 2018 at 13:54 UTC
Re^7: Last comment (and nail in the coffin of) of S::CS :) by bliako (Abbot) on Jun 10, 2018 at 17:59 UTC
Some notes below your chosen depth have not been shown here
Re^6: Shuffling CODONS by BrowserUk (Patriarch) on Jun 10, 2018 at 12:46 UTC
Re^4: Shuffling CODONS by BrowserUk (Patriarch) on Jun 10, 2018 at 07:39 UTC
I am not convinced. A statistical test for assessing statistical fairness is chi-square: Well yes. Chi² is the "standard test" in certain circles; but it needs to be implemented properly; to include Yates' (of Fisher-Yates fame) correction; to be used correctly; I haven't investigated the particular implementation you used, but I did install it so I could run your code. A few times... C:\test>junk123 best_shuffle : There's a >25% chance, and a <50% chance, that this dat +a is random. good_shuffle : There's a >1% chance, and a <5% chance, that this data +is random. bad_shuffle : There's a <1% chance that this data is random. C:\test>junk123 best_shuffle : There's a >75% chance, and a <90% chance, that this dat +a is random. good_shuffle : There's a >25% chance, and a <50% chance, that this dat +a is random. bad_shuffle : There's a >50% chance, and a <75% chance, that this data + is random. C:\test>junk123 best_shuffle : There's a >10% chance, and a <25% chance, that this dat +a is random. good_shuffle : There's a >5% chance, and a <10% chance, that this data + is random. bad_shuffle : There's a >50% chance, and a <75% chance, that this data + is random. [download] In 3 runs, it evaluates the probability that the results from (one of) the best PRNGs available, is actually random, varies between 10% and 90%, whilst that of a deliberately buggered PRNG is between 1% and 75%. Honestly, those 3 sets of results look as good an approximation of random as I can think of. I'll investigate whether it is the way you are using it; the implementation, or the potted interpretations it is producing later, once I've woken properly; but at first glance, I'd have to say "somethings not right". (May be we could feed S::CS its own results and see it it judges itself random :) ) With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity. In the absence of evidence, opinion is indistinguishable from prejudice. Suck that fhit	[reply] [d/l]