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 ...
md5's user avatar
  • 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.'s user avatar
  • 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 > ...
Yuval Filmus's user avatar
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 ...
Sarvottamananda's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Discrete lizard's user avatar
  • 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 ...
Yuval Filmus's user avatar
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 ...
Banach Tarski's user avatar
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.'s user avatar
  • 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 ...
Derek Elkins left SE's user avatar
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. ...
Yuval Filmus's user avatar
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 ...
phipsgabler's user avatar
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.'s user avatar
  • 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 ...
Ariel's user avatar
  • 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.'s user avatar
  • 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, ...
Raphael's user avatar
  • 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 ...
Andreas T's user avatar
  • 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 ...
orezvani's user avatar
  • 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 ...
Yuval Filmus's user avatar
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, \...
SapereAude's user avatar
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.'s user avatar
  • 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 ...
AspiringMat's user avatar
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$.
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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.
Dave Clarke's user avatar
  • 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 ...
Yuval Filmus's user avatar
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$.
Yuval Filmus's user avatar
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}{\...
Yuval Filmus's user avatar
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 $$ \...
Yuval Filmus's user avatar
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.'s user avatar
  • 154k

Only top scored, non community-wiki answers of a minimum length are eligible