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
2
votes
0answers
31 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 ...
2
votes
0answers
38 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)$ ...
1
vote
1answer
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:
...
3
votes
1answer
180 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 ...
3
votes
0answers
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 ...
0
votes
1answer
30 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 ...
0
votes
1answer
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$
3
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
2answers
64 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.
1
vote
1answer
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 ...
3
votes
1answer
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 ...
0
votes
3answers
75 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 ...
1
vote
2answers
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 ...
0
votes
1answer
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(...
2
votes
2answers
180 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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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}$ ...
1
vote
1answer
41 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 ...
22
votes
6answers
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 ...
2
votes
1answer
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,...
31
votes
2answers
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 ...
3
votes
3answers
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 ...
3
votes
1answer
52 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 ...
1
vote
1answer
64 views
Uniformly random iteration of subtrees
I want to iterate through the first $k$ elements of a randomly ordered list containing all subtrees for a given tree. The definition of subtrees that I'm using is: "A subtree of $T$ is a subgraph of $...
3
votes
1answer
86 views
PRNG for a gaussian distribution?
I need suggestions for algorithm for Pseudo random number generators that will produce a near gaussian distribution (bell curve) for automatically generating test data. I know that PRNG produce ...
2
votes
1answer
38 views
Sublinear Homomorphism Property Testing Counter Example
This is a homework question, so I'm not looking for answers, just general guidance.
I'm looking at a Sublinear Algorithms survey where (Group) Homomorphism property testing is discussed. The case of ...
1
vote
1answer
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 ...
1
vote
0answers
119 views
Matrix with zero spectral radius
I need an algorithm which generates a random matrix with spectral radius equal zero.
The only solution I have so far is to generate two vectors $v,w$, normal onto each other ($v\perp w$), and then ...
-1
votes
1answer
106 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
31 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
31 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 ...
7
votes
1answer
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,...
2
votes
2answers
420 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
35 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
162 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
158 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
81 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
413 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 ...
25
votes
11answers
9k 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
58 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
65 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 ...
7
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
215 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 ...
2
votes
1answer
126 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)$...
3
votes
1answer
124 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, ...
