16
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 ...
- 636
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.♦
- 154k
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 > ...
- 274k
10
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,807
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 ...
- 274k
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 ...
- 7,768
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 ...
- 274k
7
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,188
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.♦
- 154k
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 ...
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. ...
- 274k
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
7
votes
Accepted
Is it possible to randomly allocate items to bins such that each distinct allocation has equal probability?
It appears your question is equivalent to sampling uniformly at random from the integer partitions of $N$, but constrained so that your partition has $\le B$ parts.
If that is correct, there are ...
D.W.♦
- 154k
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.3k
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.♦
- 154k
5
votes
Is shuffling a set of items after popping an item meaningfully more random than doing it once, before starting?
Say we have $n$ people. After shuffling the whole list (once), every person occupies every position with probability $1/n$.
Shuffling before each draw means every choice is uniformly random; that is, ...
- 71.9k
5
votes
Accepted
Summation of a Random Variable
Your outcomes are not the number of candidates but rather which candidates were hired: $\Omega = \{0,1\}^n$. Then you have $X_i(a_1, \dots, a_n) = a_i$ and $X(a_1, \dots, a_n) = \sum\limits_{i=1}^n ...
- 625
5
votes
Reachability queries on uncertain graphs
I edited your question to make it self-contained.
The literature on uncertain graphs is really rich for this problem. What you are looking for is "reachability in uncertain graphs", which has been ...
- 1,934
5
votes
Accepted
Sorting in a probabilistic order
One of the popular models for biased permutations is the Mallows model, dating to a paper of Mallows from 1957. Lu and Boutilier, quoting Doignon et al., give the following recipe for sampling a ...
- 274k
5
votes
Accepted
How do we prove the time complexity of this simple problem in probabilistic inference on a Bayesian network?
Exponential time is not required for finding the requested probability. In fact, only linear time is needed, as we will see below.
First let's define some additional notation. Let $X = (x_1, x_2, \...
- 319
5
votes
Accepted
Given an unsorted list of $n$ items, how many random comparisons are needed on average to be able to sort the list?
Asympotically, you'll need $\Theta(n^2 \log n)$ comparisons.
Suppose $x_{(1)},\dots,x_{(n)}$ denotes the elements in sorted order. Then if you don't see a comparison between $x_{(1)}$ and $x_{(2)}$, ...
D.W.♦
- 154k
5
votes
Accepted
Dynamic programming: optimal order to answer questions to score the maximum expected marks
First, if any $p_i=0$, then immediately throw it away since you're guaranteed to lose. If any probability is $1$ then immediately ask it! (after all why risk not getting the reward when you're ...
- 594
4
votes
Accepted
Two definitions of universal hash functions
The two definitions are not equivalent. The second definition does not imply the first. You can take $\mathcal{H}$ to be the collection of all functions $h$ such that $h(1) = 1$.
- 274k
4
votes
Accepted
The transition function in a Markov decision process
The notation $T\colon A\times U\times A\to[0,\infty)$ means a function with three parameters, the first from $A$, the second from $U$, and the third from $A$, which outputs a non-negative real.
It is ...
- 274k
4
votes
The transition function in a Markov decision process
Elements of $A\times U\times A$ are triples $(a_1,u,a_2)$, where $a_1$ and $ a_2$ are elements of $A$ and $u$ is an element of $U$. The $\times$ gives the Cartesian product of its arguments.
- 20.2k
4
votes
Accepted
Deep DFS traverse on graph
You can compute the exact distribution of $\sum_{i=1}^n s_i$ using dynamic programming: for each vertex $v$, index $m \in \{0,\ldots,n\}$ and index $S \in \{0,\ldots,9m\}$, calculate the number of ...
- 274k
4
votes
Accepted
Random Walk on the Integer Line
Hint: $S_l - S_r$ is the sum of $2n$ independent variables $X_1,\ldots,X_{2n}$, with $\Pr[X_i = 1] = \Pr[X_i = -1] = 1/2$.
- 274k
4
votes
Accepted
Sampling from a set of numbers with a fixed sum
You can bound the variance as follows. Let $b_i$ be an indicator variable signaling that $x_i$ was chosen. You are interested in $y = \sum_i b_i x_i$. We have
$$
\mathbb{E}[(b_ix_i)^2] = \frac{x_i^2}{\...
- 274k
4
votes
Accepted
Confusion about the definition of the average-case running time of algorithms
The definition is a special case of a more general notion. Given probability distributions $\mu_1,\mu_2,\ldots$ on inputs, the average running time (with respect to the $\mu_i$) is defined as
$$
\...
- 274k
4
votes
Accepted
Hidden Markov Model initial probability reestimate: Why $\pi^*_i = \gamma_i(1)$ instead of $\pi^*_i = \frac{\gamma_i(1)}{\sum_{j = 1}^N \gamma_j(1)}$
It is defined to be a probability. A probability is by definition already normalized. In particular, we are guaranteed that
$$\sum_{j=1}^N \gamma_j(1) = 1,$$
as there are only $N$ possibilities ...
D.W.♦
- 154k
Only top scored, non community-wiki answers of a minimum length are eligible