Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

-1
votes
1answer
60 views

Is there a name for this shuffle algorithm?

Is there a standard name for the following algorithm? At each step, the code picks an index, remove the object at that index, and remember to never pick that index again. See the following ...
0
votes
2answers
29 views

Random conditional association

I have a really specific problem to solve and i'm looking for an existing algorithm to help me (i hope i'm in the right section of stackExchange). I would have to make "random" association between ...
1
vote
1answer
20 views

On uniform randomness of the weight of the remaining edges of a graph after deleting some of them

Suppose we have a graph $G(V,E,W)$, where $V$ and $E$ are the set of vertices and edges and $W$ is non-negative weight on the edges. Let $w(e)$ be the weight of edge $e$ and $N(e)$ be the neighboring ...
0
votes
0answers
44 views

If P=BPP, then Is it correct that IP=NP?

I'm now studying Interactive Proof System in Goldreich's textbook and here. I have the following question: Suppose P=BPP, then this show that randomness doesn't give us power over deterministic ...
5
votes
1answer
99 views

Is it possible to simulate a fair coin with a finite number of tossing of a biased one?

It is a classic problem to simulate a fair coin with a biased one. According to Fair Coin (wiki), John von Neumann gave the following procedure: Toss the coin twice. If the results ...
1
vote
2answers
72 views

How to determine seed collision probability in a PRNG?

I want to use a PRNG to generate random patterns. I would provide the PRNG with a hash value as a seed. Ideally, the seed size would be 64-bit or 128-bit and I would expect no collisions if the seeds ...
2
votes
1answer
25 views

Is there a complexity class “BQP without error”?

I was wondering if there is a complexity class for problems that can be solved efficiently by a quantum computer such that it always gives the right answer? For example the Deutsch-Josza algorithm ...
1
vote
0answers
62 views

Generate higher dimensional pink noise

1D Pink noise, is easy enough to generate. See https://www.dsprelated.com/showarticle/908.php for example. What about higher-dimensional pink noise, such as 2D or 3D pink noise? Is there an algorithm ...
3
votes
1answer
79 views

How could you characterize “true randomness” of a finite sequence?

This question occurred to me while reading http://arxiv.org/abs/1806.08762/ Any observed sequence is necessarily finite, and any finite sequence is computable, either by explicitly storing all the ...
0
votes
1answer
49 views

Finding the Entropy of a random experiment with probability of $\frac{1}{3}$

Entropy is the randomness collected by an operating system or application for use in Cryptography or other uses that require random data. The formula for Entropy is $$H(p_1, ..., p_k)=-\sum_{i=1}^{k} ...
2
votes
1answer
124 views

Generating uniformly random bits from a stream of arbitrarily biased bits

Say we have a function called GenBiasedBit. This function returns 1 with probability p (where p is an unknown real number between 0 and 1 exclusive) and returns 0 with probability 1 − p. How could I ...
24
votes
11answers
8k views

Is von Neumann's randomness in sin quote no longer applicable?

Some chap said the following: Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin. That's always taken to mean that you can't generate ...
1
vote
1answer
53 views

Are there any stochastic models of non determinism in the rate of program execution?

We know that typical operating systems and high level languages (especially those with garbage collection) cannot be used for real time operating systems. Java & jet engines don't mix, and ...
1
vote
2answers
49 views

Would using mouse position in the below scenario generate true random numbers?

I'm having trouble wrapping my head around random number generation so I figure it would be better to ask now, rather than screw up later. Let's say I want to write a function that generates a random ...
6
votes
3answers
2k views

Problem with the pseudo random number generator One-Time-Pad

I've started learning cryptography in class and we've come across One-Time-Pads, in which the key (uniformally agreed upon) is as long as the message itself. Then you turn the message into bits, do $...
1
vote
1answer
40 views

Placing small circles randomly inside a larger circle, where no two small circles intersect

Sorry if this is the wrong place to ask, was unsure...let me know if it belongs some where else. So i am trying to work out a way to write an algorithm to place a series of small circles of a set ...
0
votes
0answers
17 views

Creating a Visual Model of Network Traffic Flow

I am a beginner in computer science and networking softwares. I need some help creating a visual model of network traffic flow. I want to create a visual model of a network in flux and the end-to-end ...
2
votes
1answer
60 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
votes
1answer
42 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, ...
0
votes
1answer
49 views

On $BPP\not=SUBEXP$ and $SUBEXP\not\subseteq P/poly$?

Let $SUBEXP\not\subseteq P/poly$ hold. We know $BPP\subseteq P/poly$. So we know $SUBEXP\not\subseteq BPP$ holds. So either $BPP \cap SUBEXP=BPP$ holds or $BPP \cap SUBEXP\not=BPP$ holds. In https:...
2
votes
1answer
88 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 ...
0
votes
1answer
36 views

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

Say I have a simple program that has the pseudocode like this: ...
1
vote
1answer
36 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 ...
4
votes
3answers
793 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 ...
3
votes
2answers
46 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 ...
3
votes
2answers
202 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 ...
1
vote
1answer
81 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
3answers
82 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
vote
0answers
31 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. ...
0
votes
1answer
31 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. ...
7
votes
2answers
143 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 ...
2
votes
1answer
351 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 ...
5
votes
2answers
292 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 ...
2
votes
3answers
311 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 ...
0
votes
1answer
40 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 ...
0
votes
2answers
948 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 ...
2
votes
3answers
2k views

Time complexity of this while loop

So, i would like to know the time complexity of the following codes: ...
0
votes
0answers
18 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 ...
1
vote
0answers
22 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 ...
0
votes
3answers
175 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
1answer
38 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 ...
1
vote
1answer
53 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 ...
1
vote
0answers
28 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 ...
0
votes
1answer
38 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 ...
2
votes
1answer
118 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 ...
3
votes
1answer
66 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
votes
1answer
361 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 ...
0
votes
0answers
40 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 ...
3
votes
2answers
151 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 ...
7
votes
2answers
166 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 ...