# Tag Info

### How to simulate a die given a fair coin

What you can do, is to employ a method called rejection sampling: Flip the coin 3 times and interpret each flip as a bit (0 or 1). Concatenate the 3 bits, giving a binary number in $[0,7]$. If the ...
• 6,519
Accepted

### Why is adding log probabilities faster than multiplying probabilities?

Also, the Wikipedia page (https://en.wikipedia.org/wiki/Log_probability) is confusing in this respect, stating "The conversion to log form is expensive, but is only incurred once." I don't understand ...
• 626
Accepted

### How to simulate a die given a fair coin

To have a slightly more efficient method than the one pointed out by @FrankW but using the same idea, you can flip your coin $n$ times to get a number below $2^n$. Then interpret this as a batch of $m$...
Accepted

### Is it possible to simulate a fair coin with a finite number of tossing of a biased one?

No, it's not possible. Suppose the bias of the coin is $1/3$, and suppose you could guarantee termination. Then there would be some $n$ such that this always terminates after $n$ coin flips. Let $S$...
• 141k
Accepted

• 166

### Returning a random subset with length k of N strings while only storing at most k of them

This problem is covered in The Art of Computer Programming. I can't recall exactly where, but the algorithm is pretty easy to understand when you know the trick. Let $l$ be the number of lines read ...
• 18.9k
Accepted

### Conditional Probabilities as Tensors?

This is definitely possible, although the tensor has of course certain additional structure (constraints). If you consider the following conditional defined for a categorical response $Y$ on ...
• 166

### About sorting numbers in linear time

If your input consists of integers, that is your elements are from the set $\mathcal{U}=\{0,\ldots,u-1\}$, you can sort faster than $O(n\log n)$ assuming your model of computation is the word RAM. ...
• 11.9k
Accepted

### Turn biased random number generator into uniform

For general $p$ you can't generate a random bit using a finite number of samples. Indeed, suppose you could do it using $n$ samples. Let $c_k$ be the number of inputs of Hamming weight $k$ which will ...
• 270k

### Chernoff bound when we only have upper bound of expectation

Yes, we can get a bound like this. To see why, we will need to look a little more closely at how Chernoff bounds are proved. A relatively standard form of this kind of tail bound would assume that ...
• 2,886
Accepted

### Probabilistic algorithm with two-sided error

Monte Carlo methods are inherently not one-sided, though it's dubious whether they're usually two-sided. The general idea is that in order to estimate the expectation of a random variable $X$, we take ...
• 270k