LESSWRONG
LW

Comment Permalink

The biased random generator is also just as likely to output 0000000000 as it is 0010111101.

This is the mistake.

If you actually do the maths the biased generator is significantly more likely to output 0000000000 than 0010111101.

For a much simpler example, suppose we run on two times. The random generator outputs 00 25% of the time, 01 25% of the time, 10 25% of the time and 11 25% of the time.

For the biased generator, we need calculus. First suppose its p(0) = x. Then p(00 | p(0) = x ) = x^2. Since we have what is essentially a uniform distribution over [0,1] (the presence of absence of a single point makes no difference) we need to integrate f(x) = x^2 over the interval [0,1], which gives and answer of p(00) = 1/3. The same method gives p(11) = 1/3 and p(01) = p(10) = 1/6.

The general rule, is that if we run it n times, for any k between 0 and n the chance of it outputting k 1s is 1/(n+1), and that probability is shared out evenly among all possible different ways of outputing k 1s (also derivable from calculus). Thus p(0000000000) = 9.1% while p(0010111101) = 0.043%.

uzalud13y00

Thanks, this is a great answer. It didn't occur to me that stateless generator with unknown p(0) will have such a "preference" for all-digits-are-same-sequences. p(ten zeros) = 1/11 if p(0) can be any number; but p(ten zeros)=1/1024 if p(0)=1/2.

See in context

1 Can you recognize a random generator?

by uzalud

28th Dec 2011

1 min read

1

I can't seem to get my head around a simple issue of judging probability. Perhaps someone here can point to an obvious flaw in my thinking.

Let's say we have a binary generator, a machine that outputs a required sequence of ones and zeros according to some internally encapsulated rule (deterministic or probabilistic). All binary generators look alike and you can only infer (a probability of) a rule by looking at its output.

You have two binary generators: A and B. One of these is a true random generator (fair coin tosser). The other one is a biased random generator: stateless (each digit is independently calculated from those given before), with probability of outputting zero p(0) somewhere between zero and one, but NOT 0.5 - let's say it's uniformly distributed in the range [0; .5) U (.5; 1]. At this point, chances that A is a true random generator are 50%.

Now you read the output of first ten digits generated by these machines. Machine A outputs 0000000000. Machine B outputs 0010111101. Knowing this, is the probability of machine A being a true random generator now less than 50%?

My intuition says yes.

But the probability that a true random generator will output 0000000000 should be the same as the probability that it will output 0010111101, because all sequences of equal length are equally likely. The biased random generator is also just as likely to output 0000000000 as it is 0010111101.

So there seems to be no reason to think that a machine outputting a sequence of zeros of any size is any more likely to be a biased stateless random generator than it is to be a true random generator.

I know that you can never know that the generator is truly random. But surely you can statistically discern between random and non-random generators?

Personal Blog

1

New Comment

55 comments, sorted by

top scoring

Click to highlight new comments since: Today at 6:05 AM

[-]benelliott13y230

The biased random generator is also just as likely to output 0000000000 as it is 0010111101.

This is the mistake.

If you actually do the maths the biased generator is significantly more likely to output 0000000000 than 0010111101.

For a much simpler example, suppose we run on two times. The random generator outputs 00 25% of the time, 01 25% of the time, 10 25% of the time and 11 25% of the time.

[-]uzalud13y00

[-]timtyler13y50

But surely you can statistically discern between random and non-random generators?

See DIEHARD.

[-]Cthulhoo13y20

I see a possible confusion in your post, in the sense that you have apparently fused two hypothesis into one: A is random A is fair

The two are not equivalent: A can be a random generator with p(0)!=50% or it can have p(0)=50% but output a very predictable string, e.g. 01010101010101010101...

Going back to your example if you hypothesis is A=(random et fair) then seeing the string 0000000000 can lower your belief in the statement (not for the "random" part, but for the "fair" part"). If your hypothesis was A=(random et p(0)= 0.00000000000000001%) then the string could raise your belief instead.

[-]uzalud13y00

Yes, I misspoke. The question is to discern between fair and biased random generators, not between random and non-random ones. As benelliott pointed out, stateless random bit generators seem to have quite unequal probability distributions of output sequences.

[-]snarles13y10

From a Bayesian viewpoint, no generator is inherently random. It is our inability to predict the outcome which makes the output "random."

[-]wedrifid13y20

From a Bayesian viewpoint, no generator is inherently random. It is our inability to predict the outcome which makes the output "random."

Bayesianism is agnostic on the subject - it's physics that has an opinion. A rather strong opinion.

[-]DanielLC13y00

Physics only tells you if you can predict the later output from the earlier output. It can't tell you what you know about the later output. If I flip a coin, it's random what it will land on before I flip it, but it has a probability near one of having landed on whatever I saw after I flipped it.

[-]Thomas13y20

I've asked before. What about radioactive atoms decay? Are they truly random or not?

Do you think there is a mechanism behind those apparently random pops of radium atoms in a jar?

[-]Maelin13y20

Here is my understanding (which I hope others will correct if it is mistaken).

Suppose I have a duplication machine, with an in slot and two out slots. You drop something in the in slot and two identical versions of it are produced in the out slots. They are down-to-the-atom identical at the moment of production - there is not an 'original' and a 'copy', there are 'two originals'.

Now I position the machine so that one out slot drops into a blue box and the other into a yellow box. I drop you into the machine. As you tumble down the in slot, what is your subjective expectation about what colour box you will end up in? It might be ~50% blue and ~50% yellow (with a small probability that the machine explodes or the boxes change colour or whatever).

In fact, 'you' experience both. But no single instance of you remembers landing in both a blue box and a yellow box. Instead, one instance of you remembers landing in a blue box, and the other remembers landing in a yellow box. Both of you remember a single continuous narrative thread, from entering the in slot, to landing in a coloured box.

There is no sense in which the you from before the experiment landed in one box but not the other and could have predicted which one with better information. Each instance of you might initially think, "Well, I remember falling into the in slot, and then I ended up here. So the other guy must be the copy". But this is false. There was one of you, and now there are two.

Similarly with quantum events. The universe bifurcates (trifurcates, whatever - this is obviously a simplification) and different instances of us experience each different possibility. Before a quantum experiment, it is nonsensical to try to make definitive predictions about "which" outcome we will experience. The feeling that this could/should be possible is an intuition based in the fact that we only see our own narrative thread running back into the past, we don't see all the other narrative threads of the different versions of us. Different instances of us will experience each outcome of the experiment.

After the experiment, we can ask "which instance are we?" But before the experiment, it is meaningless to ask "which instance will we be?"

[-]prase13y10

What does it mean "truly random"? If it means "indeterministic", in the sense of "there is no way to predict the outcome with certainty from any set of previously gathered data", then chances are that the radioactive decay is "truly random". However, this doesn't make the sentence

It is our inability to predict the outcome which makes the output "random."

false.

[-]Thomas13y10

What does it mean "truly random"?

That there is no finite algorithm behind, which would decide when which atom will explode.

In other words, that there is no hidden variables behind those events, which would cause the decay.

It is quite an unorthodox view in quantum mechanics, that those exist.

As far as I can see, the official view in QM is inherently "nonbayesian" in this sense. No hidden mechanism which would output the decay time of an uranium atom for example.

[-]DanielLC13y40

All of them will decay and all of them will not decay in different worlds.

Let's assume for the sake of argument that the Copenhagen interpretation is true. Before the particles decay, there is no way to tell which decay. It's random. After they decay, you can tell by looking. You know which ones decayed. It's not random at all.

Randomness is a state of the mind. All indeterminism tells you is that randomness must be a state of every mind that exists before the event.

Imagine a universe where it's always possible to tell the future from the past, but it's not always possible to tell what's on the right from what's on the left. This is deterministic, but if you rotate it 90 degrees, it isn't. A coordinate transformation can't be changing whether or not something is random, can it?

[-]Shmi13y10

This is deterministic, but if you rotate it 90 degrees, it isn't.

Time is not quite like space (or, in the PDE language, initial value problems are quite different from boundary value problems). There are QFT techniques that treat time as "imaginary space", but their applicability is quite limited and they certainly do not justify the view that "Randomness is a state of the mind", which is either untestable or manifestly false.

[-]prase13y00

initial value problems are quite different from boundary value problems

Could you be more specific, in what sense different?

In any case, final (or terminal?) value problems are the same as the initial value problems, PDE-wise.

[-]Shmi13y00

Could you be more specific, in what sense different?

Start with the obvious link, look for hyperbolic and elliptic PDEs and ways to solve them, especially numerically. The wave equation techniques are different from the Laplace equation techniques, though there is some overlap. Anyway, this is getting quite far from the original discussion.

In any case, final (or terminal?) value problems are the same as the initial value problems, PDE-wise.

Not quite. For example, the heat/diffusion equation cannot be run backwards, because it fails the uniqueness conditions with the t sign reversed. In a simpler language, you cannot reconstruct the shape of an ink drop once it is dissolved in a cup of water.

[-]prase13y00

I was mainly asking what differences are, in your opinion, important in the context of the present debate.

the heat/diffusion equation cannot be run backwards, because it fails the uniqueness conditions with the t sign reversed

1) You can run the diffusion equation backwards, only you encounter problems with precision when the solution exponentially grows.

2) Fundamental laws of nature are [second order in time and - edit:that's not true ] symmetric with respect to time reversal.

[-]Shmi13y20

I was mainly asking what differences are, in your opinion, important in the context of the present debate.

Well, we are quite a ways from the original context, but I was commenting on that treating time and space on the same footing and saying that future and past are basically interchangeable (sorry for paraphrasing) is often a bad assumption.

You can run the diffusion equation backwards, only you encounter problems with precision when the solution exponentially grows.

In other words, it is ill-posed and cannot be used to recover the initial conditions.

Fundamental laws of nature are second order in time and symmetric with respect to time reversal.

This is a whole other debate on what is fundamental and what is emergent. Clearly, the heat equation is pretty fundamental in many contexts, but its origins can be traced to the microscopic models of diffusion. There are other reasons why the apparent time reversal might not be there. For example, if you take the MWI seriously, the branching process is has a clear time arrow attached to it.

[-]prase13y00

In other words, it is ill-posed and cannot be used to recover the initial conditions.

With precise measurement you can. Once started to be solved numerically different initial conditions (for the standard diffusion equation) are all going to yield constant function after some time due to rounding errors, so the information is lost and can't be recovered by time-reversed process. But as a mathematical problem the diffusion equation with reversed time is well defined and has unique solution nevertheless.

[-]Shmi13y10

From what I recall, the reverse-time diffusion u_t=-u_xx is not well posed, i.e. for a given solution u(t), if we perturb u(0) by epsilon, there is no finite t such that the deviation of the new solution from the old one is bounded by epsilon*e^t. A quick Google search confirms it: (pdf, search inside for "well posed")

[-]prase13y00

I didn't realise that "well-posed" is a term with a technical meaning. The definition of well-posedness I have found says that the solution must exist, be unique and continuously depend on the initial data, I am not sure whether this is equivalent to your definition.

Anyway, the problem with the reverse dissipation equation is that for some initial conditions, namely discontinuous ones, the solution doesn't exist. However, if a function u(x,t) satisfies the diffusion equation on the interval [t1,t2], we can recover it completely from knowledge of not only u(x,t1), but also from u(x,t0) with any fixed t0 lying between t1 and t2.

[-]pragmatist13y00

A small nitpick: The Schrodinger equation is not second order in time.

[-]prase13y00

The Dirac one as well. Corrected.

[-]DanielLC13y00

Let me start over.

You could define "randomness" to mean indeterminism. If you do so, you would call the results of a fair, indeterministic coin toss random. Even so, if I tossed such a quantum coin, and you saw it land on heads, you would not be willing to bet even money that it landed on tails. P(coin landed on heads|your current information) ≈ 1. When you're finding expected value, this is all that matters.

[-]Shmi13y20

As far as I can see, the official view in QM is inherently "nonbayesian" in this sense. No hidden mechanism which would output the decay time of an uranium atom for example.

Indeed there is no hidden "time until I decay" number hidden inside each radioactive atom (based on some pseudo-random generator, or what have you), but how is it related to Bayes? And what do you mean by "official"?

[-]Thomas13y00

what do you mean by "official"?

I mean the *prevailing view among (quantum) physicists that:

"Indeed there is no hidden "time until I decay" number hidden inside each radioactive atom "

You said it.

but how is it related to Bayes?

It is, while one thinks, that he must update on every evidence. You can't update anything on a decay of the particular radioactive atom. Could be another one, but it just wasn't and what is to update? Nothing, if that was a "truly random" event.

Either it wasn't, either you have nothing to update based on this evidence.

[-]Shmi13y20

prevailing view among (quantum) physicists

This "view" has been experimentally tested in a simpler case of two-state systems as Bell's inequality, though I do not remember, off-hand, any tests related to radioactive decay.

It is, while one thinks, that he must update on every evidence. You can't update anything on a decay of the particular radioactive atom.

You can update your estimate of the element's half-life, if nothing else.

[-]Thomas13y00

You can update your estimate of the element's half-life, if nothing else.

You can update the half-life from the TIME of the decay. But nothing from the fact that it was the atom number 2 and not the number 1 or any other.

This "view" has been experimentally tested

I know. That's way I keep bringing up this "true random" case.

[-]Normal_Anomaly13y10

If I understand correctly, there is no physical difference between atom 2 and atom 1. There just is no fact of the matter to update on.

[-]Thomas13y10

Say you have two diamonds, both marked with a million uranium 238 atoms.

You can measure in WHICH diamond the first decay will occur. An evidence you can't use it for any update then.

[-]prase13y00

That there is no finite algorithm behind, which would decide when which atom will explode.

We can test algorithms which we use to predict which atom would explode and when. The variables are part of the theory, not of the atoms. Absence of hidden variables effectively means that there is no regularity such that we could infer a law that would predict the state of an arbitrary system at time t1 with certainty* from observations made at time t0 < t1. Nevertheless any selected atom* is either going to explode or isn't at a given time, and we can observe which was the case afterwards. Bayesianism doesn't prohibit updating our beliefs about events after those events happened, in fact it doesn't say anything at all about time. The "inherent randomness" of radioactive decay doesn't make the uncertainty non-Bayesian in any meaningful way.

That said, I am afraid we may start to argue over the silly problem of future contingents and over definitions in general. The right question to ask now is: why do you want to distinguish truly random numbers from apparently random ones? The answer to the question about the quality of quantum randomness may depend on that purpose.

*) Although I know that certainty is impossible to achieve and atoms are indistinguishable, I have chosen to formulate the sentences the way I did for sake of brevity.

[-]Luke_A_Somers13y00

There are many forms of Bayesianism, and I've only seen a few that are married to the notion that ALL uncertainty is due to ignorance and none due to nondeterminism.

QM, incidentally, even in MWI, is nondeterministic in the sense that you don't know which of the outcomes you personally will experience.

[-]wedrifid13y10

QM, incidentally, even in MWI, is nondeterministic in the sense that you don't know which of the outcomes you personally will experience.

Yes I do. All of them. What I cannot predict is what my observation will be when it is determined by a quantum event that has already occurred but with which I have not yet had any interaction. That's no more deterministic than a 'for loop' in a computer - self reflective code before the loop can predict exactly what is going to happen in the future but code within the loop has to do a lookup of the counter variable (or a side effect) if it is going to work conditionally.

[-]Shmi13y10

Yes I do. All of them.

That's not a testable prediction, or a useful one.

[-]pragmatist13y-40

That's not a testable prediction, or a useful one.

It is in fact a testable prediction.

[-]Shmi13y00

I cannot find anything in that entry that suggests that experiencing all possible outcomes can be experimentally tested. Feel free to elaborate.

[-]pragmatist13y10

Sorry, I should have elaborated, but I was short on time when I wrote the comment.

Let's say you set up a sequence of quantum experiments, each of which has a 90% chance (according to the Born probabilities) of killing you instantly and a 10% chance of leaving you unharmed. After a number of such experiments you find yourself alive. This is something you would expect if some form of MWI were true and if all surviving future selves had conscious experience continuous with yours. It is not something you would expect if a collapse interpretation were true, or if MWI combined with some sort of indeterminism (governed by Born's rule, presumably) about which future self continues your conscious experience were true. So such a sequence of experiments should lead you to update in favor of MWI + experience all possible outcomes.

[-]Shmi13y00

Sorry, I am having trouble taking quantum suicide/immortality seriously. How is this different from The Simple Truth:

Inspector Darwin looks at the two arguers, both apparently unwilling to give up their positions. “Listen,” Darwin says, more kindly now, “I have a simple notion for resolving your dispute. You say,” says Darwin, pointing to Mark, “that people’s beliefs alter their personal realities. And you fervently believe,” his finger swivels to point at Autrey, “that Mark’s beliefs can’t alter reality. So let Mark believe really hard that he can fly, and then step off a cliff. Mark shall see himself fly away like a bird, and Autrey shall see him plummet down and go splat, and you shall both be happy.”

If there is even a remote chance that Mark would fly, he probably flew in almost every universe he survived.

Now, suppose one really dedicated and overzealous grad student of Tegmark performs this experiment. The odds of the MWI being a good model might go up significantly enough for others to try to replicate it in the tiny subset of the universes where she survives. As a result, in a tiny minority of the universes Max gets a Nobel prize for this major discovery, whereas in most others he gets sued by the family of the deceased.

If EY believed in this kind of MWI, he would not bother with existential risks, since humanity will surely survive in some of the branches.

[-]Vladimir_Nesov13y00

See this post.

[-]pragmatist13y00

Now, suppose one really dedicated and overzealous grad student of Tegmark performs this experiment. The odds of the MWI being a good model might go up significantly enough for others to try to replicate it in the tiny subset of the universes where she survives. As a result, in a tiny minority of the universes Max gets a Nobel prize for this major discovery, whereas in most others he gets sued by the family of the deceased.

I'm not suggesting that this is a scientific experiment that should be conducted. Nor was I suggesting you should believe in this form of MWI. I was merely responding to your claim that wedrifid's position is untestable.

Also, note that a proposition does not have to meet scientific standards of interpersonal testability in order to be testable. If I conducted a sequence of experiments that could kill me with high probability and remained alive, I would become pretty convinced that some form of MWI is right, but I would not expect my survival to convince you of this. After all, most other people in our branch who conducted this experiment would be dead. From your perspective, my survival could be an entirely expected fluke.

If EY believed in this kind of MWI, he would not bother with existential risks, since humanity will surely survive in some of the branches.

I'm fairly sure EY believes that humanity will survive in some branch with non-zero amplitude. I don't see why it follows that one should not bother with existential risks. Presumably Eliezer wants to maximize the wave-function mass associated with humanity surviving.

[-]Shmi13y00

If I conducted a sequence of experiments that could kill me with high probability and remained alive, I would become pretty convinced that some form of MWI is right, but I would not expect my survival to convince you of this.

Probably, but I'm having trouble thinking of this experiment as scientifically useful if you cannot convince anyone else of your findings. Maybe there is a way to gather some statistics from so called "miracle survival stories" and see if there is an excess that can be attributed to the MWI, but I doubt that there is such excess to begin with.

Presumably Eliezer wants to maximize the wave-function mass associated with humanity surviving.

Why? The only ones that matter are those where he survives.

[-]wedrifid13y10

Presumably Eliezer wants to maximize the wave-function mass associated with humanity surviving.

Why? The only ones that matter are those where he survives.

If if he doesn't care at all about anyone else at all. This doesn't seem likely.

[-]pragmatist13y00

Why? The only ones that matter are those where he survives.

This seems like a pretty controversial ethical position. I disagree and I'm pretty sure Eliezer does as well. To analogize, I'm pretty confident that I won't be alive a thousand years from now, but I wouldn't be indifferent about actions that would lead to the extinction of all life at that time.

[-]wedrifid13y10

I'm pretty confident that I won't be alive a thousand years from now, but I wouldn't be ambivalent about actions that would lead to the extinction of all life at that time.

Indifferent. Ambivalent means, more or less, that you have reasons for wanting it either way as opposed to not caring at all.

[-]TheOtherDave13y00

Well, presumably he wouldn't be ambivalent as well as not being indifferent about performing/not-performing those actions.

[-]pragmatist13y00

Thanks. Corrected.

[-]ArisKatsaris13y-10

Why? The only ones that matter are those where he survives.

If they don't matter to you, that still doesn't necessitate that they don't matter to him. Each person's utility function may care about whatever it pleases.

[-]dlthomas13y-30

QM, incidentally, even in MWI, is nondeterministic in the sense that you don't know which of the outcomes you personally will experience.

This is broken because

which of the outcomes you personally will experience

is incoherent in the context of MWI. There is a "you" now, on this side of the event. There will be many people labeled "you", on the other side. There is no one person on the other side that corresponds to "you personally" while the event is something you can say "will" about - at that point, it's "did".

[-]Luke_A_Somers13y10

Congratulations! You have constructed an interpretation of what I said that doesn't make sense.

Why don't you go back and try doing it the other way?

[-]dlthomas13y00

Which other way?

[-][anonymous]13y00

Assume for now that the universe is the expression of a computable function. Then there exists a universal turing machine with a binary alphabet that computes this function. By compressing its input we can get a single number identifying our universe. If we knew this number and hat enough computing power we could then compute the exact timepoint of the radioactive decay of any single atom. But the number in itself would be completely random, meaning it would not be itself determined by anything else. It's just the universe that happened to have us as part of its execution. Would you count that as "truly random" or not?

You could of course argue that the universe might not in fact be a computable function. But that claim would go far beyond just random atomic decay since we could in principle encode the time points of all radioactive decays ever into the initial number from which to create our universal turing machine.

[-]wedrifid13y00

But the probability that a true random generator will output 0000000000 should be the same as the probability that it will output 0010111101, because all sequences of equal length are equally likely.

With a fair random generator:

p(0000000000) = 1/2^10
p(1000000000) = 1/2^10
p(0100000000) = 1/2^10
p(0010000000) = 1/2^10

The numbers produced are independent of each other and for our purposes we don't care about the order. The relevant thing is how likely it is is to produce a given total number of zeroes or ones.

p(just one 1) = 10/2^10; A whole heap more likely!

So the chance that the generator is fair is rather slim. You can calculate just how slim by simply applying bayes rule (and doing some integration).

On a related note if you role two six sided dice you are just as likely to get two sixes as you are to get a three and a five. But if you are playing Settlers of Catan and put all your settlements next to the twelve instead of the eight then you are probably going to lose.

[-]Quinn13y00

p(just one 1) = 1/2^9; A whole heap more likely!

Actually p(just one 1) = 10/(2^10).

if you role two six sided dice you are just as likely to get two sixes as you are to get a three and a five.

Nitpick: this is true if by "a three and a five" you mean (that the dice are labeled and) "die A comes up 3, and die B comes up 5", but it's false as written (and in games like Settlers, the identities of simultaneously thrown dice are not tracked).

[-]wedrifid13y00

(and in games like Settlers, the identities of simultaneously thrown dice are not tracked).

They are tracked actually, at least in the latest version - the only one worth playing. The red one determines whether or not you qualify for a bonus card. So yes, obviously I mean "a three and then a 5". If also considering a five and then a three then the point becomes even stronger.

[-]uzalud13y00

Hm. So the only relevant measure is the prevalence of zeros, because the generators are stateless (n+1st digit does not depend on the nth digit)?

But what if the generator B was not necessarily stateless?

Moderation Log