29
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 number is in $[1,6]$, take it as a die roll.
Otherwise, i.e. if the result is $0$ or $7$, repeat the flips.
Since $\frac 68$ of the possible outcomes lead to ...
14
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 this, because I think you would need to take the log of every term independently before adding. What am I missing?
If you just want to compute $P(A_1)\ldots P(...
12
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$ die flips, where $m$ is the largest number so that $6^m < 2^n$ (as already said, equality never holds here). If you get a number greater or equal to $6^m$ ...
12
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$ denote the set of flip-sequences that causes your algorithm to output 0 (so that $\overline{S}$ is the set of flip-sequences that causes your algorithm to ...
11
The algorithm works, but to understand why, you need to know basic probability theory. The idea is to prove by induction that at step $t$, the currently selected algorithm is uniform among the first $t$ elements. This is clearly the case when $t=1$. Assume now the induction hypothesis for time $t$, and consider what happens at time $t+1$. With probability $1/...
11
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 > 1$, it is not surprising that your process often failed to terminate.
To gain more information, we need to know the exact distribution of the number of $E$-...
10
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$ nodes is as an $N \times N$ matrix. The Markov property (that the future states depend only on the current state) is implicit in the constant edge weights (or ...
9
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, you store it in memory. Each time you read a new string, you replace it with the one in memory with probability $1/i$, if this is the $i$th string you've read so ...
8
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.
For DTMC's the transitions always take one unit of "time." As a result, there is no choice for what your weight on an arc should be-- you put the probability of ...
8
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 have proven that $NP \ne coNP$, from which it follows that $P \ne NP$. In other words, if we knew of such a problem, a proof that is in $coNP \setminus NP$ ...
8
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 process gets extinct with probability 1. When the number is more than 1, it has a chance of surviving forever; the extinction probability is just what you calculated ...
8
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 happens, is that the samples chosen in the beginning have a chance to be overwritten by the samples chosen later. Intuitively, this balances it somewhat. But we ...
7
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 with respect to the coin tosses. This quantity depends on the input. For example, quicksort with a random pivot has expected running time $\Theta(n\log n)$. ...
7
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 detailed explanation at mathforum.org, including the algorithm (its NextBit() would be flipping your fair coin).
The case for throwing a dice with a fair coin (...
7
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 encode $X$ if you already know $Y$, than if you didn't. In your example, learning $Y$ enables you to guess $X$ correctly with probability 0.75, but as $H_2(0....
7
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 to $n$, then it is very likely that the smallest of the $k$ numbers is the one that your friend sent you.
More concretely, suppose that $k$ is constant. With ...
7
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 is $P[ X \geq a] \leq E[X]/a$ if $X \geq 0$. If we substitude $a = 2E[X]$ then we will have $P[ X \geq 2 E[X]] \leq 1/2$.
So, basically we run the algorithm ...
7
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 round of the algorithm, it has a probability of success of $p$. If you repeat it $100/p$ times and take the best cut found in any of those iterations, then the ...
7
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 right number. Let's say there are $N > 1$ possible values only one of which is correct at each minute. Then, in a world with only two miners, each minute there ...
7
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. When $p = 1/2$, the situation is more complicated.
Consider a random walk on the line started at the origin. The number of walks of length $2n$ which never move ...
7
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 one to weigh the recursive choices in such a way that expected size lies within a certain finite interval: Boltzmann samplers. They are based on the ...
6
It depends what you mean by "probabilistic". There are at least two interpretations. First, the algorithm has some probability of success for every input. Second, the algorithm succeeds on a certain fraction of inputs.
For the first interpretation, it is easy to rule out such an algorithm: probabilistic computation can be simulated (inefficiently but ...
6
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 need a random input in some algorithm. In the other way you can imagine that there is an oracle who has already tossed a coin infinitely many times and has ...
6
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 trials up to seeing $n$ different elements, where the elements are picked uniformly at random from a set of size $m$.
You can write $T_n$ as the sum of ...
5
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 so far. At each stage, you read the next line from stdin. Choose $r$ to be a random integer uniformly chosen from the range $[1,l+1]$. If $r \le k$, then discard ...
5
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 categorical predictors $X_i$:
$P(Y|X_1,\ldots,X_n)$
this correspond to a conditional probability tensor of size $d_0 \cdot d_1 \cdot \ldots \cdot d_n$. Here $Y$ (as a ...
5
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 = 1$, so the size of any subarray must be greater than or equal to zero.
The pivot is randomly chosen, so uniformly distributed between $0$ and $1$. The ...
5
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.
you can sort deterministically (even on using $\text{AC}^0$ computations) in time $O(n \log\log n)$
there is a randomized algorithm that sorts in $O(n \sqrt{\log\...
5
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
$$
X = X_1 + \cdots + X_n
$$
with all $X_i$ independent, discrete, supported in $[-1,1]$, with mean $\mu_i = 0$, variance $\sigma_i^2$.
The resulting tail ...
5
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 the average of many samples of $X$.
For example, suppose that you're a petroleum company, and you're trying to decide where to look for oil. For every square ...
Only top voted, non community-wiki answers of a minimum length are eligible