# Tag Info

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 ...
• 646
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$...
• 163k
Accepted

• 319
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)}$, ...
• 163k
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 ...
• 613
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 ...
• 278k
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$.
• 278k
Accepted

• 278k
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 ...
• 163k

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

By "incurred once" it probably means that if you have $N$ probabilities $p_1,...p_N$ then you switch to log space only once by taking logs of each $p_i$, perform probability multiplications in the log ...
• 9,857
Accepted

### Why does the distribution of pseudorandom numbers change when operating like this?

rand() returns an integer uniformly distributed between 0 (inclusive) and RAND_MAX (exclusive). When using modulo to partition those possibilities into 6 buckets you will end up with a few buckets ...
• 4,636
Accepted

• 618