New answers tagged randomized-algorithms
10
votes
Accepted
Proof for boosting success probability of a random algorithm with binary output
The proof I know of uses a weak version of Chernoff bound:
If $X_1, X_2, …, X_n$ are independent Bernoulli random variables of same parameter $p$, and $X = \sum\limits_{i=1}^nX_i$, then:
$$\mathbb{P}(...
Top 50 recent answers are included
Related Tags
randomized-algorithms × 429algorithms × 190
probability-theory × 76
complexity-theory × 56
algorithm-analysis × 52
randomness × 45
graphs × 36
probabilistic-algorithms × 27
time-complexity × 24
approximation × 20
runtime-analysis × 16
sorting × 16
sampling × 15
data-structures × 14
monte-carlo × 13
combinatorics × 12
quicksort × 12
pseudo-random-generators × 12
complexity-classes × 11
optimization × 10
streaming-algorithm × 9
terminology × 8
computational-geometry × 8
arrays × 8
random-number-generator × 8