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.
236
questions
0
votes
0answers
35 views
Random team generator with constraints
I would like to create a tool to split a group of persons into multiple teams "randomly".
Here is a mockup that shows the UI: https://ibb.co/jDHFkdH
Inputs
To generate the teams, the tool ...
0
votes
1answer
30 views
What's the sum of heights of a random binary search tree
What's the sum of heights of a random binary search tree?
By a random binary search tree, I mean the usual definition: you have $n$ keys to be inserted, and all Permutations are equally likely.
The ...
4
votes
0answers
46 views
Uniformly random decimal numbers
Due to finite precision of number representations, we face situations like:
In: 0.1+0.1+0.1==0.3
Out: False
(on my ...
1
vote
1answer
17 views
Modifying the probability of sucess of an algorithm
This is motivated from a homework question. Let $A$ be an algorithm with probability of success equal to $q$ for solving a given problem. Let $p \in (0, 1)$. Find an algorithm that has a probability ...
1
vote
0answers
27 views
What is the most random Markov martingale?
Consider a boxing match between players A and B. If A wins, then $1$ point is gained; otherwise $1$ point is lost. Assume that $A$ is as same good as B. Denote by $X_t$ the expected point of A at time ...
1
vote
0answers
66 views
Hardness result for online matching
Currently studying the following paper:
"Fair Allocation in Online Markets" - Gollapudi and Panigrahi 2014
In which they present Theorem 2 as a hardness result for online maxmin matchings (...
1
vote
3answers
62 views
Is every binary sequence the output of some meaningful-text-input algorithm?
Here is the problem: Let's say we have a random binary sequence, just an arbitrary sequence of zeroes and ones (of some arbitrary length of digits). Can we find an algorithm that would decode/...
1
vote
1answer
25 views
Why does random noise in recurring task periods result in uniform period offsets?
I have a recurring task which finished just now. I schedule it to run every ten minutes; the task will reoccur $10n$ minutes from now for all positive $n$. If instead I choose 50/50 between ten ...
1
vote
0answers
15 views
Distribution independence property testing
I have been reading the proof in the following paper, and I am unable to understand some parts in the proof. This paper shows that a distribution $A$ over $[n]\times[m]$, $n\geq m$, can be $\epsilon$-...
0
votes
2answers
52 views
2
votes
1answer
97 views
Some questions about `RANDOM(a, b)`
This is a question from CLRS:
Describe an implementation of the procedure RANDOM(a, b) that only makes calls
to RANDOM(0, 1). What is the expected running time of your procedure, as a
function of $a$ ...
-1
votes
1answer
48 views
computer science paper: Why t14 and t19 are unreachable and why t19 reachable?
I am reading the paper[1] at: https://arxiv.org/abs/1905.07147
The paper says in Overview section 3:
The figure shows a constructed function Bar, which is written in
Solidity and contained in a smart ...
0
votes
0answers
39 views
Disconnect giant component in random graphs by edge deletion
From a complete random graph (ER graph) after deleting an edge randomly with some probability (p) in each step how many edge deletion occurs to make the graph disconnected or break the giant component?...
4
votes
1answer
203 views
Randomly selecting element from data structure, probability based on weight
I have a list of elements, each with an id and a weight.
A: The weight should be directly proportional to the probability of being randomly selected: An element with weight 10 should be twice as ...
0
votes
0answers
34 views
How can I randomly sample from the set of NP Complete problems?
I'd like to create some program that can keep spitting out verification algorithms.
My verification algorithms take two inputs: problem instance, and solution (both encoded in binary), and output True ...
1
vote
1answer
34 views
Definition of RP/poly is not clear!
In Motwani and Raghavan's textbook, p38-39, they states:
A sequence $C_1, C_2, C_3, \dots$ of circuits is a circuit family for function $f_n\colon {0,1}^n \rightarrow \{0,1\}$ if $C_n$ has $n$ inputs ...
1
vote
1answer
66 views
Could AI be used to detect when a human is picking survey response options randomly?
Context: I am a clinical psych researcher dabbling in machine learning.
Humans cannot be truly random. Therefore, could machine learning be used to analyze a string of numbers and determine the ...
1
vote
1answer
49 views
Randomized Version of NP
I came across interactive proofs and randomized computation, in particular, i read about the complexity classes $\text{IP}, \text{BPP}, \text{RP}$, etc.
Since the above classes are well-known, I will ...
1
vote
1answer
39 views
Reinforcement learining basics - is it possible to deal with environment with random events
As part of data science course I would like to solve particular problem with reinforcement learning algorithm.
I believe I understand general concept, however the problems I had read about up till now ...
1
vote
1answer
26 views
Are there any established methods for generating random graphs/networks that are both planar and meshlike?
There are well-defined methods for generating random graphs / networks that satisfy certain properties, including small-world graphs, scale-free networks, and totally random non-planar graphs. I am ...
1
vote
1answer
41 views
Computational indistinguishability for any distribution using a Chernoff bound
I had a question about a general statement regarding finding a computationally indistinguishable distribution given any distribution, observed (in the third paragraph of Section 11, page 31) here. ...
2
votes
1answer
59 views
Shared randomness does not increase capacity of a noisy channel - Why?
Why is it the case that when Alice and Bob use a noisy channel for communication, the capacity of the channel does not increase even if they are allowed to share pre-distributed randomness?
This is ...
2
votes
1answer
23 views
Is there a way to measure the maximum random bits of the outputs of a generator?
I want to give examples to explain want I want to know first. Let $G \colon s \mapsto G(s)$ be a PRG.
Let $F_{1} \colon s \mapsto G(s) \Vert b$, where $b = \bigoplus_{k = 1}^{|G(s)|} G(s)[k]$. ...
0
votes
1answer
91 views
How to position images within a canvas while avoiding overlapping
I have a canvas. On this canvas, I want to position 1, 2 or 3 images. The images can be positioned anywhere on the canvas just as long as they're within the canvas. The images move by their top-left ...
0
votes
2answers
67 views
Randomize List with guaranteed Index Change
I usually post on Stackoverflow, but I got stuck with a problem which I think fits better here and I hope someone can help me. The task ist pretty simple:
Shuffle/Randomize an array/list
conditions:
...
0
votes
1answer
269 views
Algorithmic challenge: generate a list of random non overlapping squares
For an undisclosed reason, I need a list of $n$ squares in a two dimensions space where each square does not overlap.
So the challenge is simply: given a two dimensional area $a$ (...
0
votes
0answers
17 views
Computer Generated If-Statements to create A.I
Just a thought-experiment, could a program be written so that the computer generates it's own if-statements (semi/randomly) and runs them, gathers the results, then tests them in new scenarios, and ...
4
votes
1answer
205 views
Similarity Of Matrices
Give a randomized algorithm that takes input two $n \times n$ matrices $A$ and $B$ with integer
entries and does the following: If $A$ and $B$ are similar, then with high probability the algorithm ...
0
votes
1answer
43 views
Are the algorithms for picking between 2 numbers randomly a lot less computer intensive than the algorithms for picking almost any number randomly?
Are the algorithms for picking between 2 numbers randomly a lot less computer intensive than the algorithms for picking almost any number randomly? The definition of random for our purpose is anything ...
3
votes
1answer
105 views
Under which conditions a given program is deterministic on x86_64 machines?
Given a certain x86_64 "vanilla" binary, without micro-architecture instructions, which can therefore be executed by any x86_64 computer, what are the conditions for the result to be ...
0
votes
2answers
81 views
Benford's law is not working?
So I recently came across Benford's law and immediately tried to code it out but the answer I got was rather confusing. I've been thinking about it for about an hour now and still can't get it, I ...
0
votes
1answer
30 views
How does random number probabilities work in distributed systems?
Let's say I have a code which does coin toss at 25% win probability.
If I run this code n number of times in the same system it will yield ~25% win.
If I run this code on n devices (once each) will ...
3
votes
1answer
62 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 ...
2
votes
0answers
46 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
46 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
32 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
204 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
31 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 ...
1
vote
1answer
308 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
244 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
50 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
122 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
27 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
77 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
51 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
210 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
15 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
132 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
334 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
102 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 ...
