The tag has no usage guidance.

learn more… | top users | synonyms

4
votes
2answers
89 views

About randomness and minmax algorithm with alpha beta pruning

Will choosing the child of a node randomly in the alpha beta algorithm have a better chance to get a cut off than choosing them in order? Here's the pseudocode with my addition marked with ***. ...
-1
votes
0answers
17 views

Is Dist − NP ⊆ Avg − P a reasonable stance? [closed]

It is known that $Dist-NP\subseteq Avg-P\implies P=BPP$. So proving $Dist-NP\subseteq Avg-P$ proves $P=BPP$ which most people believe. Now my problem is if $Dist-NP\subseteq Avg-P$ a reasonable ...
1
vote
0answers
74 views

If NP is easy on average then does it mean P=NP?

If $NP=RP$ then $NP$ is easy on average. Then from point $1$ in abstract in http://lance.fortnow.com/papers/files/derand.pdf which says $NP$ is easy on average implies $P=BPP$ do we have ...
3
votes
2answers
85 views

How likely is it that a computer miscalculates 1+1? [on hold]

Of course, normally a fully-functional computer will calculate 1+1=2. However, the physics governing the behavior of a chip is quantum mechanical. So in principle there is a certain probability that ...
5
votes
1answer
52 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?
4
votes
2answers
61 views

On certificates in BPP (avoiding majority vote)

Assume that we have a $BPP$ algorithm $A$ for a problem $\Pi$. Given input $x$ we run $A$ on $\Pi$ polynomially many times and take majority output. However if the problem $\Pi$ is also in $NP$ ...
1
vote
1answer
38 views

How broken is LCG in the case of partial output?

Suppose we have a linear congruential generator defined by $X_{n+1} = (a X_n + c) \mod 2^n$ where $a, c, n$ are all known and we would like to determine the initial value $X_0$. However, if we can ...
6
votes
3answers
149 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, ...
1
vote
2answers
37 views

Random sampling of tuples

When I talked with students about pseudo-random number generation, I mentioned that you should not blindly use subsequent outputs of a pseudo-random number generator (PRNG) to form tuples as they may ...
2
votes
1answer
122 views

Should Kolmogorov complexity include all resources or just program size?

I've been thinking about pi and Kolmogorov complexity (Kc). As the digits of pi are randomly distributed (and infinite) , they can't be compressed with a typical compression program. Through the ...
3
votes
0answers
18 views

Similarity-based binary representation of graph

I have given an undirected graph of which I want to associate every vertex with a (random) binary vector. I can chose the dimensionality of the vector but it has to be identical for every vertex. The ...
2
votes
1answer
42 views

How does the Weibull distribution work as fault model in wireless sensor networks?

I am a little bit confused with the concept of using the Weibull distribution or other distribution for fault model. As I understand, in simulation this distribution is often used for modelling a ...
3
votes
2answers
40 views

Could PRNGs make use of more internal state?

In the context of our class on combinatorial algorithms we have been discussion randomness. One student said (paraphrasing): Pseudo-random number generators (PRNGs) must have a period since they ...
15
votes
2answers
340 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 ...
6
votes
1answer
287 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$ ...
4
votes
1answer
39 views

One-shot Private Randomness Extractor

Suppose a pair of random variables $(X,Y)\in\mathcal{X}\times \mathcal{Y}$ with joint distribution $P_{XY}$ is given. I am interested in a deterministic mapping $f:\mathcal{Y}\to \{0, 1\}^k,$ for ...
0
votes
1answer
21 views

Confused by extremely high autocorrelation

I have the following python code ...
0
votes
0answers
60 views

Hash Table: How to Calculate Max Load of a Bucket in Practice

My question is related to this question I posted in math forum: http://math.stackexchange.com/questions/1512644/balls-and-bins-hash-table-a-concrete-example but I could not get an answer that I ...
2
votes
0answers
22 views

What are the recent research directions in the topic of circuit lower bounds from derandomization?

I am thinking of the classical paper, https://www.cs.sfu.ca/~kabanets/Research/poly.html Can someome link to some papers/reviews that give a sampling of what are the recent thoughts in this ...
0
votes
0answers
18 views

Bias for modified knuth shuffle? [duplicate]

The Knuth shuffle, also known in its original form as Fisher-Yates-shuffle, generates a random permutation, considered unbiased. I.e. all permutations are supposedly equally likely. The algorithm is ...
2
votes
2answers
66 views

How to sample random game input that looks similar to human control?

What I would like to do is improve upon projects like 'RNG plays pokemon'. There, a computer produces a random sequence of inputs that are transmitted to an emulator and played in-game. Though this ...
3
votes
2answers
115 views

How to extract randomness from a file?

I have a generator of files with approximately 7 bits /byte entropy. The files are about 30KB each in length. I'd like to use these as sources of entropy to generate random numbers. Theoretically I ...
4
votes
1answer
51 views

Bias of first values produced by a family of RNGs

Suppose I'm doing a large number of pseudo-random but deterministic experiments, where each experiment requires generating several random numbers. I'm approaching this by having each experiment use a ...
0
votes
0answers
10 views

Removing the acceptance error from AM

Typically the AM class is defined with error upper bound of 1/3 for deciding both the situations of the membership question being true or false. But curiously enough for the situations when the ...
0
votes
1answer
34 views

Estimate distribution of a composite variable

Suppose I have N sets of numbers (10 numbers per set) {a1, ....., a10}. I form a sum by taking one number at random from each set. SUM = num from set 1 +......+ num from set N. If I do this a large ...
2
votes
1answer
79 views

Can a probabilistic Turing Machine compute an uncomputable number?

Can a probabilistic Turing Machine compute an uncomputable number? My question probably does not make sense, but, that being the case, is there a reasonably simple formal explanation for it. I should ...
1
vote
2answers
102 views

About being able to sample a permutation of a finite set uniformly at random [closed]

I was looking at this question. So if I understand the above discussion right then it concludes that if say one had access to an oracle which can uniformly at random sample from a finite set then ...
6
votes
3answers
188 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 ...
0
votes
1answer
97 views

Can you generate random linear programming problems?

I looked at Linear Programming, and it are problems like this: You know that Cabinet X costs 10 cents per unit, requires 6 square feet of floor space, and holds 8 cubic feet of files. Cabinet ...
1
vote
1answer
47 views

Which cellular automata rules are suitable for randomizing an input sequence?

S. Wolfram has in has book "A New Kind of Science" listed 256 simple rules of cellular automata. Which of these rules could via iteration essentially contribute to render an input sequence more random ...
3
votes
1answer
395 views

Set the parameters of a Erdos-Renyi graph generator to get a specific mean degree

I'm trying to reproduce the synthetic networks (graphs) described in some papers. The topic is the same as a previous question of mine, but with a different focus. It is stated that the Erdos-Renyi ...
7
votes
1answer
2k 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 ...
3
votes
1answer
46 views

PRNG bad seeding and von Neumann unbiasing

Large period PRNGs such as Mersenne Twister require good seeding otherwise the initial output in the sequence may not seem to be high-quality, at least for the first few words (and in the way that is ...
6
votes
2answers
104 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 ...
0
votes
0answers
98 views

Generate a Random Diagonally Dominant Matrix

I would like to write a function to generate a diagonally dominant matrix of random values. What I'm ultimately leading to is writing a code to implement the Jacobi method on this matrix in CUDA for a ...
0
votes
1answer
307 views

Comparing random access and sequential access

Assume that we choose randomly $k$ distinct numbers $N_1$, $\dots$, $N_k$ in $\{1, \dots, k\}$ and we have a file of $k$ parts. We have these two cases : We read (or write) sequentially from part ...
1
vote
0answers
50 views

Using “incremental algorithms” to find the $k^{th}$ smallest number

This is what I vaguely understand of what an "incremental algorithm" is - say one such for calculating the $k^{th}$ smallest number for a given sequence of elements $x_1, x_2,...,x_n$ then after the ...
0
votes
2answers
142 views

Is randomly building a BST different from random sampling whole trees?

What is the difference between a randomly built binary search tree (using n keys )and choosing a binary search tree (of n key) from a random distribution
1
vote
1answer
76 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 ...
12
votes
2answers
547 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 ...
13
votes
7answers
5k 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
831 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, ...
4
votes
3answers
339 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
119 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
50 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 ...
20
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... ...
5
votes
1answer
206 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: ...
28
votes
7answers
3k 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
87 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
100 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 ...