# 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.

188 questions
Filter by
Sorted by
Tagged with
45 views

### If current time in milliseconds is considered good enough random seed for a pseudorandom number generator, why not just use that time directly?

I was reading about pseudorandom number generators and how they need a seed and how that seed is usually current system time in milliseconds. One of the most common algorithms is the linear ...
29 views

### Simple generator of pseudo-random permutations of variable length short sequence

The problem in front of me is to write a function (from scratch) to permute n elements, where n is an argument. I decided to break it down to applying Knuth's shuffles algorithm, therefore I needed to ...
48 views

### Need help regarding random password generator: Urgent [closed]

I had generated a random password from a website which unfortunately has put me into trouble. The password contains 26 characters which includes alphabets, numbers and special characters. My trouble ...
48 views

### Finding efficient randomized algorithm

I'm doing a course on randomized algorithms and I've encountered a question that I'm struggling to solve. Given a system of $m$ linear equations with $n$ variables over finite field $\mathbb{F_2}$ ...
7 views

### How to input random values (constraints) of any variables in case of formulating Linear Programming Problem?

Suppose, Min 2x+3y Subject to, x=2,x=5,x=7 y=5, y=9 is a linear program. Where x holds the values 2 or 5 or 7 and y holds the values 5 or 9. Then what should the correct ...
28 views

### Derandomize MAX-CUT problem using $\log n$ bits

Consider the MAX-CUT problem. We can flip $n$ coins to generate a random cut, and by linearity of expectation we get that with "good probability" our cut we'll be bigger then $\frac{n}{2}$. Using ...
23 views

### Proving $BPP[\frac{1}{3},\frac{2}{3}] = BPP[a,a+\gamma]$ where $0<a<a+\gamma<1$

I can prove $BPP[\frac{1}{3},\frac{2}{3}] \subseteq BPP[a,a+\gamma]$ by sampling the promised $BPP[\frac{1}{3},\frac{2}{3}]$ Turing machine $k$ times and accept if $k\cdot(a+\frac{1}{2}\gamma)$ of the ...
32 views

### Are real computers capable of producing true random series with a program of finite length?

Suppose that one has a Blum–Shub–Smale machine. Is it possible to write down a program of finite length that produces a series of numbers, with each consisting of a finite number of digits, such that ...
8k views

### Can we generate random numbers using irrational numbers like π and e?

Irrational numbers like $\pi$, $e$ and $\sqrt{2}$ have a unique and non-repeating sequence after the decimal point. If we extract the $n$-th digit from such numbers (where $n$ is the number of times ...
70 views

### What doest it mean: “computer is an intelligence amplifier”?

There is one example in Kolmogorov complexity books and related articles: Consider we have a monkey at a typewriter and a monkey at a computer keyboard. If the monkey types at random on a typewriter,...
2k views

### Simulating a probability of 1 of 2^N with less than N random bits

Say I need to simulate the following discrete distribution: $$P(X = k) = \begin{cases} \frac{1}{2^N}, & \text{if k = 1} \\ 1 - \frac{1}{2^N}, & \text{if k = 0} \end{cases}$$ The most ...
36 views

### How good (or bad) is my makeshift PRNG?

Say I have designed a makeshift PRNG for my personal amusement, now I would like to see how good it is. How do I benchmark its "randomness"? Ideally, I want to know a statistics test, such that if I ...
50 views

### Random observations of a total ordering, how much they tell us?

Suppose we have a total ordering over elements $a_1,a_2, ..., a_n$, meaning there is permutation $\pi$ such that $a_{\pi(1)}<a_{\pi(2)}<...<a_{\pi(n)}$. But we don't know $\pi$. What we know ...
50 views

83 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, ...
192 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 ...
39 views

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

Say I have a simple program that has the pseudocode like this: ...
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 ...
1k 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 ...
53 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 ...
380 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 ...
120 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$ ...
84 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 ...
46 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. ...
35 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. ...
230 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 ...
938 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 ...
332 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 ...
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 ...