# Questions tagged [randomized-algorithms]

An algorithm whose behaviour is determined by its input and a generator producing uniformly random numbers.

179 questions
Filter by
Sorted by
Tagged with
145 views

### Concentration Bounds for Dependent Rounding

Consider the following random process which is defined on $n$ numbers $0\leq x_1,\ldots,x_n\leq 1$: At each step, pick an arbitrary number, say $x_i$. Then randomly (and independently) change its ...
193 views

### Type-and-effect systems, stochasticism and effect squelching: how about quicksort?

There's a feature of Haskell's type system which bugs me: you can't implement a randomized sorting algorithm without the use of randomness spilling out into all of its callers. That seems undesirable....
225 views

410 views

### the confusion about 'with high probability (w.h.p.)'

w.h.p. can often be seen in the analysis of randomized algorithms. It's definition can be seen here https://en.wikipedia.org/wiki/With_high_probability. However my confusion is that: Assuming we ...
204 views

### Height of randomly built binary search tree by insert and delete?

In Introduction to algorithm (CLRS), even in its third edition (published in 2009) it is noted in Sec 12.4 that little is known about height of randomly built binary search tree using insert and ...
114 views

### What upper bound can we get under 3-wise independence? (comparable edition)

Here is the original question: What bound can we get using $k$-th moment inequality under 3-wise independence? .Yury has given a 3-wise independent example that shows the upper bound is no better than ...
421 views

### Texts on application of randomized algorithms

as far as I know, Motwani & Raghavan, ”Randomized Algorithms”, Cambridge University Press, 1995 is the standard book for randomized algorithms. This is an excellent theoretical intro. Which is ...
926 views

### Chernoff Bounds for settings with limited dependence

Could someone point me to a way of bounding the tail probability of sums of bernoulli variables each generated by the same distribution but the condition of independence is only partially satisfied. ...