Tagged Questions

The tag has no usage guidance.

53 views

Turing Completeness of System Which Randomly Fails to Complete Calculations

If one were to create a variant of a turing complete language which upon completing a calculation randomly changes the answer by one, would it be Turing complete? For example, say I had a Python ...
14 views

Problem with random numbers and while loop [on hold]

I have to generate two random numbers for 52000 instances in an ArrayList, attack 1 and attack 2, where attack 1 must be greater than attack 2, so i have to put them in the list. This is my sample ...
71 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 ...
26 views

Martin-Löf randomness characterization

In his 1973 paper On the notion of a random sequence, Levin states (without proving) a characterization of Martin-Löf randomness by writing Theorem 3. A sequence $\alpha$ is random w.r.t. the ...
14 views

Compression of Memoryless Sources

Are there any compression algorithms outside of entropy encodings that yield a significant compression ratio for memoryless sources (not the Markov kind, but this kind)? More concretely, if a million ...
25 views

Uniform generation of random bipartite bi-regular graphs?

I want an algorithm that takes the following Input: $M,N,k,d$ positive integers such that $kM = dN$. and produces the following Output: Random bipartite graph, with $M$ vertices all of degree $k$ ...
33 views

Is it possible to derive a deterministic CSPRNG given two functions, at least one of which is a CSPRNG?

Let f and g be two functions with integer range 0..m-1. They may keep state and interact ...
20 views

2D random walk. Should both dimensions be independent?

My assignment is to compare several probability distributions in random walk algorithm. I'd like to analyse it in 2D linear space to make the concept more intuitive. What is the correct approach in ...
35 views

Name for this algorithm to roughly shuffle infinite list with finite memory

A couple of friends and I were talking about the best way to attempt to shuffle a infinite list, given finite memory. We immediately concluded that you could not do so, at least not in the same sense ...
127 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 ***. <...
85 views

39 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 ...
123 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 ...
20 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 ...
44 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 ...
44 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 ...
432 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 ...
292 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$ ...
40 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 ...
21 views

Confused by extremely high autocorrelation

I have the following python code ...
72 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 need....
24 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 direction?...
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 ...
69 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 ...
129 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 ...
53 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 ...
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 ...
82 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 ...
106 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 ...
196 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 ...
102 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 ...
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 ...
451 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 ...
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 ...
52 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 ...
105 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 ...
105 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 ...
322 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$...
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 ...
144 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
79 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 ...
624 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 ...
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 ...
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, $k$....