Problem 44393. Testing for randomness: uniform distribution of integers

Created by David Verrelli

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>On Cody several problems have been set up asking players to generate one or more 'random' numbers. Usually they are asking for numbers from a uniform distribution function (UDF). However, Test Suites do not always test very carefully to see how 'random' the sequences generated by the submitted codes are. Indeed, rigorous testing of randomness is a sophisticated field of endeavour. (See e.g.</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://en.wikipedia.org/wiki/TestU01\"><w:r><w:t>TestU01</w:t></w:r></w:hyperlink><w:r><w:t> and the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://en.wikipedia.org/wiki/Diehard_tests\"><w:r><w:t>Diehard tests</w:t></w:r></w:hyperlink><w:r><w:t>.)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>MATLAB provides access to several very good pseudo-random number generators. Even these do not generate truly random number sequences — however, they are good enough for most purposes.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Here we will be considering only integer sequences. Your task will be to distinguish those that are 'practically' random — in this case being uniformly distributed — from those that aren't.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You must return:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>the probability of the given sequence being generated (a scalar float); and</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>your assessment of whether the sequence could 'plausibly' have been produced by a true random number generator (a scalar Boolean).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Input sequences will be vectors of various lengths containing only the integers 1, 2, 3 and 4.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Here are a few cases to consider:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>EXAMPLE ONE — Random sequence (UDF)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ Input = [3 4 3 3 4 2 2 2 1 3 2 2 1 3 3 2 4 3 1 2 3 2 1 4 2 1 4 4 4 2 3 1 2 1 2 2 1]\n prob ~ 5.29E-23\n isRandom = true]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>EXAMPLE TWO — Non-uniform distribution</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ Input = [1 3 3 1 1 1 1 3 1 1 4 1 2 1 1 1 1 1 3 1 3]\n % Notice that there are far too many ones, and too few twos and fours.\n prob ~ 9.09E-13\n isRandom = false]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>EXAMPLE THREE —</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.spirit-statement.org/sequence-generation/\"><w:r><w:t>Blocked randomisation</w:t></w:r></w:hyperlink><w:r><w:t> (or 'permuted block randomisation')</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ Input = [1 3 2 4, 1 4 2 3, 3 1 4 2, 2 1 3 4, 1 4 3 2, 3 2 4 1, 4 1 3]\n % Notice that each of the four digits appears in groups of four. In such cases the identity of neighbouring digits is often biased too, although it isn't apparent in the short sequence above. \n prob ~ 5.55E-17\n isRandom = false]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>EXAMPLE FOUR — Repeated pattern</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ Input = [1 3 1 4 2 4 2 3, 1 3 1 4 2 4 2 3, 1 3 1 4 2 4 2 3, 1 3 1 4 2 4 2 3, 1 3 1 4 2]\n % Notice the pattern of eight digits that is repeated. Notice also that the identity of neighbouring digits is biased, as e.g. 4 is only ever followed by 2, and 3 is only ever followed by 1. \n prob ~ 5.29E-23\n isRandom = false]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>EXAMPLE FIVE — Partial repeated sequence, too few runs</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ Input = [1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 1 2 3 1 2 4 1 3 4 2 3 4 1 2 3 4]\n % Notice that the sequence \"1 2 3 4\" is repeated in part or in full. Notice also that the neighbouring digits are biased — e.g. 2 most commonly follows 1, but 2 is never followed by 1 or 2. And finally notice that there are no runs (repeated occurrences of the same numeral). \n prob ~ 5.42E-20\n isRandom = false]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>EXAMPLE SIX — Partially segregated sequence, runs too long</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ Input = [1 1 4 1 1 1 1 1 1 3 3 3 3 1 3 3 3 3 4 4 4 4 2 4 4 4 4 2 2 2 2 2 2 3 2 2]\n % Notice that the sequence unfolds as mostly 1, then mostly 3, then mostly 4, and mostly 2 at the end. Notice also that the neighbouring digits are biased — each number most commonly follows itself. And finally notice that the runs are longer than we would expect from a truly random (UDF) sequence. \n prob ~ 2.12E-22\n isRandom = false]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>As will be apparent, there are various tests that</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>could</w:t></w:r><w:r><w:t> be applied: inspecting occurrence of numerals, pairs of neighbouring numerals, runs of numerals (length of runs, number of runs), repeated sequences, etc. Your job is just to return the correct outputs. You are</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>not</w:t></w:r><w:r><w:t> necessarily required to implement every test.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>Note: the sequences in the examples above were for illustrative purposes; most sequences in the Test Suite are considerably longer.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>See also:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:hyperlink w:docLocation=\"https://www.mathworks.com/matlabcentral/cody/problems/44435\"><w:r><w:t>Problem 44435: \"Testing for randomness: uniform distribution of real numbers (distribution checking)\"</w:t></w:r></w:hyperlink><w:r><w:t> (easier)</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

On Cody several problems have been set up asking players to generate one or more 'random' numbers. Usually they are asking for numbers from a uniform distribution function (UDF). However, Test Suites do not always test very carefully to see how 'random' the sequences generated by the submitted codes are. Indeed, rigorous testing of randomness is a sophisticated field of endeavour. (See e.g. <a href = "https://en.wikipedia.org/wiki/TestU01">TestU01</a> and the <a href = "https://en.wikipedia.org/wiki/Diehard_tests">Diehard tests</a>.)MATLAB provides access to several very good pseudo-random number generators. Even these do not generate truly random number sequences — however, they are good enough for most purposes.Here we will be considering only integer sequences. Your task will be to distinguish those that are 'practically' random — in this case being uniformly distributed — from those that aren't.You must return:<ul><li>the probability of the given sequence being generated (a scalar float); and</li><li>your assessment of whether the sequence could 'plausibly' have been produced by a true random number generator (a scalar Boolean).</li></ul>Input sequences will be vectors of various lengths containing only the integers 1, 2, 3 and 4.Here are a few cases to consider:EXAMPLE ONE — Random sequence (UDF)<pre> Input = [3 4 3 3 4 2 2 2 1 3 2 2 1 3 3 2 4 3 1 2 3 2 1 4 2 1 4 4 4 2 3 1 2 1 2 2 1]
 prob ~ 5.29E-23
 isRandom = true</pre>EXAMPLE TWO — Non-uniform distribution<pre> Input = [1 3 3 1 1 1 1 3 1 1 4 1 2 1 1 1 1 1 3 1 3]
 % Notice that there are far too many ones, and too few twos and fours.
 prob ~ 9.09E-13
 isRandom = false</pre>EXAMPLE THREE — <a href = "http://www.spirit-statement.org/sequence-generation/">Blocked randomisation</a> (or 'permuted block randomisation')<pre> Input = [1 3 2 4, 1 4 2 3, 3 1 4 2, 2 1 3 4, 1 4 3 2, 3 2 4 1, 4 1 3]
 % Notice that each of the four digits appears in groups of four. In such cases the identity of neighbouring digits is often biased too, although it isn't apparent in the short sequence above. 
 prob ~ 5.55E-17
 isRandom = false</pre>EXAMPLE FOUR — Repeated pattern<pre> Input = [1 3 1 4 2 4 2 3, 1 3 1 4 2 4 2 3, 1 3 1 4 2 4 2 3, 1 3 1 4 2 4 2 3, 1 3 1 4 2]
 % Notice the pattern of eight digits that is repeated. Notice also that the identity of neighbouring digits is biased, as e.g. 4 is only ever followed by 2, and 3 is only ever followed by 1. 
 prob ~ 5.29E-23
 isRandom = false</pre>EXAMPLE FIVE — Partial repeated sequence, too few runs<pre> Input = [1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 1 2 3 1 2 4 1 3 4 2 3 4 1 2 3 4]
 % Notice that the sequence "1 2 3 4" is repeated in part or in full. Notice also that the neighbouring digits are biased — e.g. 2 most commonly follows 1, but 2 is never followed by 1 or 2. And finally notice that there are no runs (repeated occurrences of the same numeral). 
 prob ~ 5.42E-20
 isRandom = false</pre>EXAMPLE SIX — Partially segregated sequence, runs too long<pre> Input = [1 1 4 1 1 1 1 1 1 3 3 3 3 1 3 3 3 3 4 4 4 4 2 4 4 4 4 2 2 2 2 2 2 3 2 2]
 % Notice that the sequence unfolds as mostly 1, then mostly 3, then mostly 4, and mostly 2 at the end. Notice also that the neighbouring digits are biased — each number most commonly follows itself. And finally notice that the runs are longer than we would expect from a truly random (UDF) sequence. 
 prob ~ 2.12E-22
 isRandom = false</pre>As will be apparent, there are various tests that could be applied: inspecting occurrence of numerals, pairs of neighbouring numerals, runs of numerals (length of runs, number of runs), repeated sequences, etc. Your job is just to return the correct outputs. You are not necessarily required to implement every test.<tt>Note: the sequences in the examples above were for illustrative purposes; most sequences in the Test Suite are considerably longer.</tt>See also:<ul><li><a href = "https://www.mathworks.com/matlabcentral/cody/problems/44435">Problem 44435: "Testing for randomness: uniform distribution of real numbers (distribution checking)"</a> (easier)</li></ul>

Solve

Solution Stats

8 Solutions
2 Solvers

Last Solution submitted on Nov 30, 2018

Last 200 Solutions

Solution Comments

Solution 1352879

1 Comment

1 Comment

David Verrelli on 3 Dec 2017

The function you are trying to use here is part of the Signal Processing Toolbox, which is not available on Cody. However, you might find another way of implementing your idea in core MATLAB without that specific function.

Problem Recent Solvers2

Problem Tags

random randomness udf

Problem 44393. Testing for randomness: uniform distribution of integers

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers2

Suggested Problems

More from this Author31

Problem Tags

Problem 44393. Testing for randomness: uniform distribution of integers

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers2

Suggested Problems

More from this Author31

Problem Tags

Players