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.
255
questions
2
votes
1
answer
243
views
Why doesn't this put $BPP$ in $NP$?
From Sipser Gacs we know $x\in L(M)$ for a machine $M\in BPP$ $\iff$ $$\exists t_1,\dots,t_{|r|}\forall r\in\{0,1\}^{|r|}\vee_{i\in\{1,\dots,|r|\}}M(x,r\oplus t_i)=1.$$
From Adleman we know $x\in L(M)$...
- 2,891
3
votes
1
answer
283
views
RNG: removing bias by counting bits
I have a hardware RNG that sends me some random bits. Due to nature of that RNG, the source is biased. Then, the bitstream is processed in a following way to remove the bias:
two counters are used, ...
- 379
1
vote
1
answer
534
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 ...
- 113
0
votes
1
answer
71
views
Looping through random integers - will it halt with probability 1?
Say I have a simple program that has the pseudocode like this:
...
- 469
1
vote
1
answer
77
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 ...
- 147
6
votes
3
answers
3k
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 ...
- 61
2
votes
2
answers
120
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 ...
- 391
7
votes
3
answers
743
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 ...
- 171
2
votes
1
answer
186
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$ ...
1
vote
3
answers
223
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 ...
- 1,602
1
vote
0
answers
232
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. ...
- 1,602
0
votes
1
answer
44
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. ...
- 103
8
votes
3
answers
638
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 ...
- 183
3
votes
1
answer
2k
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 ...
- 33
5
votes
2
answers
586
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 ...
- 53
2
votes
3
answers
578
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 ...
- 555
0
votes
1
answer
54
views
Difference in scale between mean page loading times and exponentially distributed page loading times?
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 ...
- 101
0
votes
2
answers
4k
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 ...
- 103
2
votes
3
answers
3k
views
Time complexity of this while loop
So, i would like to know the time complexity of the following codes:
...
- 131
0
votes
0
answers
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 ...
- 319
2
votes
0
answers
33
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 ...
- 141
1
vote
3
answers
324
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 ...
4
votes
1
answer
59
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 ...
- 143
1
vote
1
answer
197
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 ...
- 315
1
vote
0
answers
36
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 ...
- 111
0
votes
1
answer
69
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 ...
fsacer
2
votes
1
answer
228
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 ...
- 1,602
2
votes
1
answer
170
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:
...
- 3,040
2
votes
1
answer
813
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 ...
- 123
0
votes
0
answers
46
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 ...
- 2,891
3
votes
2
answers
779
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 ...
- 83
7
votes
2
answers
298
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 ...
2
votes
1
answer
233
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 ...
- 359
1
vote
2
answers
270
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 ...
- 1,617
3
votes
1
answer
143
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 ...
- 771
-1
votes
1
answer
62
views
Can randomization be proven?
There exists a collection c where c = {1, 2, 3} and a randomization of c, ...
- 1
7
votes
2
answers
283
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 ...
- 73
0
votes
1
answer
113
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:
...
4
votes
1
answer
54
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 ...
- 141
3
votes
1
answer
323
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 ...
4
votes
1
answer
270
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 ...
- 143
6
votes
1
answer
77
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.
- 778
-1
votes
1
answer
535
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 ...
- 149
3
votes
1
answer
1k
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 ...
- 188
1
vote
1
answer
373
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
1
vote
0
answers
171
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
...
- 111
0
votes
1
answer
104
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 ...
- 232
6
votes
2
answers
134
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 ...
- 5,994
3
votes
1
answer
79
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 ...
- 369
0
votes
1
answer
95
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 ...
- 109