Discussion on answer by Nikos M.: How to simulate a die given a fair coin

12:57 PM

6

Q: How to simulate a die given a fair coin

Suppose that you're given a fair coin and you would like to simulate the probability distribution of repeatedly flipping a fair (six-sided) die. My initial idea is that we need to choose appropriate integers $k,m$, such that $2^k = 6m$. So after flipping the coin $k$ times, we map the number enco...

Should we protect this one? The quality of new answers is deteriorating.

FrankW

1:33 PM

@Nikos M. I still don't understand what you want to say.

And given that we are still discussing the matter, you can hardly claim that I have accepted your post as correct by now.

David Richerby

2:07 PM

@FrankW I've no objection to protection. Would it help much? One of the poor new answers is by an established user; the other isn't.

Raphael

@FrankW Of the two new answers I see (Nikos and Emanuele), one is wrong but the other has some merit.

@DavidRicherby That, too; protection only helps with lowest-rep users. Locking does more, but that's hardly appropriate. The volume we have now can and should be dealt with by community moderation, imho. Downvote crap and it vanishes.

FrankW

I also remembered the one before that, which is just a subset of what's been posted before.

Raphael

@FrankW The answers and comment indicate, though, that your answer is not elaborate enough to be clear to many who are interested in the topic. That can, but does not have to, be a reason for some editing.

David Richerby

@Raphael I think the two answers Frank and I are talking about are Nikos's (wrong) and Sohcahtoa82's (strict subset of Frank's). Emanuele's answer looks fine to me.

Raphael

8:41 PM

@FrankW Do you get what Nikos' problem is with the die question? He's pretty convinced (unfortunately quite a bit angry, not to say arsey, too).

Gilles

@Raphael he's also mostly right (but expressing himself badly, either because he's confused or because he's not good at being clear)

Raphael

@Gilles He's clearly wrong in stating that rejection sampling would only approximate the distribution.

@Gilles He has some correct statements in there, but his conclusions are mostly false. E.g. the introductory sentence of his answer, "Unfortunately one cannot (faithfuly) simulate a (fair) die using (sequences of) fair coin(s).", which he keeps referring to.

I honestly don't see how to fix his language so that truth remains.

Gilles

@Raphael this is correct

you can only do it probabilistically

Raphael

Huh?

Gilles

the algorithm terminates with probability 1, but it isn't guaranteed to terminate

Raphael

8:50 PM

That's the same, in practice (which is all @FrankW claims).

Also, that's not the point Nikos makes.

He writes, "But it will still have an amount of error or mis-match of probabilities." as his main argument, and that's wrong.

(I'm a bit fuzzy about the real different between "almost surely" and "always", especially in discrete domains. Yes, an infinite computation exists; but it doesn't happen, ever. Seems like the 0.9999... = 1 thing to me.)

Gilles

@Raphael there's a deterministic algorithm postprocessing the output of a probabilistic oracle

there is no computable function that turns a fair coin into a fair 6-sided die

there is a function which terminates for a set of oracle outputs with measure 1, but it is not the set of all oracle outputs

Raphael

@Gilles True. So? Nobody claims that.

Gilles

@Raphael yes: FrankW and you, in the comments. Though it's not very clear whether you're actually claiming that, or only that there is a function that terminates with probability 1

Raphael

Frank says, "this does it in practice" (without going into detail). Nikos says, "no". I maintain Nikos is wrong, even though some of his concern may be true.

Gilles

this could make a fine Computer Science question btw

Raphael

8:59 PM

@Gilles What now?

Gilles

Where Nikos is wrong is his claim that it doesn't work in practice. It works in practice, even if it doesn't work in theory, because in practice, if something has probability 1, it happens.

Raphael

@Gilles I don't think we do since we both know better. Maybe some careless comment can be read that way.

@Gilles Also in theory, by the way. You just have to go beyond comfy-cozy TM-land.

Gilles

@Raphael of course there's a theory in which it works! But there's also a relevant theory in which it doesn't.

Raphael

@Gilles In that theory, there are no dice so the question about simulating one is moot.

Gilles

Oracle machine

In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any complexity class. Even undecidable problems, like the halting problem, can be used. == Oracles == An oracle machine can be conceived as a Turing machine connected to an oracle. The oracle, in this context, is an entity capable of solving some problem, which for example may be a decision problem or...

Raphael

9:08 PM

(By the way, I note that nobody mentioned quite real concerns regarding practicality, namely "where do you get your random bits?" and, as a follow-up, "does this maintain good properties of my PRNG?"

Gilles

@Raphael “where do you get your random bits” has a whole tag on Cryptography: entropy

Raphael

@Gilles As long as you allow only deterministic oracles, no dice. As soon as you allow random (not non-deterministic!) oracles we are in probability-land. (Or not? I mean, it's certainly possible to define the notion of deterministic algorithms with a random oracle, but that seems ... silly.)

Gilles

“does this maintain good properties”: what properties? The thread handles the uniform distribution property.

@Raphael ???

Raphael

@Gilles I'm sure it does. Nobody mentioned that tag (on that question thread), either.

Gilles

deterministic algorithms with a random oracle are ubiquitous

@Raphael because the question is not about that

Wandering Logic

9:11 PM

Nikos' answer appears incorrect to me in two regards. (1) He says "Rejection sampling may provide an approximate simulation indeed. But it will still have an amount of error or mis-match of probabilities." That's just incorrect as far as I can see. If rejection sampling returns a result it will have exactly the same distribution as the 6-sided die.

No?

Raphael

@Gilles PNGRs are only accurate up to some level of scrutiny. There are famous examples when the original sequence was "good", but certain ways of using it produced "bad" sequences of otherwise distributed numbers. So a reasonable question would be, given PRNG A, are sequences produced by rejection sampling still good?

Gilles

@WanderingLogic yes, that part is either wrong or confusing, depending on the meaning of “approximate”

if it's approximate as in getting an approximately uniform distribution, then rejection sampling doesn't do that

Wandering Logic

(2) He says that the claim "in practice" is wrong. But by "in practice" Frank W meant "with probability 1 and mean number of trials 4/3".

Which is about as close to "useful in practice" as I can imagine.

Gilles

if it's approximate as in a terminating approximation (i.e. bounded number of iterations) of the non-terminating loop of rejection sampling, then it's correct

but I guess the second meaning is esoteric to most people (and quite possibly to Nikos as well)

@WanderingLogic yes, I agree, his claim about impracticality is wrong

Wandering Logic

@Gilles It's worse than esoteric to me. I'm a systems guy so the subtlty of "probability 1 is not the same as certain" is lost on me.

Gilles

9:15 PM

@WanderingLogic have you heard of Maxwell's demon?

Raphael

@Gilles I have never heard the term "approximation" in that sense.

Gilles

Denotational semantics

In computer science, denotational semantics (initially known as mathematical semantics or Scott–Strachey semantics) is an approach of formalizing the meanings of programming languages by constructing mathematical objects (called denotations) that describe the meanings of expressions from the languages. Other approaches to providing a formal semantics of programming languages include axiomatic semantics and operational semantics. Broadly speaking, denotational semantics is concerned with finding mathematical objects called domains that represent what programs do. For example, programs (or program...

Raphael

@WanderingLogic Seconded. "terminates with probability 1" means that the algorithm is as likely to loop as it is to roll a 7 on a six-sided die.

Gilles

@Raphael no

Maxwell's demon

In the philosophy of thermal and statistical physics, Maxwell's demon is a thought experiment created by the physicist James Clerk Maxwell to "show that the Second Law of Thermodynamics has only a statistical certainty". It demonstrates Maxwell's point by hypothetically describing how to violate the Second Law: a container of gas molecules at equilibrium is divided into two parts by an insulated wall, with a door that can be opened and closed by what came to be called "Maxwell's demon". The demon opens the door to allow only the faster than average molecules to flow through to a favored side of...

Raphael

@Gilles I know denotational semantics, but I won't read the whole article to find the fragment you mean.

Gilles

9:16 PM

@Raphael search for approxim

Wandering Logic

@Raphael Yes, I'm reading far more into the question than the OP put there. If the OP clearly understood the difference between a process and a thread (or between a processor and a core) then OP would not have needed to ask a question.

Raphael

@Gilles I don't see any use that comes close to the meaning "terminates only with probability 1".

Gilles

@Raphael the two aren't directly related

Raphael

@Gilles I don't even see a use close to "does not terminate".

@Gilles How does this apply here? The situation is similar (ignoring that we know our model perfectly whereas physicists only know approximations of reality): there is a process/computation that ensures entropy to increase/infinite runtime, but it doesn't happen. The demon does not exist (if the probability 0 part is true).

Gilles

@Raphael a potentially infinite loop is approximated by a loop that terminates after N iterations.

The approximation converges to the original loop when N→∞

Raphael

9:25 PM

@Gilles That's a use of the term compatible with other common uses, but that is not what happens for rejection sampling. It is what Nikos claims (imho), which is wrong.

Gilles

defining a topology in which this convergence occurs was one of the foundations of denotational semantics

I'm not going to devote more time on this in a chatroom. If you care, cs.stackexchange.com/questions/ask

Raphael

Sounds a bit like a precursor of lattice/fixpoint theory? Right direction?

Gilles

@Raphael not a precursor, it's the same theory

or the same ballpark at least

Raphael

@Gilles Good call. Neither the question nor Nikos' contribution (let alone his behaviour) justify several man-hours of fruitless discussion.

@Gilles Okay. I've perceived lattice theory to be a bit broader; but somebody certainly came up with it first.

Wandering Logic

@Gilles Yes, I've heard of Maxwell's demon. And I've also heard of Landauer's Principle which shows that the demon must either consume energy (i.e. the system isn't closed) or generate entropy. (As described in the "criticisms" section of the Maxwell's demon wikipedia article.)

Gilles

9:32 PM

@WanderingLogic our computers have a power source, so consuming energy isn't a problem

Wandering Logic

But it's all navel gazing anyway. There's no hypothesized demon in the case of rejection sampling.

The probability of eventually generating an answer is 1. The probability of not terminating is 0. Not almost 0. Not 0 plus an infinitesmal hyper-real. 0.

I like philosophy.se as much as the next guy, and I am rarely accused of being practical or down to earth, but this is just too esoteric and subtle for me.

Wandering Logic is now going to go take a random walk. What is the probability he will return to his desk?

Gilles

@WanderingLogic The Computer has called and wants your geek license back

Raphael

@WanderingLogic Will you walk in 2D or 3D?

@Gilles Can the computer explain to us the difference between "always" and "almost surely" in terms what to expect when crossing the street (or an scenario tangible to us)? If no, it has no business revoking any licenses and has more thinking to do.

Gilles

9:48 PM

@Raphael The Computer most definitely doesn't explain anything. Proceed to the nearest extermination center.

Raphael

@Gilles Damn. On to the next clone.

Wait, did you....? Computer, I think @Gilles is hiding a nano-probe in his pocket! Do you really want to let him near that circuit board of yours?

Oh. Turns out I'm all out of clones. Bye, I guess.

Wandering Logic

10:06 PM

@Raphael Unfortunately for you, I live in Illinois, USA. People in neighboring states call people from Illinois "flatlanders" because it is a big, completely flat, 2-dimensional grid of corn and soy fields. Thus I will be returning an infinite number of times. (But only with probability 1, so I guess it's not certain.)

FrankW

10:31 PM

Having read over the discussion regarding the die question, I'll just say that I get @Gilles point. But I definitely didn't see that argument in Nikos answer or comments.

Transcript for

Discussion on answer by Nikos M.: How…