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

204 questions
Filter by
Sorted by
Tagged with
50 views

### Sampling from specific random distribution on sets

I have a random distribution on sets in mind, that has three parameters: $n, w, k$. The goal is to sample sets of $k$ integers from $[0, n)$ (without replacement) such that the elements within each ...
34 views

### Permutation with stable partitions

I am searching a fast pseudo-random permutation function with the following requirements. Given a predefined set of values $V$ and an integer $k$. Split $V$ to $k$ subset, and iterate over any subset ...
40 views

### Randomized Assignment Problem

Given $x_1,...,x_n,y_1,...,y_n\in \mathbb{R}^d$ find a permutation matrix $P\in\mathbb{S}_d$ that minimizes $\sum_{ij}P_{ij}|x_i-y_j|$. This is an assignment problem and can be solved in $O(n^3+n^2d)$ ...
16k 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 ...
30 views

### Median of distribution with memory constraint

Task I want to approximate the median of a given distribution $D$ that I can sample from. A simple algorithm for this, using $n$ samples, is: ...
182 views

### Weighted Online Matching - randomized algorithms

Let's consider the edge weighted online matching problem. The Vertices arrive online and reveal all their current edges and edge-weights $w_e>0$. The goal is to maximize the matchings weight. An ...
334 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$ ...
31 views

### Problem with proving that $RP \subseteq NP$ : a non-deterministic TM for a language $L \in RP$

I'm having a small issue with wikipedia's proof that $RP \subseteq NP$: An alternative characterization of RP that is sometimes easier to use is the set of problems recognizable by nondeterministic ...
15 views

### How to generate a uniform random sample of unique vertex pairings from a undirected graph under constraint?

I'm working on a research project where I have to pair up entities together and analyze outcomes. Normally, without constraints on how the entities can be paired, I could easily select one random ...
29 views

### Is the BPP class closed for union and intersection?

Just like the title says. I want to prove that given two languages $L_1,L_2 \in BPP$, $L_1 \cup L_2 \in BPP$ and $L_1 \cap L_2 \in BPP$
11k views

### Differences and relationships between randomized and nondeterministic algorithms?

What differences and relationships are between randomized algorithms and nondeterministic algorithms? From Wikipedia A randomized algorithm is an algorithm which employs a degree of randomness ...
33 views

### Reference asking: phase transition in SAT

This is not a technical question, I hope this community has a room for such questions, but I will delete it in case this is inappropriate. It has been experimentally observed (e.g. here) that when ...
88 views

### PAC learning vs. learning on uniform distribution

The class of function $\mathcal{F}$ is PAC-learnable if there exists an algorithm $A$ such that for any distribution $D$, any unknown function $f$ and any $\epsilon, \delta$ it holds that there exists ...
57 views

### Shuffling a collection too large for memory

I have a set that is too large to hold in memory but I have a function that I can use to compute a value within the set given an index. I'm curious if there's a standard way to shuffle this set, a ...
13 views

### How to implement random sampling with continuous variables?

How functions like rnorm in R (and similar functions) create a random sample ? If I want to implement one algorithm to simulate this procedure what can I do? When you have the pdf or pmf of a ...
23 views

### Algorithm For Random Distribution of Prizes Over A Given Time Period

I have been assigned a task to come up with an algorithm for evenly distributing prizes over a given time frame, I am looking for advice as I am a bit stumped on where to start. Here are my ...
65 views

### Grid Puzzle Split Algorithm

I want to generate a random partition of an $N\times N$ grid into $N$ connected groups having $N$ tiles each. How would I do this? Max grid size will be 10x10. Below is an example for a 5x5 grid.
14 views

### Is there a theorem which relates calculating the total number of a combinatorial object with picking one at random?

A common algorithmic challenge is to generate an object of a certain kind, uniformly at random. For example, generating a random permutation of size $k$ from a given (multi)set of $N$ characters, as ...
65 views

### generalizing ball-bin problem to k-universal family

I am trying to solve a question in the book on Probability and Computing by Michael Mitzenmacher, Eli Upfal. The question asks to generalize ball-bin problem for 2-universal hashing to $k$-universal ...
17k 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 ...
77 views

### How likely is for a pseudorandom number generator to generate a long sequence of similar numbers?

How likely is for a pseudorandom number generator to generate a long sequence of similar numbers? "Similar numbers" could be same numbers, or numbers from a given range. For example, if we consider ...
347 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 ...
74 views

### Can neural network process randomness?

So the question is : Is it theoretically possible to feed a neural network with some random values to expect an output since randomness is a lack of knowledge in most case. For this question, I've ...
38 views

### Reservoir Sampling vs Round Robin

You are given a List of numbers (length unknown). Let's say the length is 10. GetRandom(List) is called once. If implemented correctly, each number has 1/10 probability of being returned. GetRandom(...
97 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 ...
75 views

### Concentration bound for sum of dependent geometric random variable?

consider following persudocode: i=0 while(i< k): uniformly pick u,v in V if(uv in E): remove uv form E; i++; let $T$ be the number of ...
54 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 ...
183 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 ...
61 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}$ ...
30 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 ...
49 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 ...
44 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 ...
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$ ...
9k 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 ...
86 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 ...
53 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 ...
65 views

212 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 match, start over,...
425 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 ...
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 ...