# Questions tagged [randomness]

Randomness is a way to mathematically model uncertainty. We often assume to have access to some well-defined source of random numbers, or that input values or events follow some probability distribution.

203 questions
Filter by
Sorted by
Tagged with
17k views

### How to simulate a die given a fair coin

Suppose that you're given a fair coin and you would like to simulate the probability distribution of repeatedly flipping a fair (six-sided) die. My initial idea is that we need to choose appropriate ...
2k views

### Returning a random subset with length k of N strings while only storing at most k of them

Here's the problem. I've written a program that reads strings from stdin, and returns a random subset of those strings. The only other argument provided to the program is the length of the subset, $k$....
1k views

### Can someone explain LazySelect?

The LazySelect algorithm is given in these slides as follows. We have a set $S$ of $n = 2k$ distinct numbers and want to find the $k$th smallest element. Let $R$ be a set of $n^{3/4}$ elements ...
86 views

### Randomized Algorithm with matrices [closed]

We have two computers, Comp1 and Comp2, which hold binary matrices A and B of size $n\times n$. We want to check if the matrices of the computers are identical except for exactly 1 entry. Comp1 has ...
149 views

### Finding the kth element of a permutation [closed]

Is there a way to generate a random permutation of the numbers 1 to N such that I can find the k-th element of the permuted list without needing to either 1) store the entire permuted list, or 2) ...