There are 5 answers already that explain how it can be done. So "it can't be done" is a bold statement. Additionally, a tri-coin would face the same problem, since 6 is not a power of 3 as well.

@FrankW, think of the simple case that rejection sampling may take arbitrarily long to get an outcome in range (since the sequences can be arbitrarily long with a specific outcome), so your answer is also not correct about practicality

@FrankW, per my edits and comments i think your downvote is not appropriate anymore

Since the probability of taking arbitrarily long is going to 0 exponentially, rejection sampling is only impractical if you're proverbial Murphy. But in that case no problem is solvable at all on a computer, since a cosmic ray might flip a bit and crash the machine with higher probability than rejection sampling taking even 1000 tries.

@FrankW, no you are wrong, this can happen in every given interval (prove otherwise if you doubt this). What you state is the limit of the sequence towards infinity (which is sth different)

"Taking arbitrarily long" is a statement about the limit towards infinity. And I don't have the slightest idea, what you want to say with the first sentence.

@FrankW, i will explain to you. What you mention is that the set typical sequences (of given elementary probabilities) includes only the sequences that match these elementary probabilities. but each of those typical sequences can include arbitrarily long sub-sequence(s) of exactly same outcomes. Is this clear?

This answer is wrong: rejection sampling provably gives the correct distribution (even though the answers don't give the proof). I recommend you do some reading about that method.

As a way of explaining: all the long sequences split up evenly over the target values. All infinite sequences have probability zero, so that's not an issue either.

@Raphael, no you are wrong too. It is not about infinity either. Arbitrarily long means among others things that there is not a specific upper limit after which the sampling will be in range (amd i dont mean this in probability). Because if this was so, then there would be a deterministic method to math the event space of a die exactly to the event space of a coin. Rejection sampling is an approximation in probability. What happens if one wants to simulate the die faithfuly in each throw? Prove otherwise if u can. You can keep the reading to yourself because it seems you will need it.

I don't know your background, but if several people with a genre background tell you that you are wrong, you better think real hard and make a good argument as to why they are wrong. I don't know if you did the first, but certainly not the latter. To say it again: no, rejection sampling is not an approximation. It gives exactly the correct distribution (easy calculation), with expected constant runtime. Infinite worst-case runtime, but it terminates with probability one (easy calculation).

@Raphael Nikos is correct in that the best you can do is simulate with probability 1, which is not the same thing as being able to simulate. If you need a guarantee that the algorithm will terminate in a specific time (i.e. $\forall x, \exists T, \Box \mathrm{runtime}(A,x) \le T$), then no exact algorithm is possible — what is possible is only $\forall x, \Box \exists T, \mathrm{runtime}(A,x) \le T$.

@Gilles That may be true (see said other question) but I don't see Nikos making that point. Regarding details, note the gap between "infinite runtime" and "terminate in a specific time". In fact, we have guaranteed (a.s.) finite runtime (if no upper bound).

@Raphael, i'm sorry for being harsh, but you may understand how it seems. The fact is as Giles mentions that the simulation is probabilistic (i.e approximate) and of course in this sense Frank's answer (and yours is correct). My answer tackles another point (complementary if you like) to yours. The fact that the error in the probabilistic simulation is never zero. Because if so there would be a deterministic algorithm to match exactly the 2 event spaces (which do not match by dimensionality). So either the simulation will run arbitrarily long or will generate biased distribution (not fair die)

@Raphael, and Frank, let me tell you a little secret, if i was one of the first to answer this question i would probably use rejection sampling myself. So i decided to post another answer :)

Problem 1): "No finite runtime bound or wrong distribution" is correct; you don't say that in your answer. Problem 2): "probabilistic (i.e approximate)" -- that's not a common use of approximate (which makes your point hard to understand). Probabilistic algorithms are also tied to the notion of "being correct with certain probability" which does not apply here, so I would use neither term to descripe rejection sampling.

I used the new move comments to chat moderator tool

← 95 messages moved from Computer Science

... and I moved yesterday's discussion about that answer in the main chat room to this room, so that it's all in one place.

@Raphael rejection sampling is not correct in the sense that it isn't guaranteed to terminate (I refer you to yesterday's conversation about P=1 vs guaranteed)

@Gilles It is correct in the sense that "if it terminates, the result is correct". Since the premise is (practically) always fulfilled, that's good enough.

(Are we still talking about whether or not some post or comment on the question was accurate, or are we discussing the matter for its own sake?)

@Raphael that's called “partially correct”

@NikosM. Note that others do have a point that rejection sampling is partially correct (this is a technical term), in that whenever the algorithm terminates, it does give an exact result (exactly 1/6 chance of each value), not an approximate result.

If you modify the rejection sampling algorithm to quit the loop after a given number of times, then what you have is an algorithm with a termination guarantee but which is not correct, and instead gives an approximation of the desired result. But that modified algorithm is not called rejection sampling.

I need to go do things other than chat now.

Is "efficient in practice" a technical term? 'Cuz that's what @FrankW said.

@Gilles, correct rejection sampling is partially correct (when it terminates), did not say otherwise and in fact stated this in several comments i made here and there. i think this should be settled by now.

@Giles, On the other hand people stated several times that my answer was wrong even after providing more detailed analysis. Not happy about that

thankx for the discussion i will have to go too (rarely go into discussion unless absoutely necessary)

@WanderingLogic Not that I know; both components up to interpretation. "Constant expected time" probably fits the bill for most interpretations.