The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
66 views

What's the problem of using the clock to generate random numbers?

If the clock shows 14:15:36.909302, why not just use the fractions of a second part (09302) as a kind of random number? What is wrong with this form of generating random numbers? I am aware that ...
3
votes
3answers
138 views

Non-uniform random distribution: How do I get a random between 100 and 180 that is on average close to 120? (like in a Gaussian distribution)

Presume I have the following case: int value a int value b, for which a < b int value ...
4
votes
2answers
72 views

Uniformly random efficient sampling of shortest s-t paths, with optimal random bits

Motivated by Efficiently sampling shortest s-t paths uniformly and independently at random, The answers give methods of randomly sampling shortest $s\text{-}t$ paths. However, they use a lot of ...
0
votes
0answers
96 views

NFA random generator

I'm working on a NFA to DFA conversion tool that is different from the Subset Construction and I need to test this tool. In order to be sure that the immplementation has no bug I'd like to generate a ...
6
votes
4answers
226 views

What is a good algorithm for generating random DFAs?

I am generating random DFAs to test a DFA reduction algorithm on them. The algorithm that I'm using right now is as follows: for each state $q$, for each symbol in the alphabet $c$, add $\delta (q, ...
2
votes
1answer
360 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
179 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 ...
13
votes
5answers
404 views

How can it be detected that a 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
47 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
127 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
115 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
1k 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 ...