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.
247
questions
0
votes
1
answer
15
views
Does a random phenomenon have a pre defined probability distribution? what does it mean for something to be random?
While studying Shannon's notion of perfect secrecy I came upon the idea that a bit is perfectly random if it happens to be 0 or 1 with an equal probability. What does this mean? Also, what can we say ...
- 3
1
vote
1
answer
22
views
construct language in ${\sf BPP \backslash (RP \cup coRP)}$ assuming $\sf RP \neq ZPP$
Problem
This is a HW problem from CMU 15-455 (hw10, p1(a)), spring 17 by Ryan O'Donnell.
Assume $L \in {\sf RP \backslash ZPP}$. Define
$$ L' = \left\{ (x, y) : \text{either $x \in L$ and $y \notin L$,...
- 98
1
vote
1
answer
39
views
Average and max. hitting time to a specific vertex [closed]
Consider simple random walks that stop when reaching a given node $x$ in an undirected, unweighted and connected graph on $n$ nodes.
Let
$H(i,x)$ denote the (expected) hitting time from $i$ to $x$, ...
- 13
1
vote
1
answer
34
views
Naïve array sampling algorithm: the possibility of a item being chosen and its time complexity
This naïve sampling algorithm I am talking about is fairly simple: create a set for storing chosen items first, randomly select an item from the array, and examminate if it is in the set. If it isn't, ...
- 111
1
vote
1
answer
27
views
Why Lavarand (as opposed to other methods of generating random seeds)?
Cloudflare famously uses a wall of lava lamps (https://en.wikipedia.org/wiki/Lavarand) to seed random number generators. But if you're going into the real world to seed your rng, why lava lamps? Why ...
- 11
0
votes
0
answers
20
views
Is it a well-posed question to decide whether a process is deterministic, given that the machine is equipped with a TRNG?
Consider a machine equipped with two input devices: A true random number generator for a fair coin toss, and stdin. I wondered whether it's possible to decide that ...
- 221
1
vote
0
answers
33
views
Probability of a randomised algorithm solving SAT
Let WALKSAT be defined as follows:
Let $σ$ be a random truth assignment to the vars
For $t = 1, 2, . . . , 3n$:
◦ If $\phi$ is satisfied by $σ$, exit the loop
◦ Else, pick an unsatisfied clause $c$ ...
- 379
1
vote
0
answers
19
views
How to select a random node when nodes are untrusted in a distributed network? [closed]
Assume in a distributed network, where the nodes are not trusted and are identified by their public keys, we intend to select one of them in a random process. In such a situation, all of the nodes ...
- 143
0
votes
1
answer
19
views
Can we simply consider a pseudo random number generator to be a function $f: \Bbb{Z}_n \to \Bbb{Z}_n$ for ever-increasing $n$?
On modern architectures, random number generators get seeded by the current system time as a source of randomness, which is nice because it is kind of unpredictable when a process will switch to the ...
0
votes
1
answer
42
views
Are turing machines & equivalents with infinite sized random programs still turing machines?
Are turing machines with an infinite program tape that is completely random, or another example is a Game of Life simulation on an infinite randomly initialized grid, still turing machines, so to ...
- 11
0
votes
0
answers
386
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 ...
- 101
0
votes
1
answer
49
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 ...
- 171
4
votes
0
answers
54
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 ...
- 603
1
vote
1
answer
20
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 ...
- 81
1
vote
0
answers
31
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 ...
- 119
1
vote
0
answers
70
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 (...
- 11
1
vote
3
answers
70
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/...
- 111
1
vote
1
answer
29
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 ...
- 689
1
vote
0
answers
17
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$-...
- 11
0
votes
2
answers
53
views
2
votes
1
answer
117
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$ ...
- 377
-1
votes
1
answer
49
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 ...
- 249
0
votes
0
answers
43
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?...
- 1
4
votes
1
answer
241
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 ...
- 43
0
votes
0
answers
35
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 ...
- 205
1
vote
1
answer
37
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 ...
- 719
1
vote
1
answer
71
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 ...
- 11
1
vote
1
answer
61
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,543
1
vote
1
answer
72
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 ...
- 113
1
vote
1
answer
31
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
1
answer
46
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. ...
- 219
2
votes
1
answer
67
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 ...
- 262
2
votes
1
answer
24
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]$. ...
- 589
0
votes
1
answer
162
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 ...
- 107
0
votes
2
answers
96
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:
...
- 101
0
votes
1
answer
445
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
0
answers
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 ...
- 1
4
votes
1
answer
236
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
1
answer
47
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 ...
- 1
3
votes
1
answer
140
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 ...
user82256
3
votes
0
answers
49
views
Assuming $\mathsf{P=BPP}$ would it be possible to derandomize the verifier in Interactive Proof systems?
By the definition, in an Interactive Proof system the verifier is allowed to generate random numbers, which allows the omniscient prover to not fool it in the vast majority of cases for every problem ...
- 1,393
0
votes
2
answers
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 ...
- 101
0
votes
1
answer
45
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 ...
- 101
3
votes
1
answer
66
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 ...
- 12.4k
2
votes
0
answers
48
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 ...
- 121
2
votes
0
answers
51
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
1
answer
36
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:
...
- 113
3
votes
1
answer
209
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 ...
- 149
3
votes
0
answers
36
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 ...
- 31
1
vote
1
answer
444
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 ...
- 57