29
votes
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
14
votes
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
12
votes
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$...
- 236
12
votes
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$...
D.W.♦
- 141k
11
votes
Accepted
Generating random words by grammar
Your process is a textbook example of a branching process. Starting with one $E$, we have an expected $3/2$ many $F$s, $9/4$ many $T$s, and so $9/8$ many remaining $E$s in expectation. Since $9/8 > ...
- 270k
10
votes
Accepted
What are Markov chains?
A Continuous-time Markov Chain can be represented as a directed graph with constant non-negative edge weights. An equivalent representation of the constant edge-weights of a directed graph with $N$ ...
- 17.3k
9
votes
Accepted
Returning a random subset with length k of N strings while only storing at most k of them
Use reservoir sampling. This is a good description in Wikipedia, or in Knuth.
Let's start with the simple case, where $k=1$. You always have one string in memory. When you read the first string, ...
D.W.♦
- 141k
9
votes
Accepted
Why is ZPP = RP ∩ co-RP?
The solution is given in the link provided by you in wikipedia article ZPP. See the section Intersection Definition in the link. You need to know about Markov's Inequality though.
Markov's inequality ...
- 4,747
8
votes
What are Markov chains?
Markov Chains come in two flavors: continuous time and discrete time.
Both continuous time markov chains (CTMC) and discrete time markov chains (DTMC) are represented as directed weighted graphs.
...
- 81
8
votes
Accepted
What do we know about $NP \cap co-NP$?
There is no decision problem that is (unconditionally) known to be in $coNP \setminus NP$. If we had a decision problem that we could prove is in $coNP$ and could prove is not in $NP$, then we would ...
D.W.♦
- 141k
8
votes
Accepted
What is the chance that this code terminates?
This is an example of a branching process. The behavior of a branching process depends on the expected number of children, which in your case is $1.25 > 1$. When this number is at most 1, the ...
- 270k
8
votes
Accepted
Reservoir sampling algorithm probability
The whole reason for performing this sampling method is to get an uniform sample even if the population size is unknown at the start. So, if this method works, the probability cannot be skewed.
What ...
- 6,978
7
votes
Accepted
Understanding Expected Running Time of Randomized Algorithms
There are two notions of expected running time here. Given a randomized algorithm, its running time depends on the random coin tosses. The expected running time is the expectation of the running time ...
- 270k
7
votes
How to simulate a die given a fair coin
An alternative to rejection sampling (as described in FrankW's answer) is to use a scaling algorithm, that takes into account an answer of [7,8] as if it was another coin flipping.
There is a very ...
- 203
7
votes
Accepted
Mutual information intuition
Mutual information tells you how much you learn about $X$ from knowing the value of $Y$ (on average over the choice of $Y$). In other words, mutual information measures how many fewer bits you need to ...
- 2,497
7
votes
What is the best you can do with a noisy message?
Suppose that $k \ll n$. In that case, your friend can send you the index of the first door containing a treasure. Of the $k$ numbers you get, you pick the smallest one. If $k$ is small enough compared ...
- 270k
7
votes
Accepted
How can Karger's algorithm (and other randomized algorithms) be used in practice?
Karger's algorithm is a randomized algorithm. It has a small probability of error, but that probability can be made arbitrarily (exponentially) small simply by repeating the approach.
If we do one ...
D.W.♦
- 141k
7
votes
Why are forks in the Blockchain eventually resolved?
If we simplify and assume that each miner randomly guesses a hash (as opposed to being more systematic) and we discretize time, say into minutes, then each minute each miner is hoping to "roll" the ...
- 11.8k
7
votes
Accepted
Expected length of a random walk on a line
The behavior when $p = 1/2$ and when $p > 1/2$ is rather different. When $p > 1/2$, in expectation you move $2p-1$ steps to the left, so you will hit the origin after a linear number of steps. ...
- 270k
7
votes
Generating random words by grammar
As Yuval has noted, this way of randomly generating recursive data structures is known to (usually) end up with an infinite expected size.
There is, however, a solution to the problem, that allows ...
- 370
6
votes
What does the "principle of deferred decisions" formally mean
The principle of deferred decisions is the concept that we have two ways to make a random choice both of which are equivalent.
One way is that you can toss a coin yourself at the exact step when you ...
- 1,168
6
votes
Accepted
What is the complexity of a variation of the Coupon collector's problem?
When $m$ is much larger than $n$, the expected number of trials is basically linear in $n$. We can make this more precise, as shown below.
Let $T_n$ be the random variable which counts the number of ...
- 13.2k
5
votes
Accepted
Probabilty that quicksort partition creates an imbalanced partition
If $\alpha=0.5$, then $1-2 * 0.5 = 0$, which says that the smaller subarray cannot have length greater than half the original, since then it would be the larger subarray.
If $\alpha=0$, then $1-2 * 0 ...
- 166
5
votes
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
5
votes
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
5
votes
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
5
votes
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
5
votes
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
5
votes
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
5
votes
Accepted
Why arrival process of packets at a switch is not a Poisson Process?
"new flow arrivals" means "arrivals of new flows". A flow is a TCP connection (roughly); each individual TCP connection is a separate "flow". So, this is talking about new TCP connections, and the ...
D.W.♦
- 141k
Only top scored, non community-wiki answers of a minimum length are eligible