The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
1answer
65 views

Random permutations by probability matrix

I have the following problem: I need to generate $\ell$ random permutations each of length $n$ from a list of $m$ elements ($m \ge n$) by a predefined probability matrix $P$ of size $n$ x $m$. ...
1
vote
1answer
26 views

Sampling from a Acyclic Deterministic Finite Automaton

Assume you have a finite language $L$ succinctly represented as a acyclic DFA $M$ (models can't be much simpler than that :) ). How can we efficiently sample a word from $L$ with uniform ...
-3
votes
1answer
42 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 ...
0
votes
2answers
67 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 ...
0
votes
2answers
48 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) ...
0
votes
1answer
118 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
243 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
81 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
127 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
263 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
566 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
222 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
514 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
48 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
143 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
119 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 ...
9
votes
1answer
2k 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 ...