The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
44 views

How to detect repeating random numbers?

What is the best way to detect repeating sequences of random numbers? For example, say I got two random number generators (RNG). One of them has been tampered with and is repeating the sequence of ...
8
votes
2answers
14 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 ...
10
votes
7answers
2k 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 ...
3
votes
2answers
313 views

Returning a random subset with length k of N strings while only storing at most k of them

Here's the problem. I've written a program that reads strings from stdin, and returns a random subset of those strings. The only other argument provided to the program is the length of the subset, ...
2
votes
3answers
121 views

Can a transcendental number like $e$ or $\pi$ be compressed as not algorithmically random?

The related and interesting fields of Information Theory, Turing Computability, Kolmogorov Complexity and Algorithmic Information Theory, give definitions of algorithmically random numbers. An ...
7
votes
1answer
97 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$: $$ ...
-1
votes
1answer
33 views

checking if there're equal bits in binary string [closed]

We have two binary strings, $X$ and $Y$, in two different computers. Both of them in length $n$. The computers can communicate by sending bits to each other. We have to build randomized algorithm to ...
19
votes
2answers
2k 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... ...
4
votes
1answer
109 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: ...
24
votes
7answers
2k 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 ...
2
votes
1answer
45 views

Are there any practical differences between a Turing machine with a PRNG and a probabilistic Turing machine?

Say I plugged in a hardware true-random number generator (TRNG) to my computer, then wrote programs with output that depends on the TRNG's output. Can it do anything non-trivial that a Turing machine ...
0
votes
1answer
46 views

Finding prime factors of non-random key generator

I have been working on a challenge i found on the internet. It is as follows: You've stumbled onto a significant vulnerability in a commonly used cryptographic library. It turns out that the ...
3
votes
2answers
137 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, ...
1
vote
1answer
32 views

Interpreting probabilistic time turning machines

I was trying to understand better the definition of a strong PSRG and I came across this expression which I am trying to understand better: $$ Pr_{r \in \{0,1\}^l}[A(r) = \text{"yes"}]$$ Where r is ...
0
votes
1answer
114 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 ...
2
votes
1answer
130 views

Chernoff bounds and Monte Carlo algorithms

One of Wikipedia examples of use of Chernoff bounds is the one where an algorithm $A$ computes the correct value of function $f$ with probability $p > 1/2$. Basically, Chernoff bounds are used to ...
6
votes
2answers
84 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 ...
2
votes
0answers
67 views

The sequence in which every symbol minimizes conditional complexity?

I formulate the question in terms of universal distributions. Fix a version of Solomonoff's universal distribution $\mathbf M$ and consider the following procedure for generating an infinite binary ...
7
votes
3answers
223 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 ...
5
votes
2answers
163 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 ...
6
votes
1answer
422 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 ...
4
votes
1answer
40 views

Speaking of “randomness” in computing terms, to what sense can any extant digital processor make “random” results?

From a very strictly adhering sense to the hardware and circuit-level operations of any standard (non-specialized, DSPs, or supercomputing systems, etc.) microprocessor follow very similar, almost ...
3
votes
2answers
114 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 ...
15
votes
8answers
771 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
106 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. ...
3
votes
1answer
109 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 ...
2
votes
1answer
116 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
214 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 ...
22
votes
2answers
512 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: ...
12
votes
2answers
1k 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 ...
13
votes
1answer
477 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
255 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 ...
13
votes
3answers
589 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. ...
10
votes
4answers
1k 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 ...
13
votes
1answer
1k 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
214 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
181 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
80 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 ...
4
votes
2answers
139 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, ...
12
votes
7answers
3k 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 ...