The randomness tag has no wiki summary.
8
votes
2answers
98 views
What randomness really is
I'm a Computer Science student and am currently enrolled in System Simulation & Modelling course. It involves dealing with everyday systems around us and simulating them in different scenarios by ...
3
votes
2answers
45 views
Random generator considerations in the design of randomized algorithms
It is well known that the efficiency of randomized algorithms (at least those in BPP and RP) depends on the quality of the random generator used. Perfect random sources are unavailable in practice. ...
2
votes
1answer
52 views
Accurate definition of BPP
I'm a bit confused about the definition of BPP. The way BPP is defined in typical text books (Arora/Barak for example) is that if M(x) is a Probabilistic Turing Machine (PTM) that recognizes a ...
1
vote
1answer
55 views
Are genetic algorithms special instances of random search done in an unexpectedly short run-time? [closed]
I was wondering since randomness is embedded in genetic algorithms at almost every level, is there a really fine line between genetic algorithms and pure random search?
Ever since I finished my ...
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 ...
21
votes
2answers
263 views
How asymptotically bad is naive shuffling?
It's well-known that this 'naive' algorithm for shuffling an array by swapping each item with another randomly-chosen one doesn't work correctly:
...
0
votes
0answers
16 views
Algorithm: Uniformly sampling on hyperplanes [duplicate]
Possible Duplicate:
Uniform sampling from a simplex
Given the vector size N, I want to generate a vector <s1,s2, ..., sn> that ...
7
votes
2answers
278 views
Uniform sampling from a simplex
I am looking for an algorithm to generate an array of N random numbers, such that the sum of the N numbers is 1, and all numbers lie within 0 and 1. For example, N=3, the random point (x, y, z) should ...
10
votes
1answer
217 views
Generating inputs for random-testing graph algorithms?
When testing algorithms, a common approach is random testing: generate a significant number of inputs according to some distribution (usually uniform), run the algorithm on them and verify ...
3
votes
1answer
129 views
How to random-generate a graph with Pareto-Lognormal degree nodes?
I have read that the degree of nodes in a "knowledge" graph of people roughly follows a power law distribution, and more exactly can be approximated with a Pareto-Lognormal distribution.
Where can I ...
12
votes
3answers
237 views
Is rejection sampling the only way to get a truly uniform distribution of random numbers?
Suppose that we have a random generator that outputs
numbers in the range $[0..R-1]$ with uniform distribution and we
need to generate random numbers in the range $[0..N-1]$
with uniform distribution.
...
8
votes
4answers
659 views
Most efficient algorithm to print 1-100 using a given random number generator
We are given a random number generator RandNum50 which generates a random integer uniformly in the range 1–50.
We may use only this random number generator to ...
11
votes
1answer
379 views
How to prove correctness of a shuffle algorithm?
I have two ways of producing a list of items in a random order and would like to determine if they are equally fair (unbiased).
The first method I use is to construct the entire list of elements and ...
8
votes
5answers
192 views
How can encryption involve randomness?
If an encryption algorithm is meant to convert a string to another string which can then be decrypted back to the original, how could this process involve any randomness?
Surely it has to be ...
4
votes
1answer
115 views
Online generation of uniform samples
A source provides a stream of items $x_1, x_2,\dots$ . At each step $n$ we want to save a random sample $S_n \subseteq \{ (x_i, i)|1 \le i \le n\}$ of size $k$, i.e. $S_n$ should be a uniformly chosen ...
3
votes
1answer
78 views
Making random sources uniformly distributed
How do I build a random source that outputs the bits 0 and 1 with $prob(0) = prob(1) = 0.5$. We have access to another random source $S$ that outputs $a$ or $b$ with independent probabilities ...
3
votes
2answers
112 views
Is the number of coin tosses of a probabilistic Turing machine a Blum complexity measure?
I read that the number of coin tosses of a probabilistic Turing machine (PTM) is not a Blum complexity measure. Why?
Clarification:
Note that since the execution of the machine is not deterministic, ...
10
votes
7answers
1k views
Generating uniformly distributed random numbers using a coin
You have one coin. You may flip it as many times as you want.
You want to generate a random number $r$ such that $a \leq r < b$ where $r,a,b\in \mathbb{Z}^+$.
Distribution of the numbers should ...
