The argument against PRNGs this paper makes isn't that the PRNG produces results that can be distinguished from TRNG, but that the 256-bit seed deterministically chooses a single shuffling. If you need 300 bits to truly shuffle the assignment but you only have 256 bits, then that's a lot of potential assignments that can never actually happen. With this argument it doesn't matter what the PRNG is, the fact that it's deterministic is all that matters. And this invalidates the p-value because the p-value assumes that all possible assignments are equiprobable, when in fact a lot of possible assignments have a probability of zero.
I imagine you could change the p-value test to randomly sample assignments generated via the exact same process that was used to generate the assignment used by the experiment, and as you run more and more iterations of this the calculated p-value should converge to the correct value, but then the question becomes is the p-value calculated this way the same as the p-value you'd get if you actually went ahead and used equiprobable assignment to begin with?
Ultimately, this all comes down to the fact that it's not hard to use true randomness for the whole thing, and true randomness produces statistically valid results, if you use true randomness for assignment then you can't screw up the p-value test, and so there's no reason at all to even consider how to safely use a PRNG here, all that does is open the door to messing up.
If you have 300 bits of shuffling entropy, you have a lot of potential assignments that can never happen because you won't test them before the universe runs out. No matter how you pick them.
Of course a PRNG generates the same sequence every time with the same seed, but that's true of every RNG, even a TRNG where the "seed" is your current space and time coordinates. To get more results from the distribution you have to use more seeds. You can't just run an RNG once, get some value, and then declare the RNG is biased towards the value you got. That's not a useful definition of bias.
Everyone agrees that most of the possible shuffles become impossible when a CSPRNG with 256 bits of state is used. The question is just whether that matters practically. The original author seems to imply it does, but I believe they're mistaken.
Perhaps it would help to think of the randomization in two stages. In the first, we select 2^256 members from the set of all possible permutations. (This happens when we select our CSPRNG algorithm.) In the second, we select a single member from the new set of 2^256. (This happens when we select our seed and run the CSPRNG.) I believe that measurable structure in either selection would imply a practical attack on the cryptographic algorithm used in the CSPRNG, which isn't known to exist for any common such algorithm.
Yeah, you're discarding almost all permutations, but in an unbiased manner. It seems to imply not only an attack, but that your experimental results rely strongly and precisely on some extremely esoteric (otherwise it would've been found already) property of the randomization algorithm. If you can only detect the effect of television on turkeys when using a PRNG whose output is appropriately likely to have a high dimensional vector space when formated as a binary square matrix then I think you should probably go back to the drawing board.
The cases that are not close to a multiple are handled by the rejection of a part of the generated random numbers.
Let's say that you have a uniform random number generator, which generates with equal probability anyone of N numbers. Then you want to choose with equal probability one of M choices.
If M divides N, then you can choose 1 of M by either multiplication with taking the integer part, or by division with taking the remainder.
When M does not divide N, for unbiased choices you must reject a part of the generated numbers, either rejecting them before the arithmetic operation (equivalent to diminishing N to a multiple of M), or rejecting them after the arithmetic operation (diminishing the maximum value of the integer part of product or of the division remainder, to match M).
This is enough for handling the case when M < N.
When M is greater than N, you can use a power of N that is greater than M (i.e. you use a tuple of numbers for making the choice), and you do the same as before.
However in this case you must trust your RNG that its output sequence is not auto-correlated.
If possible, using from the start a bigger N is preferable, but even when that is impossible, in most cases the unreachable parts of the space of random number tuples will not make any statistical difference.
To be more certain of this, you may want to repeat the experiment with several of the generators with the largest N available, taking care that they really have different structures, so that it can be expected that whichever is the inaccessible tuple space, it is not the same.
This is correct, but for the author's example of randomizing turkeys I wouldn't bother. A modern CSPRNG is fast enough that it's usually easier just to generate lots of excess randomness (so that the remainder is nonzero but tiny compared to the quotient and thus negligible) than to reject for exactly zero remainder.
For example, the turkeys could be randomized by generating 256 bits of randomness per turkey, then sorting by that and taking the first half of the list. By a counting argument this must be biased (since the number of assignments isn't usually a power of two), but the bias is negligible.
The rejection methods may be faster, and thus beneficial in something like a Monte Carlo simulation that executes many times. Rejection methods are also often the simplest way to get distributions other than uniform. The additional complexity doesn't seem worthwhile to me otherwise though, more effort and risk of a coding mistake for no meaningful gain.
And why does it matter in the context of randomly assigning participants in an experiment into groups? It is not plausible that any theoretical "gaps" in the pseudorandomness are related to the effect you are trying to measure, and unlikely that there is a "pattern" created in how the participants get assigned. You just do one assignment. You do not need to pick a true random configuration, just one random enough.
I assume that as long as p-values are concerned, the issue raised could very well be measured with simulations and permutations. I really doubt though that the distribution of p-values from pseudorandom assignments with gaps would not converge very fast to the "real" distribution you would get from all permuations due to some version of a law of large numbers. A lot of resampling/permutation techniques work by permuting a negligible fraction of all possible permutations, and the distribution of the statistics extracted converges pretty fast. As long as the way the gaps are formed are independent of the effects measured, it sounds implausible that the p-values one gets are problematic because of them.
P-values assume something weaker than "all assignments are equiprobable." If the subset of possible assignments is nice in the right ways (which any good PRNG will provide) then the resulting value will be approximately the same.
Gallant always uses TRNGs. Goofus always uses a high-quality PRNG (CSPRNG if you like) that's seeded with a TRNG. Everything else they do is identical. What are circumstances under which Goofus's conclusions would be meaningfully different than Gallant's?
Suppose I'm doing something where I need N(0,1) random variates. I sample from U(0,1) being sure to use a TRNG, do my transformations, and everything's good, right? But my sample isn't U(0,1), I'm only able to get float64s (or float32s), and my transform isn't N(0,1) as there's going to be some value x above which P(z>x)=0. The theory behind what I'm trying to do assumes N(0,1) and so all my p-values are invalid.
Nobody cares about that because we know that our methods are robust to this kind of discretization. Similarly I think nobody (most people) should care (too much) about having "only" 256 bits of entropy in their PRNG because our methods appear to be robust to that.
For new implementations, sure. But it's harder to change existing implementations (anything not already CommonMark-compatible will introduce unexpected changes to existing content if you switch to CommonMark), and especially for anything that's not being actively developed it's unlikely to ever change.
Is it? Why? If a NixOS module doesn’t support what you need, you can just write your own module, and the module system lets you disable existing modules if you need to. Doing anything custom this way still feels easier than doing it in an imperative world.
I can see your point that it can be daunting to have all the pain upfront. When I was using Ubuntu on my servers it was super simple to get things running
The problem was when I had to change some obscure .ini file in /etc for a dependency to something new I was setting up. Three days later I'd realise something unrelated had stopped working and then had to figure out which change in the last many days caused this
For me this is at least 100x more difficult than writing a Nix module, because I'm simply not good at documenting my changes in parallel with making them
For others this might not be a problem, so then an imperative solution might be the best choice
Having used Nix and NixOS for the past 6-7 years, I honestly can't imagine myself using anything than declarative configuration again - but again, it's just a good fit for me and how my mind works
In the NixOS scenario you described, what keeps you from finding an unrelated thing stopped working three days later and having to find what changed?
I’m asking because you spoke to me when you said “because I'm simply not good at documenting my changes in parallel with making them”, and I want to understand if NixOS is something I should look into. There are all kinds of things like immich that I don’t use because I don’t want the personal tech debt of maintaining them.
I think the sibling answer by oasisaimlessly is really good. I'd supplement it by saying that because you can have the entire configuration in a git repo, you can see what you've changed at what point in time
I'm the beginning I was doing one change, writing that change down in some log, then doing another change (this I'll mess up in about five minutes)
Now I'm creating a new commit, writing a description for it to help myself remember what I'm doing and then changing the Nix code. I can then review everything I've changed on the system by doing a simple diff. If something breaks I can look at my commit history and see every change I've ever made
It does still have some overhead in terms of keeping a clean commut history. I occasionally get distracted by other issues while working and I'll have to split the changes into two different commits, but I can do that after I've checked everything works, so it becomes a step at the end where I can focus fully on it instead of yet another thing I need to keep track of mentally
I just realised I didn't answer the first question about what keeps me from discovering the issues earlier
The quick answer is complexity and the amount of energy I have, since I'm mostly working on my homelab after a full work day
Some things also don't run that often or I don't check up on them for some time. Like hardware acceleration for my jellyfin instance stopped working at some point because I was messing around with OpenCL and I messed up something with the Mesa drivers. Didn't discover it until I noticed the fans going ham due to the added workload
I'm not really sure what your point is, but I'll try to take it in good faith and read it as "why doesn't docker solve the problem for it, since you can also keep those configurations in a git repo?"
If any kind of apt upgrade or similar command is run in a dockerfile, it is no longer reproducible. Because of this it's necessary to keep track of which dockerfiles do that and keep track of when a build was performed; that's more out-of-band logging. With NixOS I will get the exact same system configuration if I build the same commit (barring some very exotic edge cases)
Besides that, docker still needs to run on a system, which must also be maintained, so Docker only partly addresses a subset of the issue
If Docker works for you and you're not facing any issues with such a setup, then that's great. NixOS is the best solution for me
That’s all my point was, yeah. Genuinely no extra snark intended.
> it is no longer reproducible
The problem I have with this is that most of the software I use isn’t reproducible, and reproducible isn’t something that is the be all and end all to me. If you want reproducible then yes nix is the only game in town, but if you want strong versioning with source controlled configuration, containers are 1000x easier and give you 95% of the benefit
> docker still needs to run on a system
This is a fair point but very little of that system impacts the app you’re running in a container, and if you’re regularly breaking running containers due to poking around in the host, you’re likely going to do it by running some similar command whether the OS wants you to do it or not.
> if you want strong versioning with source controlled configuration, containers are 1000x easier and give you 95% of the benefit
For some I'm sure that's the case; it wasn't in my case.
I ran docker for several years before. First docker-compose, then docker swarm, finally Nomad.
Getting things running is pretty fast, but handling volumes, backups, upgrades of anything in the stack (OS, scheduler, containers, etc) broke something almost every time - doing an update to a new release of Ubuntu would pretty much always require backing up all the volumes and local state to external media, wiping the disk, installing the new version, and restoring from the backup
That's not to talk about getting things running after an issue. Because a lot of configuration can't be done through docker envs, it has to be done through the service. As a consequence that config is now state
I had an nvme fail on me six months ago. Recovering was as simple as swapping the drive, booting the install media, install the OS, and transfering the most recent backup before rebooting
Took about 1.5 hours and everything was back up and running without any issues
Not OP, and not a very experienced with NixOS (I just use Nix for building containers), but roughly speaking:
* With NixOS, you define the configuration for the entire system in one or a couple .nix files that import each other.
* You can very easily put these .nix files under version control and follow a convention of never leaving the system in a state where you have uncommitted changes.
I've written a dozen flakes because I want some niche behavior that the home-manager impl didn't give me, and I just used an LLM and never opened Nix docs once.
It's just declarative configuration, so you also get a much better deliverable at the end than running terminal commands in Arch Linux, and it ends up being less work.
Have you seen how bad the Nix documentation is and how challenging Nix (the language) is? Not to mention that you have to learn Yet Another Language just for this corner case, which you will not use for anything else. At least Guix uses a lisp variant so that some of the skills you gain are transferable (e.g. to Emacs, or even to a GP language like Common Lisp or Racket).
Don't get me wrong, I love the concept of Nix and the way it handles dependency management and declarative configuration. But I don't think we can pretend that it's easy.
The documentation is not great (especially since it tends to document nix-the-language and not the conventions actually used in Nixpkgs), but there are very few languages on earth with more examples of modules than Nix.
In Pattern: Defensively Handle Constructors, it recommends using a nested inner module with a private Seal type. But the Seal type is unnecessary. The nested inner module is all you need, a private field `_private: ()` is only settable from within that inner module, so you don't need the extra private type.
I haven't used Homebrew in a long time, but if I ever did it would be in the way that you describe (so far I've always found reasonable alternatives for the software I want). What I'm wondering is if this is entirely to support unsigned casks, why does Homebrew not simply resign the software itself at install time with an adhoc signature as though it had just built it?
If you don't use ANC, then why is an ANC issue that only appears on flights a reason for you to not buy a product? If someone said they have weird ears and the AirPods Pro 3 simply doesn't fit their ears, would that be a reason for you to not buy it even though it fits yours?
I'm fascinated by ASN.1, I don't know why it appeals to me so much but I find working with it oddly fun. I've always wanted to find the time to write an ASN.1 compiler for Rust, because for some reason all of the Rust implementations I've seen end up just either being derive macros on Rust structs (so going the other direction), or even just providing a bunch of ASN.1 types and functions and expecting you to manually chain them together using nom.
LaunchDaemons don't rely on GUI login state so they should come up. If you use LaunchAgents then they won't start this way, but LaunchDaemons should be enabled once the data volume is unlocked and booting finishes.
I imagine you could change the p-value test to randomly sample assignments generated via the exact same process that was used to generate the assignment used by the experiment, and as you run more and more iterations of this the calculated p-value should converge to the correct value, but then the question becomes is the p-value calculated this way the same as the p-value you'd get if you actually went ahead and used equiprobable assignment to begin with?
Ultimately, this all comes down to the fact that it's not hard to use true randomness for the whole thing, and true randomness produces statistically valid results, if you use true randomness for assignment then you can't screw up the p-value test, and so there's no reason at all to even consider how to safely use a PRNG here, all that does is open the door to messing up.
reply