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.

Filter by
Sorted by
Tagged with
44
votes
5answers
16k views

Why is the Mersenne Twister regarded as good?

The Mersenne Twister is widely regarded as good. Heck, the CPython source says that it "is one of the most extensively tested generators in existence." But what does this mean? When asked to list ...
39
votes
7answers
4k views

Can PRNGs be used to magically compress stuff?

This idea occurred to me as a kid learning to program and on first encountering PRNG's. I still don't know how realistic it is, but now there's stack exchange. Here's a 14 year-old's scheme for an ...
33
votes
2answers
1k 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: ...
32
votes
7answers
11k views

Differences and relationships between randomized and nondeterministic algorithms?

What differences and relationships are between randomized algorithms and nondeterministic algorithms? From Wikipedia A randomized algorithm is an algorithm which employs a degree of randomness ...
32
votes
5answers
11k 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 ...
31
votes
2answers
2k views

Simulating a probability of 1 of 2^N with less than N random bits

Say I need to simulate the following discrete distribution: $$ P(X = k) = \begin{cases} \frac{1}{2^N}, & \text{if $k = 1$} \\ 1 - \frac{1}{2^N}, & \text{if $k = 0$} \end{cases} $$ The most ...
27
votes
9answers
18k 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 ...
25
votes
11answers
10k views

Is von Neumann's randomness in sin quote no longer applicable?

Some chap said the following: Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin. That's always taken to mean that you can't generate ...
24
votes
3answers
3k views

Are all pseudo-random number generators ultimately periodic?

Are all pseudo-random number generators ultimately periodic? Or are they periodic at all in the end? By periodic I mean that, like rational numbers, they in the end generate a periodic subsequence... ...
24
votes
1answer
6k 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 ...
23
votes
8answers
2k 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 ...
22
votes
6answers
9k views

Can we generate random numbers using irrational numbers like π and e?

Irrational numbers like $\pi$, $e$ and $\sqrt{2}$ have a unique and non-repeating sequence after the decimal point. If we extract the $n$-th digit from such numbers (where $n$ is the number of times ...
22
votes
10answers
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 ...
22
votes
3answers
3k 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. ...
21
votes
1answer
1k 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 correctness....
20
votes
2answers
5k views

How does an operating system create entropy for random seeds?

On Linux, the files /dev/random and /dev/urandom files are the blocking and non-blocking (respectively) sources of pseudo-random ...
20
votes
5answers
6k 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 ?
13
votes
1answer
5k 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 ...
13
votes
2answers
7k views

Guessing the smallest unique positive integer

Let us consider the following game: there are some players and a computer. Each player inputs one positive integer and his name (player doesn't know another's numbers, just his own). When all the ...
12
votes
1answer
7k views

Generate scale-free networks with power-law degree distributions using Barabasi-Albert

I'm trying to reproduce the synthetic networks (graphs) described in some papers. It is stated that the Barabasi-Albert model was used to create "scale-free networks with power-law degree ...
11
votes
4answers
4k 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 ...
9
votes
3answers
2k views

Random sampling in a polygon

I would like to sample a uniformly random point in a polygon... If sample a large number they'd be equally likely to fall into two regions if they have the same area. This would be quite simple if ...
9
votes
4answers
1k 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, c)...
9
votes
3answers
352 views

What makes a pseudorandom generator, a high quality one?

Reading this answer to this SO question: Why do we not combine random number generators?, it talks about very high-quality PRNG (Pseudo Random Number Generator) so it makes me wonder what ...
8
votes
5answers
447 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 ...
8
votes
1answer
240 views

Is it possible to simulate a fair coin with a finite number of tossing of a biased one?

It is a classic problem to simulate a fair coin with a biased one. According to Fair Coin (wiki), John von Neumann gave the following procedure: Toss the coin twice. If the results match, start over,...
7
votes
3answers
2k views

Problem with the pseudo random number generator One-Time-Pad

I've started learning cryptography in class and we've come across One-Time-Pads, in which the key (uniformally agreed upon) is as long as the message itself. Then you turn the message into bits, do $...
7
votes
2answers
326 views

How do computers create 'randomness'?

I have just used a function 'rand()' in my algorithm. In fact, it was arc4random() that I used. However, it got me thinking, how is randomness created in a computer system? Can anything ever truly be ...
7
votes
2answers
226 views

Why is randomness a problem? (i.e. why do we care about derandomization?)

I'm reading Aaronson's survey on P vs. NP, and I've come to understand that in CS theory, people really care about derandomization results like P vs. BPP etc. My question is, what's the problem with ...
7
votes
2answers
379 views

Why do we care about random Boolean SAT formula?

I've been looking for a reference for the above question. As far as I know the answer is: If we can make a solver that is efficient for all randomly generated instances, it should be efficient for ...
7
votes
3answers
430 views

Unreachable Real Numbers - Randomness & Computability

I've recently read that there were many real numbers that would never be reachable by humanity. The explanation itself says that we can write as many programs as integers which is infinite, but there ...
7
votes
1answer
519 views

What does it mean for a random number generator's sequence to be only 1-dimensionally equidistributed?

Whilst reading up on Xorshift I came across the following (emphases added): The following xorshift+ generator, instead, has 128 bits of state, a maximal period of 2^128 − 1 and passes BigCrush: ...
7
votes
1answer
309 views

Which one of these two sequences is random, and which one is not?

We let $\alpha = \alpha_1\alpha_2\alpha_3\ldots$ be an infinite random sequence (under the uniform measure) where $\alpha_i$ may be $1$ or $0$, and then define the boolean function $B_k$: $$ B_k(\...
6
votes
3answers
4k views

What's a uniform shuffle?

What does it mean exactly a "uniform shuffle" algorithm ? Is this method considered a uniform shuffle ? ...
6
votes
3answers
212 views

Efficiently generating a uniformly random list of unique integers in a range

The problem: To generate a list of size $n$, Containing unique integers, Sampled uniformly in the range $\left[0,m\right)$, In $O(n)$ time, except that: Assuming $m$ is bounded by some word-size, $\...
6
votes
2answers
180 views

How best to statistically verify random numbers?

Lets say I have 1000 bytes that are supposedly random. I want to verify to a certain certainty that they are indeed random and evenly distributed across all byte values. Aside from calculating the ...
6
votes
2answers
134 views

Analog of PP for computability rather than complexity?

The complexity class PP can be defined in many ways, one of which involves randomness - a language $L$ is in PP if there is a polynomial-time, randomized TM $M$ such that $w \in L$ if and only if the ...
6
votes
1answer
71 views

Generate string with large Kolmogrov complexity

Given $c$, can you generate a string $s$ with $K(s) \ge c$, along with a proof of that fact? I think the answer is no except for small $c$, but I'm not sure.
6
votes
2answers
124 views

Online sorting without modifications

There is an array with $n$ places. There is a stream of $n$ unique numbers that arrive at a random order (permutation selected uniformly at random). Whenever a number arrives, we must put it ...
6
votes
1answer
518 views

How do incompressible strings and random strings share the same properties?

I came across the following theorem in Sipser's about incompressible strings. Let $\;f$ be some computable function which holds for almost all strings. The for any $b > 0 $, the property $\;f$ ...
6
votes
2answers
2k views

Compressing normally distributed data

Given normally distributed integers with a mean of 0 and a standard deviation $\sigma$ around 1000, how do I compress those numbers (almost) perfectly? Given the entropy of the Gaussian distribution, ...
6
votes
2answers
121 views

Invertible function that randomizes order

I am looking for an invertible discrete function $f:\{0,1,2,\dots,n-1\} \to \{0,1,2,\dots,n-1\}$ for some given integer $n$. I want $f(0),f(1),\dots,f(n-1)$ to return all the integers in range $[0..n)...
6
votes
2answers
186 views

Isn't std::bernoulli_distribution inefficient? Designing a bit-parallel Bernoulli generator

C++11 has a convenient Bernoulli RNG, illustrated at http://en.cppreference.com/w/cpp/numeric/random/bernoulli_distribution . However, distilling an entire random integer into a single random bit ...
6
votes
1answer
163 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 ...
5
votes
3answers
2k views

How to select a binary tree node uniformly at random

The exercise I'm trying to solve is You are implementing a binary search tree class from scratch, which, in addition, to insert, find and delete, has a method ...
5
votes
2answers
391 views

Shuffling a list while keeping order relative to related elements

I'm looking to shuffle a list of the elements $a_1,\dots, a_6, \dots, e_1, \dots, e_6$ while keeping two rules: if I loop though the list and filter out a specific letter or number it should be in ...
5
votes
2answers
829 views

Proving that $\text{PCP}(O(\log n),1)\subseteq \mathsf{P}$

I'm studying the PCP theorem. While it is easy to prove that $\mathsf{P}=\text{PCP}(O(\log n),0)$ , proving that $\text{PCP}(O(\log n),1)\subseteq \mathsf{P}$ i.e. PCP that uses $O(\log n)$ random ...
5
votes
1answer
337 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$. ...
5
votes
2answers
197 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. ...
5
votes
1answer
73 views

Can we derandomize subexponential algorithms given P=BPP?

Under $BPP=P$ conjecture randomization does not have much power for poly time algorithms. Can we say the same about randomized subexp algorithms like number field sieve?

1
2 3 4 5