0
$\begingroup$

I am trying to find a type of quasi-random sequence which would guarantee that it could produce all possible sequences of values within the possible value range, while still producing random-seeming results. For example, if the value range was integers between 1 and 100, I would like to find a function which could produce all the values within that range in a random-seeming distribution, but would also, for a set of a certain size, say ten, guarantee that at some point within 100^10 (or possibly more) iterations, it would produce all the possible permutations of groups of ten integers in that range.

I realize that most quasi-random algorithms are designed to avoid such results - so that sequential outputs never occur from sequential inputs. But I am curious if there is a class of them or a way of creating one with this behavior.

$\endgroup$
1
  • $\begingroup$ In fact most quasi-random algorithms would like to have this result. A truly random string will have all sequences of pairs of digits with probability $1$. Quasi-random hopes to do so as well, but may not succeed. The coupon collector result says you should expect to have all sequences of ten numbers from $[1,100]$ on average in $10^{100} \log (10^{100}) \approx 2.3\cdot 10^{102}$ tries. $\endgroup$ Apr 12 '15 at 5:51
0
$\begingroup$

All you need is a normal number. They should be easy to find, because almost all reals are normal. Unfortunately, it is hard to prove any given number is normal unless it is constructed to be so and then it probably won't look "random". The Champernowne constant $0.123456789101112131415...$ fits this. It is known to be normal in base $10$, so if you break it into digit pairs and replace $00$ with $100$ it includes all sequences of ten numbers. $\pi$ is not known to be normal, but "everybody" expects it to be. You could just go far enough out in the decimal expansion that nobody would recognize it and take your numbers from there.

$\endgroup$
2
  • $\begingroup$ Thank you @Ross Millikan, this is a very useful concept for what I'm working on. It would be especially useful to me to find a function which is invertible. Do you know, for example, if there is a normal number for which, given a sequence of numbers, you could compute the index position of those digits in the mantissa? $\endgroup$ Apr 12 '15 at 0:38
  • $\begingroup$ Certainly for the Champernowne constant you can compute the position, but you have the not-random appearance problem. If you pick a "random appearing" permutation of the pairs of digits, you can apply it to the Champernowne constant and have something that looks random to the unsophisticated eye, but you will be able to predict where a particular pair of digits will appear. Someone who guesses what you have done will be able to understand what is happening and predict future digits. $\endgroup$ Apr 12 '15 at 5:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.