5 ms·
Here's a fun trick I learned from Flajolet and Sedgewick's Analytic Combinatorics (available online, page 52). I imagine it will seem incredible when tried with
by svat 8y ago
Here's a fun trick I learned from Flajolet and Sedgewick's Analytic Combinatorics (available online, page 52). I imagine it will seem incredible when tried with an actual classroom:
> Révész in [Strong theorems on coin tossing] tells the following amusing story attributed to T. Varga: “A class of high school children is divided into two sections. In one of the sections, each child is given a coin which he throws two hundred times, recording the resulting head-and-tail sequence on a piece of paper. In the other section, the children do not receive coins, but are told instead that they should try to write down a ‘random’ head-and-tail sequence of length two hundred. Collecting these slips of paper, [a statistician] then tries to subdivide them into their original groups. Most of the time, he succeeds quite well.”
> The statistician’s secret is [...] in a randomly produced sequence of length 200, there are usually runs of length 6 or more: the probability of the event turns out to be close to 97%. On the other hand most children (and adults) are usually afraid of writing down runs longer than 4 or 5 as this is felt as strongly “non-random”. The statistician simply selects the slips that contain runs of length 6 or more as the true random ones. Voilà!
----
Obviously, the way to beat this site (or the above classroom trick) would be to use "true" random numbers. But if one doesn't have access to coins or computers, it raises the question: what is a good way to generate a long sequence of reasonably random coin flips in one's head? For example, if you've memorized many digits of pi or e or some such "believed to be normal" constant, you could use whether each digit is odd or even (or maybe even something like throw away 8 and 9, and read each remaining digit in octal to get 3 random bits). But that only gets you so far...
- munificent 8y ago> But if one doesn't have access to coins or computers, it raises the question: what is a good way to generate a long sequence of reasonably random coin flips in one's head? Doing it in your head is hard, but if you a great memory or can write things down on paper, then you could: 1. Generate a bunch more "random" coin flips than you need and write them down. Do your best to be unbiased, but don't sweat it. 2. Start a new separate list of results. 3. Go through the original results a pair at a time. If the pair is "head, tail", write "head" in the new list. If it's "tail, head", write "tail". If it's "tail, tail" or "head, head", discard it. This is basically Neumann's "fair coin from a biased coin" trick: https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_... In theory, since you know the trick, it might influence the way you generate your initial random sequence. In practice, most of us probably aren't that smart. If you are, repeating the whole process using the results of the previous run a few times should guarantee enough complex mixing that your brain isn't clever enough to back-propagate the trick into how you generate the initial random coin flips.
- cevn 8y agoGenius. I will actually remember this, in case I ever need to be ... really random.
- Chinjut 8y agoThis works for getting rid of bias in individual flips towards heads or tails, but not for getting rid of dependences between separate flips (the very problem noted in the OP that humans are bad about).
- Matumio 8y agoInteresting. I would have suggested to XOR a few sequences, which would improve the result a bit, but this method works better.
- Xcelerate 8y agoOr if you’ve already memorized some digits of pi, just use odd and even digits as left and right (or 0 and 1).
- spc476 8y agoI did that for e [1] and the program was no better than 50% correct. [1] I have a program that calculates e to some arbitrary number of digits.
- andrewla 8y agoIt would be interesting to modify the site to do this automatically -- it measures your progress using the bigram method that you detail instead of using the input directly, and see if that generally makes humans do better.
- nestorD 8y agoA fibonacci pseudo random number generator would not be too hard to keep in mind (two integers modulo a fixed number) and might give you ok results if you choose your parameter well and avoid using the weakest bits as the generated boolean : https://en.wikipedia.org/wiki/Lagged_Fibonacci_generator https://en.wikipedia.org/wiki/Lagged_Fibonacci_generator
- jjeaff 8y agoOr perhaps take the lyrics from your favorite song and convert the letters to their respective number rank in the alphabet. Then heads for even and tails for odd numbers.
- godelski 8y agoThis is definitely not random
- ben174 8y agoNot random, but not deterministic for the machine - which blocks its ability to guess your next choice.
- jjeaff 8y agoTechnically, there is nothing in the universe that is random. We just need something sufficiently complex that no one can predict it.
- aardshark 8y agoI don't think this is proven. Can you elaborate?
- godelski 8y agoIt is definitely not proven. If it was we'd have a completely different view of quantum mechanics. This was even quite a big debate among quantum physicists in the 20th century and talked about in the beginning of every quantum book (at least that I've seen).
- jjeaff 8y agoWell, if you have enough data you can predict anything. A dice roll is "random", unless you know the starting position of the die, mass, size, air currents, force of throw, on and on. With perfect data, you could predict the outcome. Thus, it isn't 'really' random.
- wwweston 8y ago> what is a good way to generate a long sequence of reasonably random coin flips in one's head? I tried the modulo 2 length of the words in the text on the site. This was effective enough; at the end of three paragraphs the guesser had 50% correct and I had a positive balance. It's also pretty broadly applicable, there's a lot of texts in the world one could choose to use (anyone with a nearby bookshelf or internet connection is set, anyone who can memorize song lyrics, bible passages, poetry, etc doesn't even need that). There's a reasonable question of whether this distribution is itself biased. If you take one list of the 500 most common English words (https://docs.google.com/spreadsheets/d/1qh3MvdKLfTadXWZMIsaqrz9OkGENALA1Vv_c9i0tyI0/edit?usp=sharing https://docs.google.com/spreadsheets/d/1qh3MvdKLfTadXWZMIsaq... ), it turns out that there are 278 with an even length and 222 odd, so that's an indication there may be an exploitable bias. There's also the question of whether relevant N-gram patterns confound that beyond recognition ... or add another layer of predictability. But then again, there's such a wide variability in potential text choices and the function is so lossy (while being simple enough that most anyone could use it) that it seems like it's a pretty good choice for generating difficult to predict coin flip sequences.
- hervature 8y agoThis bias is pretty easy to overcome. Let’s denote E with even length words and O with odd length. If two words come up with EE or OO, discard, if it is EO use 0 and if OE then use 1. Same probability for both. This trades the bias for need more words.
- your-nanny 8y agothat's pretty good. In a pinch I was just choosing left/right depending on vowel or consonant, and flipping the rule every word or so. but the distribution is still a bit too tight.
- imh 8y agoOne way to generate a sequence of heads and tails is to start with either heads or tails, then randomly choose how many of those to use before switching to the other. You're sampling the length of runs. e.g. Heads, then choosing 12113 would translate to HTTHTHHH. It feels easier to ditch some of my biases generating a sequence this way.