How many non-random sequences...

MathsNewbie

New member
Joined
Nov 12, 2015
Messages
4
If I have a sequence of positive integers N, in the range to 0 to R, then I have (R+1)^N possible sequences. Is there any way for me to estimate home many of these sequences would be non-random for any given value of N and R?
 
If I have a sequence of positive integers N, in the range to 0 to R, then I have (R+1)^N possible sequences. Is there any way for me to estimate home many of these sequences would be non-random for any given value of N and R?
How are you defining "non-random"? Thank you! ;)
 
I guess "non-random" in the sense that the sequences would fail to pass known tests for statistical randomness as defined say by...

https://en.wikipedia.org/wiki/Statistical_randomness

Does this work?
I dunno. How far have you gotten on this? (Note: A sequence can be "random", in the sense of "having been generated by a random process, such as coin-tossing or dice-throwing"; while at the same time not "seeming" random to the observer, such as an odd "streak" of sevens when tossing two fair dice. So your book's specific definitions and methods will be important in answering this exercise.) ;)
 
I dunno. How far have you gotten on this? (Note: A sequence can be "random", in the sense of "having been generated by a random process, such as coin-tossing or dice-throwing"; while at the same time not "seeming" random to the observer, such as an odd "streak" of sevens when tossing two fair dice. So your book's specific definitions and methods will be important in answering this exercise.) ;)

I don't know if there is any answer to this question, theoretically... other than testing each permutation, which will be impossible for large values of R and N... the most contemporary test for randomness I could find is a collection of ad-hoc tests, https://en.wikipedia.org/wiki/Diehard_tests, which no doubt work... I've tried to 'formalise' the question a bit more... not sure about the notation though... captured in the picture below...

attachment.php
 

Attachments

  • RandomPermutations.jpg
    RandomPermutations.jpg
    85.7 KB · Views: 21
Last edited:
It's pretty much a given that your question has no solution since it's not calculable whether a set of numbers would pass or fail a randomization test. If it were, there'd be no need for such testing, you could predict the outcomes.
Perhaps a more useful vehicle would be to define a few, fairly simple sets of "this isn't right" that are determinable in some way. For instance, you could look at the number of sequences which have two or more consecutive numbers. Not sure if it's possible to work out what the probability is there, but it seems a far more tractable problem than genuine randomness. After that you might figure out the odds on the list taking up any particular set of rules generating a non-random pattern and remove that as well. I think that's as close as you could come.
 
It's pretty much a given that your question has no solution since it's not calculable whether a set of numbers would pass or fail a randomization test. If it were, there'd be no need for such testing, you could predict the outcomes. Perhaps a more useful vehicle would be to define a few, fairly simple sets of "this isn't right" that are determinable in some way. For instance, you could look at the number of sequences which have two or more consecutive numbers. Not sure if it's possible to work out what the probability is there, but it seems a far more tractable problem than genuine randomness. After that you might figure out the odds on the list taking up any particular set of rules generating a non-random pattern and remove that as well. I think that's as close as you could come.
Thanks for the reply. I'm now wondering if it would make sense to run a simulation with say R set to 1, and increasing N incrementally from 1 by 1 until some Large_N value is reached. Each simulation would return a count, stringing the counts together would give a sequence of counts. I've no idea what the progression would look like, and might be a random sequence itself... and I'm not sure how far N would go until I run out of processor power, with R = 1 then (1+1) to the power of say 22 is already starting to get into a large number of permutations... I'm wondering... let's say a sequence of N=8 numbers either 1 or 0 yields 20 random sequences, would N=9 roughly double that number to say 40 or less? I guess the above simulation might show something like this, and testing up to say N=20 might be doable?
 
Last edited:
Top