Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

closed as off-topic by MichaelT, GlenH7, gnat, Bart van Ingen Schenau, Martijn Pieters Feb 17 at 22:11

  • This question does not appear to be about software development within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

7  
@S.Lott I don't think it's absurd at all. Unpractical? Why, of course. Absurd? Certainly not. And even if it was, absurdity can pave the way for new, useful thoughts. –  biziclop Feb 18 '11 at 11:28
19  
9....9....9....9 - You can't prove its not random. –  Glenn Nelson Feb 18 '11 at 11:41
13  
S.Lott: The idea of a easzy to calculate pseudo-random number generator is not absurd at all. I think the OP wants a way to avoid the human bias here.... –  Jens Feb 18 '11 at 12:55
7  
I find it funny (and at the same time slightly depressing) how many people seem to appreciate an argument of ignorance. "I can't imagine it, therefore it cannot exist", or answers that are completely missing the point. –  biziclop Feb 18 '11 at 12:58
4  
This question appears to be off-topic because it is about the cognitive ability of an individual and not programming. –  MichaelT Feb 12 at 3:36
show 21 more comments

11 Answers

up vote 30 down vote accepted

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.

share|improve this answer
    
This sounds really good. –  biziclop Feb 18 '11 at 22:32
2  
+1 Nice: that's what was asked for. –  Norman Gray Feb 18 '11 at 22:53
3  
This may not be a problem for a particular person's needs, but this only gives you 90 different streams. –  compman Feb 19 '11 at 3:59
5  
79, 79, 79, 79, 79, 79, 79, 79, 79, 79, oh noes! I assume you're supposed to stay <= 60, which works out well because you can use the clock for a seed if you don't have one. –  eds Feb 19 '11 at 18:52
3  
@eds Um, what? 79 -> 61 -> 15 -> ... –  Izkata Jul 8 at 19:05
show 2 more comments

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.

share|improve this answer
add comment

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

share|improve this answer
1  
+1 for "symmetric cubic knucklebones" - made I larf. –  Gary Rowe Feb 18 '11 at 12:06
6  
Downvoted - I'm not interested in external tools for generating random numbers, but rather in-head algorithms that can rely on memories or stimulus to generate truly random numbers. –  Magnus Wolffelt Feb 18 '11 at 12:46
2  
you can't roll dice in your head –  jk. Feb 18 '11 at 12:51
1  
@jk01: Correct. You can't do random in your head, either. –  S.Lott Feb 18 '11 at 13:11
    
@S.Lott - I think what you mean to say is "A typical human can't generate consistently random numbers in their head at high speed using the naive method and no external tools". –  Inaimathi Feb 18 '11 at 16:44
show 1 more comment

Highly randomised, large quantity per minute and generated by humans? Not gonna happen

The main problems you're going to run up against are

  • People get bored quickly so patterns will occur quickly
  • The human brain has a lot of structure devoted to pattern recognition/creation so you're going to have to defeat that
  • Truly random numbers contain repeats which humans try to avoid
  • Humans aren't good with large numbers

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.

share|improve this answer
    
I think this doesn´t answer the question. The 4 points of your answer only apply if people tried to find random numbers without an algorithm. I think the OP is aware of that and this is the reason why he asks for an algorithm that people can do in their heads and give good results, i.e. dont suffer the problems mentioned in your answer. –  FabianB Feb 19 '11 at 14:23
add comment

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.

share|improve this answer
add comment

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. :)

share|improve this answer
    
Although whether a truly random physical process exists is open to debate (although experiments involving the EPR paradox suggest a positive answer), a theoretical definition of a random sequence does exist, based on Kolmogorov complexity. –  biziclop Feb 18 '11 at 21:19
add comment

Sample your watch.

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.

share|improve this answer
    
And for a large number per minute? –  Gary Rowe Feb 18 '11 at 16:20
    
Not sure I follow. You're saying make the pool of numbers 3600 by including minutes? I guess, but the larger the number the less random it would be? Like you couldn't rapidly take samples as easily. –  Mark Canlas Feb 18 '11 at 16:32
1  
@Gary Rowe This criteria has to be scrapped I'm afraid, simply because regardless of the method used, the human brain is simply too slow. –  biziclop Feb 18 '11 at 21:24
    
Sorry, I was just wondering how your approach works if you need more than 60 numbers per minute. In hindsight, asking a human brain to produce that many numbers per minute is going to max it out anyway, so don't worry about it. –  Gary Rowe Feb 18 '11 at 21:50
    
@biziclop No problems. Looks like I had a comment collision while considering the situation with @Mark's approach. –  Gary Rowe Feb 18 '11 at 21:53
add comment

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.

share|improve this answer
3  
+1 I think that this is the first serious answer to this question. A little sad. –  Jens Feb 18 '11 at 13:00
6  
+1 for "roll my trusty d20." –  Ben Feb 18 '11 at 14:01
    
@Magnus Wolffelt - I remembered it being mentioned in a TED talk by Ron Eglash about the cultural significance of fractal geometry in Africa; "Bamana Sand Divination". It's fairly interesting, though I still have no idea what you'd use this technique for now that we no longer need soothsayers. ted.com/talks/ron_eglash_on_african_fractals.html –  Inaimathi Feb 18 '11 at 14:41
1  
As far as I can see, that geomantic method simply allows you to 'improve' (I suppose that 'debias' would be a better term) a source of randomness. Not to be sneezed at, but not really what the OP was looking for. Which is not to say it's not pretty.... –  Norman Gray Feb 18 '11 at 22:52
    
@Norman Gray - Human brains can come up with biased arbitrary numbers by default. –  Inaimathi Feb 19 '11 at 1:43
show 2 more comments

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Even then I would expect that you would be biased in a number of subtle ways. (IE tending to pick the same group of songs) –  Zachary K Feb 18 '11 at 11:37
    
@Zachary K Without a doubt, but then you'd also have to pick a number, which spreads it a bit. Although bias could never be eliminated, this method almost certainly prevents you from knowing which letter you'll pick (although with time you're bound to memorise some). –  biziclop Feb 18 '11 at 11:49
    
Eini mini miny moe, as we used to do as kids. –  Zachary K Feb 18 '11 at 12:46
1  
"pick a number k between 10 and 20". 17. The least random number. –  S.Lott Feb 18 '11 at 13:16
    
@S.Lott It doesn't matter how random this number is. The only reason you need it is that you tend to remember the first few letters of things more easily. –  biziclop Feb 18 '11 at 13:50
show 2 more comments

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.

share|improve this answer
    
And these physical devices really do have an unpredictable nature to them, so in a sense they are more random than the best computer algoithms. –  Omega Centauri Feb 18 '11 at 17:15
add comment

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