How random can you be?
expunctis.com
expunctis.com
> 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...
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_...
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.
[1] I have a program that calculates e to some arbitrary number of digits.
> 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.
This is what Einstein believed, but he was wrong (quote about God doesn't play dice). Physics uses the Copenhagen Interpretation, which means that we have probability waves until we measure and the wave collapses. You may have also heard of the Heisenberg Uncertainty Principle (read: "There is a resolution to what we can measure").
The fact is that you can't know all your conditions. That's why we say things are random. Because there is a probability distribution to all these constraints (even if we had a device that could measure with "infinite" precision. The problem is that the universe itself hides information from us.
There's great sources for true random numbers. White noise (in atmospheric data), particle decays, particle motion (yes, even particle motion), etc.
Tldr: There's a lot of random stuff.
When poker players need a random source (for instance, deciding when to bluff) they can look at the current or previous tabled cards (or their own cards).
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/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.
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.
It feels easier to ditch some of my biases generating a sequence this way.
Ah, should have read more carefully -- it's using 5-grams as the base, not as the model, so really it's 6-grams, so we need B(2,6). We can try 0000001000011000101000111001001011001101001111010101110110111111
Mapped the other way, 0=left and 1=right, the guesser gets it right ~43%.
A de Bruijn sequence DB(2, k) is spelled by an Eulerian path in the corresponding de Bruijn graph, whose vertices are {0, 1}^k and where any arc (x, y) has the following property: x[2..k] == y[1..k-1].
Obviously, there are as many Eulerian paths as there are de Bruijn sequences.
Each such de Bruijn sequence has a different capability at getting a good score at the game "https://www.expunctis.com/2019/03/07/Not-so-random.html".
diff --git a/not-so-random.html b/not-so-random.html
index 48c04da..168a287 100644
--- a/not-so-random.html
+++ b/not-so-random.html
@@ -169,8 +169,12 @@
randomHelpFunc = function(evt) {
evt.preventDefault();
//document.onkeydown = null;
- for (let i = 0; i<10; i++) {
- lastKey = Math.round(Math.random());
+
+ // db(2, 6)
+ var inputString = "0000001000011000101000111001001011001101001111010101110110111111";
+
+ for (let i = 0; i< inputString.length; i++) {
+ lastKey = inputString[i] == "0" ? 1 : 0;
testPrediction();
updateAll();
predictNext()Is there an error in my patch ?
diff --git a/not-so-random.html b/not-so-random.html
index 48c04da..c650b5b 100644
--- a/not-so-random.html
+++ b/not-so-random.html
@@ -169,8 +169,12 @@
randomHelpFunc = function(evt) {
evt.preventDefault();
//document.onkeydown = null;
- for (let i = 0; i<10; i++) {
- lastKey = Math.round(Math.random());
+
+ // db(2, 6)
+ var inputString = "0000001000011000101000111001001011001101001111010101110110111111";
+
+ for (let i = 0; i< inputString.length; i++) {
+ lastKey = inputString[i] == "0" ? 0 : 1;
testPrediction();
updateAll();
predictNext()However with $1 vs $1.05 returns, you'll steadily make money.
RRRRRRLRRRLRLRLLRRRRLLRRLRRLRLLLRRRLLLRLRRLLRLRL
RRRRRRLRRRLRLRLLRLLRRRRLLRRLLLLRRLRRLRLLLLLRLLLRRRLLLRLRRLLRLRL
RRRRRRLRRRLRLRLLRLLRRRRLLRRLLLLRRLRRLRLLLLLLRLLLRRRLLLRLRRLLRLRL
RRRRRRLRRRLRLRLLRLLRRRRLLRRLLLLRRLRRLRLLLLLLRLLLRRRLLLRLRRLLRLRL
RRRRRRLRRRLRLRLLRLLRRRRLLRRLLLLRRLRRLRLLLLLLRLLLRRRLLLRLRRLLRLRL
...
What's at stake here is the same thing that threatens to eventually cause another civil war in the US, but that is a question for another time. :) It is a broad class of theorems which state that if you have a function f: X -> X and you repeat it over and over it naturally finds an input x such that f(x) = x. This repetition has naturally found a set of moves which resets the Markov matrix back to what it was. If you randomized the prediction on ties then I am not sure what I would do exactly... I would have to steer the Markov matrix into a cycle but assuming that it stores the absolute counts for every single prediction, any oscillations I'm using would want to naturally decay to zero... I might be able to exploit it if you were to only look at, say, my last 1000 moves' history to make your predictions, and maybe I can still induce an oscillation that does better than random chance, but I am not sure that I can.
var seq = '0000001000011000101000111001001011001101001111010101110110111111'; var index = 0; setInterval(function(){ captureKeyFunc({code : seq[index%seq.length] === '1' ? 'ArrowLeft':'ArrowRight', preventDefault: function () {}}); index++; }, 10);
setInterval(function(){ captureKeyFunc({code : Math.round(Math.random()) === 1 ? 'ArrowLeft':'ArrowRight', preventDefault: function () {}}); }, 10);
There was an attack I read about for garage door openers or numeric entry doors where they didn't have an enter button. So entering they entered the De Bruijn sequence and had the answer in a small fraction of the time compared to trying each combo once and hitting "Enter".
The basis for this is that you will likely spend maybe 30-60s playing this game so you will register something between 100-200 keypresses or so. If you just click the "Randomize" button you can see the problem: a truly random input source will fluctuate over 100-200 keypresses much more than it will be biased upwards, so that after 100-200 you will probably see some run of "bad luck" by which the truly-random algorithm crashes from $1005 to $995 or so. Now if this were you, you would have stopped there with the last 5-10% being predicted perfectly, and said "okay, okay, the algorithm has learned how I behave." But it hasn't.\
Part of this is the fallacy that people generally assume that over a large number of trials the standard deviation of a sum of random variables drops to zero -- that is true of an average but not a sum. So you have a discrete random variable which takes on the values +1.05 with probability 0.5 or -1 with probability 0.5, so its variance is basically 1.0 (off by 625 ppm but whatever) and so its standard deviation is basically 1.0 and if you sum N of these you have a standard deviation that is 1.0 √N while the mean is 0.05 N, these only equal when √N = 1.0/0.05 = 20 and thus N=400.
So at 100-200 trials, you cannot generally expect the systematic bias from winning extra money when you are random to visibly outweigh the random noise from just randomly being wrong, you have to go to 500+ trials to really prove your mettle. But most people just won't play this thing for that long.
The program only guessed 49% of my inputs right over 100 Iterations.
When I understood it's only two keys the program guessed correct 60% of the time.
Incidentally, I also got about the same rate (59%) of success from the algorithm when I used only the two recognized keys.
This is kinda cool, our brain's RNG does better with more "mental outputs"...
This is very interesting...
Useful for generating random rocks paper scissors moves, or in this case, random directions (odd = right, even = left)
f: π(k) --> δ(k)
So even if Pi could be used as a pseudorandom generator (and it actually can't be), you'd lose that property by defining an injective map from your domain of inputs to the codomain of outputs.
0: 0 Rock
1: 1 Paper
2: 2 Scissors
3: 0 Rock
4: 1 Paper
5: 2 Scissors
6: 0 Rock
7: 1 Paper
8: 2 Scissors
9: 0 Rock
0/Rock: 4
1/Paper: 3
2/Scissors: 3
The common way of dealing with this is to "ignore" any number that would make the set biased. Here you would ignore 9 and you have an even distribution. So, you're playing 7 rounds of RPS and you go
3/R
1/P
4/P
1/P
5/S
9! SKIP! 2/S
6/RAs for why converting digits in this way matters - a lot of randomness is expressed by the entropy. It's harder for you to correctly guess the sequence {1,7,9,3,6,8,2,4} than it is to guess the sequence {1,1,1,1,0,0,0,0}.
If I ask you to guess a decimal digit I've chosen "randomly", you have a 1/10 chance of being correct. If I ask you to do the same for binary digits, you have a 1/2 chance of being correct.
Basically you want to think of these as subsequences, not individual numbers. If Pi is normal (which is a big if), then Pi is normal in every single base, including decimal or binary. But it's not generally true that a normal number generates another normal number by mapping each digit to the digit's parity.
If pi is [absolutely] normal though all sequences exist in it at equal frequency. Meaning that for any given sequence there is an infinite number of positions in pi to find it and that all the possible following digit sequences are equally likely.
So the computer could never know the next digit.
Aside: guessing a D16 roll seems way more likely than guessing a nibble of binary, and perhaps a little less likely than guessing 4 coin flips!??
And why is that a problem for generating random arrow presses?
{0,1,2,3,4,5,6,7,8,9}
{0,1}
You're selecting from a space of 10 digits for inputs, but the computer only has to guess from a space of 2 digits for outputs.
Nobody knows! Everyone in math is sure that it is, but nobody had found a proof yet. (It may be false...) An extension to this question is if pi is a "normal number". More details: https://en.wikipedia.org/wiki/Normal_number http://mathworld.wolfram.com/NormalNumber.html
[There are some technical details because pi is not a random number, but for the sake of simplicity, let's assume that pi is a random number.]
It's much easier if we'd live in a word that use base 8 instead of base 10.
Let's suppose that we have the sequence of digits of pi in base 8.The algorithm of the GP is to replace {0,2,4,6}->0 and {1,3,5,7}->1 to obtain a binary "random" sequence.
Your alternative is to write pi in binary, and use it as a "random" sequence. But if this is a good "random" sequence then you can pick every third digit and get another good "random" sequence. [Here good means something like iid with uniform distribution]
But if you start at the correct position, it's equivalent to pick every third number of the binary representation and to classify the digits in the base 8 representation as even or odd.
If you choose other starting points to pick every third digit, you get alternative maps:
* low and high: {0,1,2,3}->0 and {4,5,6,7}->1 (like in the roulette[1])
* crazy: {0,1,4,5}->0 and {2,3,6,7}->1
These other two selections produce also good "random" sequences.
The important part is that the projection that is selected maps the same number of elements to each element. In this case the three methods maps 4 elements to 1. This ensures that it maps iid with an uniform distribution to an iid with a uniform distribution.
Moreover, you can pick any arbitrary 4 numbers and map them to 0 and map the other 4 to 1 and it will work as well as the other three maps I used. (This is like the red/black option in the roulette[1].)
---
Back to base 10. Any map that maps 5 number to 1 will maps iid with an uniform distribution to an iid with a uniform distribution. In particular the even/odd map that the GP is using is fine.
With this map you loose a lot of entropy, but since there is infinite entropy you can drop a lot of it and still keep infinite entropy. It's not as efficient as using the base 2, but it correct.
[1] An ilegal fair roulette, with 36 numbers, without the green 0.
You're correct that if Pi is normal, it's normal in all bases. But that's precisely the point I'm getting at - if Pi is normal, you need to use base 2 for this to work because your codomain is just {0,1}.
Mapping a number to another number such that each digit becomes its own parity is materially different from converting that number to base 2. They aren't the same thing whatsoever, and you can't generally take a normal number and create another normal number this way.
So even if we accept the reasonable conjecture that Pi is normal, you still need to map it to the same base as your codomain in order for its entropy to be preserved. The proposed function is injective and destroys entropy.
You can use any base that is a multiple of 2 (like 10) and then apply a parity function to the digits. If pi is normal, then the digit parity sequence is also normal.
Sure you lose some entropy, but in some sense the digits of pi have 0 entropy anyway since they can be calculated. And in the other sense of treating the digits of pi as an unknown random sequence, there is infinite entropy, so throwing away 70% of it doesn't matter.
Yes, that's a well-established effect. Also, most people tend to choose "rock" for the very first throw of a session.
For instance, if you input RLLRRLLLLRLLRRRLLRLLLLLLRRLRLRLLLRRRRLRRRRRRLLLRLRLRRLRRLLRRLLLRRLRRLRLLRLRRRLRLRLLLRLLRLLLLLRLRLRRR it only guesses right 34% of the time.
https://gist.github.com/kkwteh/b81d8e599ec46a2d64b096f953a11...
If you "play" for a long time, eventually, all 64 6-grams will have occurred.
https://i.imgur.com/O3EggFY.png (0% guessed right after 15 key presses)
Here's the sequence I used. I'd be interested if this works for other people too:
1: right
2: right
3: right
4: right
5: right
6: right
7: left
8: right
9: right
10: right
11: left
12: right
13: left
14: right
15: left(this comment was meant in jest rather than as a criticism. I really enjoyed this site)
"The program keeps a database of each possible combination of 5 presses, and two counters are stored under each entry — one is for every zero that follows the combination, and the other one is for all the ones that follow this combination. So every time you press a key, an entry in the database gets updated. To make a prediction, the program needs only to look up the entry corresponding to the last 5 presses and decide by looking at the counters which key press is more likely to follow."
By the way, within those first 100 digits, there are multiple occurrences of even or odd sequences that go past the 5-gram level.
Within the first 1000 digits of pi, there is one 11-digit sequence of odd numbers, which you will lose money on.
That doesn't seem correct. How do you fairly map digits 0-9 to base 2? Assuming pi has an even distribution of digits, you are going to get a disproportionate amount of 1's.
There are 2 ways of mapping digits to binary: fixed width and minimal.
With minimal the digits 0 and 1 require 1 bit, and 8 and 9 require 4 bits. So then 0:9 maps to (0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001).
Tally it up: 15 ones, 10 zeros. That means you will be encountering 1 50% as often as 0, which doesn't seem random to me.
So then let's try fixed width:
0:9 maps to (0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001).
Tally it up: 15 ones, 26 zeros. That means you will be encountering 0 >60% as often as 1, which doesn't seem random to me. Also, with this scheme you can never encounter more than 4 ones in a row ("78"), which is also unrandom
There's no way to convert pi to base 2 in your head though...
$ python3
>>> # not using os.urandom to save a import...
>>> rng = open("/dev/urandom", "rb")
>>> "{0:08b}".format(rng.read(1)[0])
[0] http://people.ischool.berkeley.edu/~nick/aaronson-oracle/
I'm happy to participate in such statistics so I don't need that HTML file, but I'm not okay with sending it to some third party that then tracks a whole lot of other things as well. So Google Analytics is blocked as always; I'm sorry that I couldn't submit my 52% score...
I tried using an actual random number generator to generate inputs, just to verify with my eyes that, as expected, the computers guess rate hovered around 50%, and didn't get more than 5% off usually. (I realize it _could_).
I tried picking a 'random' (knowing surely I'll still have unconcious patterns) number 1-5, and then doing that many lefts, pick another number, that many rights.
That got me a really good percentage (computer was only around 30% right) up to ~40 or so iterations. But didn't last, eventually it got to around 50% or so as usual, and then I started to lose.
It would be interesting, if knowing the algorithm the guesser is using, if you could devise an algorithm to defeat it, and "win" lots of money from the "bank". I mean, I guess, the obvious thing to do, if you had the algorithm the guesser was using, you could just run it on your own past input, and then always pick next whatever the opposite of what it would pick is. It seems like that would have to work, and that it couldn't possibly work, heh. This becomes an interesting illustration of... something or other computer science-wise, it reminds me of Godel Escher Bach or something.
What this whole thing makes me think of is surveillance. Say, in an old detective thing, trying to "lose a tail" by making "random" turns. In our society of increasingly universal surveillance, _plus_ computers analyzing the data (and you don't know the exact algorithms being used)... there's probably no way to "lose the tail".
1. Let {l,r} be the numbers of times in the history we have seen a five-letter sequence with a prefix of whatever the four most recently made moves were, and a suffix of {left,right}
2. Pick r randomly between 0 and 1
3. If r > l/(l+r) (or l=r=0), guess the next move is r.
You know this is the strategy so if you can calculate l and r and so make the opposite move (randomly even) and win with a probability of r/(l+r), however by making your move, you make l/(l+r) converge towards 1/2 and so your probability of winning goes to 1/2 too. I suspect the best strategy in the long run is to play randomly or to just repeat some longish cycle that includes each length five cycle an equal number of times.
let left = () => captureBtnLeftFunc($.Event())
let right = () => captureBtnRightFunc($.Event())
() => captureBtnRightFunc($.Event())
setInterval(() => {
console.log("Guessing");
if (Math.random() < 0.5) {
left()
} else {
right()
}
}, 1000)Running this myself, the guesser is correct 46% of the time after 100 iterations.
Both cite that same "Aaronson Oracle" as the source inspiration.
The interesting part was this: I had the script just run a loop with a short delay between outputs. I started with a little under a second, and my brain/fingers kept trying to anticipate the next element. Often incorrectly, making my input predictable by the site. My fingers were just twitching to press a key.
In order to "win", I had to set the delay to 1.2 seconds, physically lift my fingers off the keyboard, and spend a little bit of effort reading each choice to make sure that I was actually following the real random instructions.
My brain just struggled to cope with the lack of pattern.
A person good at mental arithmetic could memorize a small-state PRNG and get good results but I couldn't personally do this. I wonder if this has any strategic advantages in any areas of life. Maybe poker?
Flaw in my plan: I don't know if the word length distribution for most english texts (much less a given writer) is biased.
e.g. L,R,LL,RR,LLL,RRR, and if it starts guessing right enough, reset or reverse.
Then, it ends up being closed loop two armed bandit ...
It's harder than I expected...
Let's take a simple example: you had an important meeting at 9 am but since you were stuck in traffic, you were late by 10 mins.
The final outcome can be clearly explained by actions that directly or indirectly led to them. May be there was an accident causing the traffic jam. May be you woke up 10 mins late than usual thereby getting caught in rush hour traffic. May be the cab you took to work, arrived late at your destination cause he woke up late.
All of the above are totally controllable actions, albeit not in your direct control. Hence the feeling that life is random. Because none of us have any control over the outcomes of the actions of others, who subtly influence our lives on a daily basis.
Think of it this way: our life is intertwined with the lives of others in one way or the other. From the cab driver who drives us to work to our loved ones who shatter our hearts, their actions influence us, some more than the others, but influence us nonetheless.
It's a complex equation, with a whole lot of variables, most of which are beyond our control and unknown and the solution to this equation is the outcome of an event.
I believe that if one knew the values to all the variables at any given point of time, then one would be able to solve the equation with precision
http://www.levarburtonpodcast.com/
Episode 5, "What it means when a man falls from the sky" by Lesley Nneka Arimah
Perhaps there are just too many variables.
Randomness implies unpredictability, which implies a lack of knowledge; if you can accurately predict what is going to happen next in some sequence, temporal or otherwise, by observing what has come before, then it isn't a random sequence.
But to someone who possesses all possible knowledge, nothing is random, because everything is predictable. A sequence might still retain certain properties that we associate with randomness (e.g. an unbiased distribution), but no sequence is random if you can always accurately predict the next item.
Obviously, none of us mere mortals is omniscient, but it is possible, for instance, to develop new predictive techniques and to turn once-thought-random sequences into non-random sequences.
Not according to quantum mechanics.
So ...
Are you saying an omniscient being is impossible, because something about quantum mechanics implies that it is impossible to possess all possible knowledge?
Or are you saying that even if an omniscient being possesses all possible knowledge, they would nevertheless be unable to accurately predict all sequences because of some knowledge we have about quantum mechanics?
Of course that still leaves room for an omniscient being that never collapses the wave function and just deals in probabilities. But then your predicitions sound like "there's a 99.978% probability you will be hit by a car on tuesday at 10:04 am." with the remaining 0.022% accounting for quantum flactuations adding up to produce a different result. Whether you call that "all knowing" and whether that proves that nothing is random sounds like an interesting philosophical question.
> Or are you saying that even if an omniscient being possesses all possible knowledge, they would nevertheless be unable to accurately predict all sequences because of some knowledge we have about quantum mechanics?
That's an extremely astute question. I'm impressed that you managed to realize that that's an important distinction and that you don't know which it is.
It's actually the latter, and incredibly we can prove it. And the proof of this is surprisingly accessible:
Maybe I'm thinking about a form of omniscience that exists outside of time, in which case, of course an omniscient being would know what happens next, because they would know the future just as well as the past. (Example: Any omniscient being will know which photons will pass through a polarizing lens not based on prediction but based on already knowing the outcome.)
Can you tell me more about why you think it can't?
As a less powerful entity, if you know all the result in the lab until now, you can consider an experiment made 1 hour ago and "predict" the outcome without breaking the laws of quantum mechanics.
That is, a "truly omniscient being that would not have to rely on measurement" would apparently violate the laws of physics, is one thing quantum mechanics maybe seems to say.
https://en.wikipedia.org/wiki/Uncertainty_principle
"Thus, the uncertainty principle actually states a fundamental property of quantum systems and is not a statement about the observational success of current technology"