The random tag has no wiki summary.
1
vote
1answer
45 views
How to generate uniformly random binary trees?
Could someone please provide a reference giving an algorithm to generate uniformly random binary trees?
1
vote
2answers
133 views
Best random permutation employing only one random number
The ideal random permutation algorithm of Fisher and Yates (Algorithm P in Knuth vol.2) for a sequence of $n$ objects requires $n-1$ random numbers.
In some card games one first does a "cut" and ...
3
votes
1answer
115 views
How it can be detect that random number generator is not really random?
I heard that random number generation in computers isn't really random, but there is no efficient algorithm to detect it. How can it be detected at all ?
1
vote
1answer
46 views
Stochastical algorithm
We have a stochastic random source. This gives the bit $0$ (or $1$) with probability $1/2$.
We want to generate a uniform distribution on the set S = $\{0, 1,..., n-1\}$.
Which algorithm gives with ...
4
votes
1answer
105 views
Random algorithm with biggest sequence that never repeats
I am going to attempt to write a random number generator using exisiting randomize algorithms. Can you suggest which algorithm has the biggest sequence that never repeats? I don't care if they are ...
6
votes
1answer
101 views
Streaming algorithm and random access
Consider an array $X$ of $n$ cells, each containing a number from $\{1,..., n\}$. There is at least
one duplicate number, i.e., a number that appears at least twice. I want output some duplicate ...
0
votes
0answers
22 views
Prove fingerprinting [duplicate]
Possible Duplicate:
Prove fingerprinting
Let $a \neq b$ be two integers from the interval $[1, 2^n].$ Let $p$ be a random prime with $ 1 \le p \le n^c.$ Prove that
$$\text{prob}(a \equiv b ...
8
votes
1answer
775 views
Random Sudoku generator
I want to generate a completely random Sudoku.
Define a Sudoku grid as a $9\times9$ grid of integers between $1$ and $9$ where some elements can be omitted. A grid is a valid puzzle if there is a ...
