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.

203 questions
Filter by
Sorted by
Tagged with
286 views

Expected Linear time Minimum Spanning Tree algorithm

I am trying to understand the proposed "Randomized Linear-Time Algorithm to Find MST". My findings: I have read and search almost every available resource( main paper, wiki, reports on paper, lecture ...
43 views

Looping through random integers - will it halt with probability 1?

Say I have a simple program that has the pseudocode like this: ...
40 views

Randomly choose a line - algorithm

We have a large file that can't fit into internal memory. How do we randomly pick one line so that each line has the same probability to be picked? And how do we randomly pick such n lines so that ...
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 ...
69 views

Indexing a random permutation

I am curious if there exists a method for specifying a permutation $F_k: X \to X$ with a small(ish) $k$. Something that comes very close to my goal is a block cipher, say AES. But block ciphers have ...
470 views

What Good Is Kolmogorov Complexity Since It Is Relative?

Kolmogorov complexity is relative to a choice of Universal Turing Machine. Because of the Invariance Theorem, the difference in complexity assigned by two Universal Turing Machines is bounded by a ...
129 views

Fitness model for scale free networks

In order to generate scale-free networks, we can use this algorithm, derived from Barabási–Albert model: 1) we assign every node a "weight" $\theta_i$ (or two in the direct case). 2) we place $m$ ...
85 views

Given a sufficiently powerful computer and model, can dice rolls be predicted?

I guess that this is a chaos, randomness and modelling question. Can it be conceived that a sufficiently powerful (perhaps quantum) computer might be able to accurately predict the scores on a ...
69 views

What is the relationship between entropy rate and quantization?

I have a totally random source of signal data that looks like a typical normal distribution. I've included an image as I like pictures:- The source has a mean of 0, and a standard deviation of 1. ...
41 views

TRNG by hamming distance of processor tics

I hardly remember on a lecture, where it was told, that the distance of the practical actual running-speed of a processor to the previous tic is used, to generated a true random entropy for seeding. ...
346 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 ...
1k views

How to understand the analysis of expected running time of randomized quick-sort in this paper?

I'm learning the book named Data Structures & Algorithms in Python. On Page 557-558, there is a proof of the expected running time of randomized qucick-sort. I have some problems confusing me ...
379 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 ...
464 views

Why do we need Gibbs sampling (and MCMC)?

I just learned about Gibbs Sampling which is an MCMC method. Given a distribution $\pi$, we want to sample an item according to $\pi$. Maybe my alternative suggestion would sound somewhat naive (even ...
44 views

Apologies if this is the wrong place to ask. For my experiment, I have a single-page application and a multi-page application. I am testing them with an exponential distributed delay throttling. The ...
3k views

Algorithm to create tournament brackets

I'm designing a web app to host e-sports tournaments and want to create an algorithm that generates tournament brackets. Given a list of participants' user ID's (minimum 4, maximum let's say 64), I ...
3k views

Time complexity of this while loop

So, i would like to know the time complexity of the following codes: ...
19 views

Generating symmetric keys

Let's assume that we have to generate huge number of 256-bit symmetric keys. How to do it and how to be sure that it is safe. Perhaps it requires a strong mathematical backend. Don't hesitate to ...
23 views

Are exponential random graph models based on Maximum Entropy Principle?

Can anyone shed light on whether or not ERGMs are network models based on the maximum entropy principle? Especially if we say that the available information about the network is in the form of network ...
243 views

What is the time complexity of this аlgorithm? O(n * r)

Given function rand7 returns random integer in interval [0, 6]. Your task is to implement function ...
46 views

Given a Noisy Curve, Write a Function to Output Likely Slopes

I am training a Variational Autoencoder (type of convolutional neural network), and have been plotting cost over time. The result is a noisy curve, shown here: I would like to write a function that ...
79 views

Random function “returns a uniformly distributed int”. Does this mean the probability of every number is the same?

Most functions that generate random numbers are described as: Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive) If I use it to ...
32 views

Generation of 11 bit random number

I need camera to sign one random line(there are something like 2000 lines) from the frame each second. At the beginning I have some 64 bits seed with high entropy from physical RNG and a secure ...
48 views

How to find a good saw function for PRNG?

As part of an assignment I have to write a PRNG using a sin (or any other trigonometric function) and a saw function which I'm struggling a bit with. So how would you find a good saw function with ...
167 views

Can Von Neumann bit extraction be made more efficient?

I want to develop a previous question regarding Von Neumann debiasing /randomness extraction. The typical solution (as posted) is to take pairs of throws and output a bit based on a comparison of ...
113 views

What is the Expected run time of an algorithm that randomly generates N unique strings of length D?

I was trying to rigorously/mathematically analyze the runtime of the following algorithm: ...
652 views

Randomly select a uniform subsample from a nonuniform dataset

I have a dataset of events with timestamps spanning several months. The event rate is "bursty", i.e. there are periods of much higher and lower rate than the average. I would like to randomly select ...
41 views

Term for expected randomized given advice string?

Problems which run in deterministic polynomial time given polynomial sized advice are in class P/poly. Problems which run in probabilistic polynomial time given polynomial sized advice are still in ...
366 views

How can I prove that a cryptography algorithm is a pseudo-random number generator?

I have read about cryptography prgs. If I have a generator G(x1,x2...,xn)= x1,x2,...,xn, x1&x2...&xn , how can I prove that it is a prg or prove it is not? Is there some principles I have ...
225 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 ...
183 views

Generating Pairs of Random Numbers

Please consider the following probability density function of two variables. \begin{eqnarray*} f(x_1,x_2) &=& \begin{cases} 2(x_1+x_2) & \text{for} \,\, 0 \le x_1 \le x_2 \le 1\\ 0 ...
214 views

Achieving Randomness

Can True Randomness be achieved by composing prngs in different states and with different algorithmsv(e.g. have $n$ different composition algorithms, use a prng to select any permutation of them. A ...
119 views

Extracting Randomness from Mouse Acceleration

I'm working on trying to make an "entropy pool" that will be fed as input into an RNG (as in, ex, Fortuna). In order to do so, I need to take various collected data and extract as much entropy as ...
56 views

Can randomization be proven?

There exists a collection c where c = {1, 2, 3} and a randomization of c, ...
178 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 ...
104 views

Remapping values to bias a uniform set towards a certain curvature [duplicate]

I'm trying to generate random numbers that would be distributed according to a sample curve that I provide in the shape of vertices. I came up with this: ...
41 views

Logarithmic guarantees for randomized search trees

In this paper [1], "treaps" and "randomized search trees" are introduced. The idea is to guarantee logarithmic update and query operations by assigning uniform random priorities to the keys being ...
267 views

Perfect random number generation using normal numbers

This paper describes a computable normal number. One property of normal numbers is that, written in binary, the $i^{th}$ bit is equally likely to be 0 or 1 (in the sense that as $n$ gets large, the ...
265 views

Enumerating sets in a random order

I have multiples arrays. I'd like to enumerate all sets containing exactly one item from each array in a (pseudo-)random order, without explicitly building the array of all sets. Any solution, even ...
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.
266 views

Proof Knuth S algortihm correctness

In the programming pearls book by Jon Bentley, there is a section about the problem of finding a random set of m integers from range 0 to n-1 integers. To do so they use Knuth's algorithm given by the ...
745 views

Hash multiple integers directly using FNV-1a

An alternative version of FNV-1a hash spread on the internet, which operates directly on integers instead of bytes. The offset basis and prime are the same used in the original version, which operates ...
312 views

Which neural network topology is the most efficient to generate randomly shaped letters?

I have created some unique shapes, so-called "letters" for a custom alphabet, all of which can fit into 9x9 pixels. Instead of drawing countless more, I try to combine two solutions I saw in a ...
113 views

Uniform sampling from general simplex with a twist [closed]

This is part of a question I had asked elsewhere, and then some of the links redirected me to CS stack exchange. Given $a_1,\dots,a_D$ (all strictly positive), I want to draw points uniformly from ...
82 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 ...
122 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 ...
55 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 ...
84 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 ...
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$ ...