[Math] Pen and paper pseudo-random number generator

random

tl;dr

How can I generate pseudo-random numbers using only pen and paper?

  • Uniform distribution (or as close as possible)
  • It's pen writing on paper; can't cut, fold, throw or anything like that
  • I'm expecting some formula or algorithm, but a geometric solution, graph or set theory would be ok, too
  • It's really just pen and paper. No clocks or anything external

Details

I took a test where all questions were to be marked as right or wrong, and while correct answers would be worth two points, an incorrect answer would subtract one point.

With that system, if you guess all questions randomly, your expected score should be something around 25% (50% for the half that you got right, minus 25% for those you got wrong).

While that will be not enough for passing the test, it can make a difference when you use that technique on the questions you have no idea how to answer, or which you have no time for a proper analysis (as responses in blank do not add or subtract anything from the final score), since test scores are used for classification.

That got me thinking on how to generate proper random responses for such a task, when all you have is a pen and paper.

For my specific case, it was a binary matter, so much simpler. But I wondered what about multiple choices, where the response set has five or six alternatives.

One simpler option for binary was to just set 'right for odd questions, wrong for even questions', which should produce the same result (yes?).

But I still think this is an interesting question, and my math skills are not enough for the problem. I'm pretty sure that I'll have to mod some number as the final step for getting the actual option. I also thought about using some check digit algorithm on a less random seed, perhaps reusing the last result somehow as input for the next iteration (but I may end up on a non-randomic sequence by doing that).

math.stackexchange already has some questions on this, like this and this.

Of these the responses, I liked the most were @Aaron Toponce's, @coffeemath's and @vrugtehagel's. However, they do not fit the criteria I put for the question (well, none of them is a formula, in the conventional sense, at least)

Edit 1

The question tile was changed from Yet another pen and paper random number generator question to Pen and paper pseudo-random number generator because, after thinking for a while, I came to the conclusion that you can't generate random numbers with mathematics alone and no clocks or anything external, as the question's restrictions listed.

Given a seed and a formula or algorithm, the end results will always be the same, as mathematics is deterministic by nature.

Some of the solutions I pointed above add the nondeterministic element by selecting a point in a drawing, which is fine, but not what I was looking for.

So, the definition of a pseudo-random number generator in the context of this question becomes:

A formula or algorithm, that, given an initial seed, generates a non-cyclic sequence of digits.

The distribution of the digits in the sequence should be balanced.

Edit 2

I have uploaded to gist the Notebook I used to play with the proposed solutions:

https://gist.github.com/caxcaxcoatl/3d469a9728737e51530add73327f9c9f

All mistakes (code or conceptual) there are my own. The solution authors are mentioned on the respective response sections, but I diverged a bit from each of them on the actual code.

Note: I know this is not StackOverflow, but I think sharing this would be interesting for other like-minded people.

Best Answer

I would use a linear congruential generator. Given a seed $X_n$ it returns $X_{n+1}=aX_n+c \pmod m$ for parameters $a,c,m$. I would then take some low order bits of $X_{n+1}$ as the random number. The calculation is not much even with pen and paper. You could use a relatively small $m$ because you don't need many bits. You would like $m$ to be prime, but if it has some large factors that is probably not so bad for this use. $a$ should be near $\sqrt m$ and coprime to it. You can seed it with $X_0$ being your birthday or some such.

Related Question