One time, my wife and siblings had to choose from a number of heirlooms that had be left to them but not assigned. They are living around the planet, and the discussion came up about how to decide the order in which they'd select the items.
I came up with this: Each of them select a different stock market index. On the same calendar trading day, they choose two digits past the decimal. When the market's close, compare the two digits of the closing price of their chosen index to the two digits they selected and then choose heirlooms in the order of closeness.
It worked quite well. They were on board because they could make two selections in determining their order: Market and digits. Two of them could choose the same two digits if they wanted and still have different scores. No complaints.
Another possibility: hold a private auction among the siblings and give the proceeds to the favorite charity of the person who left the heirlooms. It's fair [1], honors their memory, and makes the world a better place all at once. Three-way win.
---
[1] You can compensate for unequal economic situations by limiting the total amount that any one person can bid to a value that they can all afford.
This is one of the craziest, most convoluted approaches to randomness I've ever heard of. I love it. Personally, I would've just had a third-party roll a die to establish the order. If there's a tie, roll again. More than 6 siblings? Two dice. Fun for the whole family! (and would take just a few minutes)
Yes, thanks for prompting my memory. We needed an approach that put all five of the siblings on the same footing. Even a third party chosen by one of the five may not be trusted since the others may not know the party.
It was goofy, but satisfied them all without dissent. And it worked!
The least significant bits of a bitcoin PoW hash behave pretty randomly.
You could either bet on a fixed future block height, or on the first block past a given future timestamp...
That's actually very easy to control. Just pay a high transaction fee. The nonce comes from a PRNG that doesn't have to pass many randomness checks. Your proposal really is no more random than a counter based SHA256 PRNG except with an awfully high sample latency.
One example for using algorithmic over true randomness comes up in games. For example, if the entire map generation is driven by a single RNG instance with a user-chosen (or, initially chosen off of true randomness), players can share seeds generating interesting worlds. Or, even more interesting, folks are brute-forcing Slay the Spire seeds in order to find cool seeds involving a relic called Pandoras Box, which replaces your entire starting hand.
From there on, it becomes a very conscious decision how many RNGs to manage in an engine. Unpredictable things, like UI or random animation choices and such tend to have their own RNG, so something like the AI or story-driving systems can have their own, more predictable RNG.
However, this again raises a tricky follow-up question: Do you persist the RNG state in the save file of a user? The answer here isn't as obvious as it seems, as it allows different kinds of save-game abuses. Re-initializing the RNG on load allows players to reload in order to get different results from actions. Persisting the RNG allows players to start testing and predicting actions after loading the game. It's a tricky question.
Another really interesting tangent to go on here as well is how the NES and similar old consoles handled randomness: They didn't really. The randomness was based on player inputs. This in turn gives raise to a great TAS technique: RNG manipulation. Carefully crafting input sequences can optimize the random results you get later, which results in entirely crazy runs.
I had a fun time rigging my Geiger counter up to my computer for a little demo project of getting random numbers from radioactive decay. It's stupidly slow as is, but could be sped up. I should hook it up to my sound card multichannel analyzer and scintillator now that I have one and update this. Would be way faster with more pulses coming in from the lower-energy gammas and x-rays that the G-M tube can't see.
I haven't read the article yet, but I want to say that (so far) this is no actual proof that radioactive decay is random. There is evidence for it, and we assume it is, but it hasn't been proven.
There can be no proof, in the mathematical sense, of anything about the physical world, so radioactive decay being provably random in the most tested, accurate model of the world we have is as close to certainty as anything known about the physical world.
Semi-related is this year's Nobel Prize for experiments showing Bell's Theorem is physically true. This rules out hidden variable theories.
Technically, even then it only rules out efficient local hidden variable theories. A theory where every particle carries a local hidden variable containing the entire state of the universe can (obviously?) emulate any other theory, quantum or otherwise (with a bit of finangling for things like quantum field wierdness).
Yes, you're correct. However, nonlocal hidden theories bring other issues that don't seem plausible. That's why the best current quantum field theories do make radiation a purely random event. None use nonlocal hidden variables.
Mathematical proofs are in escapable conclusions of your choice of axioms (assumptions).
Negative physical proofs is evidence showing that a particular model (assumption) about the physical world does not hold. Negative physical proofs are relatively straightforward. Take your model, make a prediction, and then show the prediction is untrue in the physical world. This is more or less how the Bell Inequality test was supposed to be.
Positive physical proofs (for example, prove that radioactive decay is random), is in general not "actually possible". We can only show that physical reality is sufficienty compatible with your model.
Yes more or less. Bell's Theorem stated that if local realism holds (very roughly things continue existing separate from observation, and things can't influence other things faster than the speed of light), then certain measurements cannot correlate at higher than a certain rate. The relevant experiments show that for increasingly well designed and controlled cases, that these measurements correlate above the limit, and therefore local realism cannot be true.
Physical proof is not the same as mathematical proof. It is strong evidence for a mathematical model to be an adequate description of reality.
But that means we did not proof that the mathematical model is reality. There might be some weird edge case looming around the corner under which our model utterly fails to describe the physical world. Then we have to adjust the model or find a new one.
True. There's a whole debate about determinism in the universe, which includes radioactive decay. It's just one of those things that's considered roughly as random as it gets.
That's not really true. The Bells inequality experiments have proven (falsified) that there are no local hidden variables. The vast majority of scientists are not willing to throw away causality by accepting nonlocal hidden variables.
In other words the true randomness of quantum Events has been broadly accepted to reflect reality.
The article agrees, but of course it’s making a slightly different point and talking about what kinds of randomness are practically or even theoretically predictable today given what we know. Since nobody knows how to predict radioactive decay, it’s currently considered “truly” random, but its status could change in the future.
“Arguably then, from a truly omniscient perspective, nothing, not even the physical world, is truly random—it is in the nature of causality that everything that happens has a chain of prior events that caused it. But in practice, for most real-world randomness, obtaining such an omniscient perspective is infeasible to the point of being impossible.”
After this article I went and started reading about "roulette computers" and apparently there are 50+ sites owned by a single scammer, that all have the same layout: https://www.roulette-computers.com/
And apparently he owns this network of forums and review sites that all funnel towards this scam. Very interesting... It's like as 100x worse than mattress reviews it looks like
I wonder if there is an actual legitimate roulette computer that exists (which is mentioned in this randomness article).
Maybe the scammer made this post on PCG-Random ...
My former job of a slot machine tech would often involve setting up a slot machine. The PAR (paytable and reel) sheet had set groupings you could pick. Integrity and Compliance, local government regulators, security, management, superiors, surveillance all watching me like a hawk while I enabled it then seal the chips.
edit: just a note that for years I wasn't even allowed to see or touch a PAR sheet. Literally, not even see or touch the things. They were securely locked up.
Much of a slot machine is "random" but to a point where the house never lost. If it were truly random not pseudo random there would be no way to control what was won or maybe nobody would win at all. Organized chaos really. And most of the time the slot is a 10 or even 20 year old barely functioning piece of junk. The machine has been paid off (so to speak) so any money it makes is pure profit.
> If it were truly random not pseudo random there would be no way to control what was won or maybe nobody would win at all.
This doesn’t make much sense. You don’t need to manipulate an RNG to ensure the house has an edge - and to my understanding this is generally not done in the big casino venues because it’s not even necessary. Because what you’re essentially suggesting is that machines purposely use poor quality PRNGs - which is absolutely not true. They have in the past unintentionally and have only been burned by it.
Utilizing a PRNG does make auditing easier though. And it’s much easier to produce a reliable PRNG than find a reliable source of randomness that is not vulnerable to manipulation. (Having said that, mechanical real machines got by for years without any algorithmic RNG)
Games of chance that utilize effectively true randomness (since the behavior is unpredictable even to the house) have been around for millennia.
Roulette is perhaps an easier example. A typical American wheel has 38 positions: 1-36, 0 and 00. If you bet on a single number and hit, a 1/38 chance, you don't win 37x your bet, you only win 35x. If you bet on Red, or Odd, those pay 1-1 but the odds of winning are less than 50%, there are 18 winning results and 20 losing results. The payouts are always lower than the true probability of that specific outcome. If two people play opposite colors, one Red and one Black, the casino will break even on numbers but collect both wagers when 0 or 00 wins.
Another example is sports betting with a point spread. You bet $11 to win $10, on supposedly an 50-50 wager (the purpose of the point spread).
Slot machines work off the same principles. It's ok for the outcomes to be random, because the payouts are always less than the true probabilities.
The outcome of each individual spin is random. The reason a slot machine is always profitable is due to the payouts. To put it simply, a result that will occur once every 100 spins only pays out 90 credits. The various PAR sheets allow casinos to adjust how much to tilt the odds in their favor. For the 1 in 100 example, the various pay tables might have that particular outcome pay 87, 89, 91 or 94 credits, allowing a casino to decide between 6% all the way up to 13% hold. But that particular combination of reels will still occur only 1 in 100 spins (theoretically, because it is in fact random, not cycling through a script).
> High-quality algorithmic randomness is similar. If we are denied an omniscient perspective—if we can't look “inside the box” to see what is going on—the random numbers produced will seem completely random.
The article touches on this briefly, but I think the distinction between cryptographic pseudorandomness and (unfortunately) "ordinary" pseudorandomness is important here. To get at the difference, we could say that you're allowed to look at everything inside the box, except specifically the bits of the secret seed. If there's still no way for you to distinguish the output from true randomness, other than the "brute force" strategy of trying every possible seed value, then this box gives you cryptographic randomness (i.e. it's a "CSPRNG"). Usually we'd also want to make the seed big enough that we don't have to worry about that brute force attack in practice, 256 bits as a rule of thumb.
> They would then use their spy-craft to combine their message with the random numbers (e.g., by numbering the letters of the alphabet and adding each successive letter of their message to each successive number from the table). They could then send that message knowing that if it was intercepted, it would be unreadable without a copy of their codebook
(I'm sure the author understands the following, but I think it's important to clairfy it anytime we touch on encryption.)
This sort of scenario is tricky if we don't make the "cryptographic vs ordinary" distinction above. There are lots of PRNGs that look random to us but whose output can be fully predictable to a computer program after a few observations. This isn't a rare corner case: most PRNGs have this issue unless they're speficially designed not to. For example, the Mersenne Twister algorithm used by Python's `random` module has this property, and I think the PCG algorithm that this article is about also has this property. If you use Python's `random.randbytes()` to generate your codebook, it's entirely possible and arguably likely that someone reading your encrypted messages will learn enough to predict every subsequent page of your codebook, which lets them easily decrypt all your messages after a certain point.
The PCG family is somewhat harder to predict than Mersenne Twisters, but not nearly as hard to predict as cryptographic PRNGs. PCG’s author goes into some detail about it here https://www.pcg-random.org/predictability.html and the conclusion is:
“ The PCG family is designed with being difficult to predict in mind, and the default generators are not trivially predictable. But the primary design goal for most members of the PCG family is to be a fast statistically-good general purpose generator, and so by design they do not work quite as hard as most cryptographically secure generators.
“Most of the PCG output functions involve nonlinear operations and only reveal partial state, but as we saw from Knuth's truncated LCGs, that's no guarantee of that PCG generators can't be cracked.”
This article's argument boils down to Newtonian physics being, in theory, completely deterministic, thus not "true" randomness. It says, "tools exist to predict the path of a roulette ball (using data gained after it has been released and before the croupier calls, “No more bets!”), at least according to people who make money selling such gizmos". Key phrase there is according to people who make money selling such gizmos.
It leaves quantum randomness for a footnote, after spending many words saying that if you use a big enough permuted congruential generator, it's random enough for cryptographic use.
Is it possible to gather entropy from weird sources from the user like mouse movements, that person's timezone, OS version and type, language preferences, screen resolution, browser fingerprint etc?
How would that be any different than atmospheric noise or die rolls? Are people's mouse movements and browser fingerprints that predictable, because last time I checked, people have a certain cadence by the way they move their mouse and the way they type, and browser fingerprinting yields very unique data which is hard to replicate and reproduce.
> Is it possible to gather entropy from weird sources from the user like mouse movements, that person's timezone, OS version and type, language preferences, screen resolution, browser fingerprint etc?
User mouse movements, maybe. But only while it's moving.
A person's timezone, OS version and type, language preferences, screen resolution, browser fingerprint etc... those don't change so often. So they're not really good sources of entropy.
This article touches a nerve for me since i have always wanted to better understand (ever since exposed to books by Ivar Ekeland and Nassim Taleb) the relation and differences between concepts like Random, Probability, Stochastic, Pseudo-Random, Determinism/Non-Determinism, Chaos, Information, Entropy.
I would really appreciate it if folks can point me to books/papers/articles/etc. which explain all of the above starting from first principles.
Also are there any courses one can pursue to study the above?
Not a good book for this at all. I don't think I'd start with cryptography if what I was really after was stochastic processes; something in algorithms would be better. But a good modern starting book for cryptography is JP Aumasson's Serious Cryptography.
“Arguably then, from a truly omniscient perspective, nothing, not even the physical world, is truly random”
Super misleading statement, especially with the accompanying footnote. Quantum physics indicates there really is true randomness in the physical world, but let’s just ignore that, stick to Newtonian physics, and throw in a quick footnote to cover ourselves.
Collapse posits truly random events, but there are many deterministic theories. In the end it doesn't really matter though- even if apparent collapse is caused by decoherence, you still subjectively experience winding up in one of them. There are other theories (Bohm comes to mind) that are entirely deterministic without decoherence, but they rely on a random seed and non-local hidden variables.
She has time to write blog posts, but claims she doesn't have a few minutes to update the lying front page that makes claims like pcg having just as good prediction difficulty as chacha20 and other misleading entries.
I came up with this: Each of them select a different stock market index. On the same calendar trading day, they choose two digits past the decimal. When the market's close, compare the two digits of the closing price of their chosen index to the two digits they selected and then choose heirlooms in the order of closeness.
It worked quite well. They were on board because they could make two selections in determining their order: Market and digits. Two of them could choose the same two digits if they wanted and still have different scores. No complaints.
Not random, but seemed fair to all.