Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.
Sign up to join this community
Are you aware of, or have you devised, any practical, simple-to-learn "in-head" algorithms that let humans generate (somewhat "true") random numbers? By "in-head" I mean.. preferably without any external tools or devices. Also, a high output (many random numbers per minute) is desirable.
Asked this on SO but it didn't get much interest. Maybe this is better suited for programmers.
Here is an algorithm from George Marsaglia:
Choose a 2-digit number, say 23, your "seed".
Form a new 2-digit number: the 10's digit plus 6 times the units digit.
The example sequence is 23 --> 20 --> 02 --> 12 --> 13 --> 19 --> 55 --> 35 --> ...
and its period is the order of the multiplier, 6, in the group of residues relatively prime to the modulus, 10. (59 in this case).
The "random digits" are the units digits of the 2-digit numbers, ie, 3,0,2,2,3,9,5,... the sequence mod 10. The arithmetic is simple enough to carry out in your head.
Check out this article on Geomancy. Specifically the section on generating Geomantic charts. It involves a pseudo-random number generating technique using binary digits and some simple recursive calculation. It seems like you could do this in your head fairly easily (though a piece of paper would help).
Disclaimer: I haven't tried it myself; when I need a sufficiently random number, I either get some output from /dev/random, use rand in whatever language I have handy, or roll my trusty d20.
If you're a math prodigy, the Middle-square method is a pretty computationally light, if noticeably unreliable method.
I think a reasonable assumption is that you have to rely on the vast amount of verbal information you store in your brain. The source can be anything, song lyrics, poems, Monty Python sketches, but it has to be something you know by heart.
Then you have to select a fairly random part of it eliminating unconscious bias as much as possible. A way to do this for example would be to select a song, pick a number k between 10 and 20 and then find the kth letter in its lyrics.
Obviously this won't give you a uniform distribution in itself, as the frequency of letters is different, but it's a random letter nevertheless, or at least as close to it as I believe is possible without an external source.
Update: By the way, when people are asked to write a random sequence of say coin tosses, the most common mistake by far is to make your sequence "too random": runs of identical results will be too short, which a simple run length analysis will reveal. This method is mainly aimed at avoiding this trap. Of course other anomalies might arise from the shadow of this run length bias, but you'd need proper experiments to find them. Somewhat ironically, an algorithm for generating random numbers by thinking alone cannot be found by thinking alone.
I do this if I need a random number that's a factor of 60 (seconds). Take the appropriate modulo of whatever time it is. 4:17:23 PM, simulating a die roll, becomes 5.
Excellent question. I fear that a good answer may prove very difficult.
But as a start, it’s quite easy to generate “true” randomness when two people are involved: simply let one of the people count silently in their head modulus some number, and the other say “stop” after an arbitrary interval. Afterwards, this number can be transformed into other distributions using standard methods.
To make this method robust, the modulus mustn’t be too large, otherwise there will be a strong bias against small numbers. I’d really be interested to see if there exists any work analyzing the stochastic properties of this method.
This is a complex question; I'll try and explain a bit without wandering too far off into the weeds.
First, we have to ask "what is true randomness"? Such discussions quickly degenerate into philosophical waters, but the gist is this: "is the universe truly random"? In other words, if you quantize time and matter, can you compute the next state of the universe from the current one? If yes, then the universe is deterministic and there is no true randomness (see what I mean about "philosophical"?)
Because "true randomness" is difficult to define, we often settle for "pseudorandomness." This is generally required when generating "random" numbers on a computer, of course.
The simplest pseudorandom number generator would be something like Dilbert's famous "9.. 9.. 9.." algorithm. But intuitively it doesn't seem very good (which of course is the joke). Statisticians have developed a whole host of tests to say whether a sequence of purportedly random outputs are "good". Start with the wikipedia page for "chi squared test" and you could spend an afternoon just reading about these tests.
A simple computer algorithm like a "linear congruential generator" produces numbers good enough for a chi-squared test (you still need to "seed" this algorithm from something, however).
The next step up in "goodness" is "cryptographically strong randomness" which means that given a sequence a1, a2, ... you cannot predict the next number in the sequence with "reasonable probability" unless you use a lot of computation. These numbers are sometimes called "computationally pseudorandom." One common way to obtain such a sequence is via a "hash chain" like this: a1 = SHA512(a2), a2=SHA512(a3), ... Since we believe (based on experience, not mathematical proof) that SHA512 is computationally hard-to-invert, we believe that a2 is "impossible" to predict given just a1.
So now the question arises, what's the best thing humans can do under the rules stipulated in your question? Humans are notoriously bad at generating randomness; there used to be a web site that would have you attempt to generate coin flips by "randomly" typing H, T, T, H, H, T, T, etc. as if you were flipping a coin (but you do it in your head). After a while, the web site would start to predict your flips better than 50% of the time (using a Hidden Markov Model). We are just bad at this.
There are ways to improve the situation using various mixing techniques that are probably doable in your head. And there are even applications I could dream up for why you might want this (political prisoner wants to encrypt a message to outside allies). But I think this post is long enough. :)
The very reason for the proliferation of tool-based RNGs is that a good in-head algorithm for random number generation is yet to be developed.
Fortunately portable random number generators - including coins for the flopping, dice (with various numbers of facets) for rolling, cards for the picking and straws for drawing - are relatively easy to obtain at low cost. Moreover, for the technophiles amongst us, there are some rather good simulations of these tools available for most mobile platforms.
I would heartily recommend any of these over any meat-ware alternative.
Highly randomised, large quantity per minute and generated by humans? Not gonna happen
The main problems you're going to run up against are
This led a lot of cryptographers to abandon "in-head" techniques in favour of external processes that were random because it was just too simple to work out patterns based on "in-head" numbers.
Off-topic but interesting
While it's not a mechanism for generating random numbers in your head, the Solitaire algorithm (as portrayed in Neal Stephenson's Cryptonomicon) demonstrates how difficult it is to use random numbers for cryptographic purposes. It requires only a pack of ordinary playing cards to create a reasonably secure output but the method to do is quite intricate.
I'm genuinely curious about anything that people might have come up with on this problem.
Please step away from the desk and go to Las Vegas.
Mankind has dozens of randomizing procedures. You can see all of them in Las Vegas.
You have spinning circles. You have tumbling cubes. And you have shuffled tokens. They all work marvellously well.
Cubes are perhaps the oldest. Apparently there were elongated 4-sided sticks used at one point. Symmetric cubic knucklebones of sheep were popular for millennia. We've been using those kinds of randomizers since -- probably -- about the same time we developed language.
http://itunes.apple.com/us/app/motionx-dice/id287509231?mt=8
"Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin”
--- John von Neumann
I can't think of any. In fact I would expect that anything you came up with would have so many biases in it that it would be worthless.
If I need random numbers I generally roll dice.
Are you asking for an LCM you can do in your head? Note that the idea that this is better than dice remains absurd.
However, this is as random as any finite, definite and effective algorithm can possibly be.
http://www.vias.org/simulations/simusoft_lincong.html
http://www1.i2r.a-star.edu.sg/~knandakumar/nrg/Tms/Probability/Probgenerator.htm
U_{k+1} = ( a \times U_k + b ) mod (m + 1).
It's easier to see what this is doing if we pick small values a=5, b=1, and m=7. You should be able to do that in your head.
