Questions tagged [randomness]
Randomness is a key component of probabilistic algorithms, many combinatorial aarguments, the analysis of hashing functions, and in cryptography, among other applications.
164
questions
3
votes
0
answers
58
views
Are there any problems in $\mathsf{BPP}$ that are known to be $\mathsf{RP}$-hard or $\mathsf{coRP}$-hard?
It's suspected that probabilistic complexity classes such as $\mathsf{RP}$ or $\mathsf{BPP}$ don't have complete problems. Of course, their promise counterparts have complete problems, but I am not ...
- 275
2
votes
1
answer
171
views
Do pseudo-random number generator test batteries have any theoretical grounding?
There are a lot of PRNG test batteries, like DieHarder. They do check that some statistical tests expected for random sequence are indeed present.
But is there any theoretical motivation, why this ...
- 295
0
votes
0
answers
67
views
Are there any examples of problems in ZPP not yet in P?
Is there a problem of which we can prove that it is in ZPP but we don’t yet know whether it’s in P or not?
- 177
3
votes
0
answers
122
views
Inverse of leftover hash lemma
Leftover hash lemma:
Let $X$ be a random variable over $X \in {\mathcal {X}}$ and let $m>0$. Let $h: {\mathcal S} \times {\mathcal X} \rightarrow \{0,1\}^m$ be a 2-universal hash function. If $m \...
- 778
2
votes
1
answer
280
views
Chernoff bound for weighted sums of Bernoulli random variables
I tried to prove the following Chernoff-type bound when doing research, and found that it is of indepent interest.
Let $X_1, \dots, X_n$ be independent random varibles such that each $X_i$ is a ...
- 23
0
votes
0
answers
32
views
What are the two quantities involved in the tradeoff for a language to follow Zipf's law?
In any human (and non-human) language the frequency distribution of words follows Zipf's law, which states that the slope of the linear regression for the frequency distribution of words vs the rank ...
- 101
13
votes
3
answers
2k
views
Expected number of random comparisons needed to sort a list
Consider the task of sorting a list x of size n by repeatedly querying an oracle. The oracle draws, without replacement, a random pair of indices (i, j), with i != j, and returns (i, j) if x[i] < x[...
- 419
5
votes
1
answer
296
views
Hardness assumption: an NP-complete problem whose ratio of hard instances do not tend to zero?
I am wondering about the following property $\text{(P)}$ of an $NP$-complete language $L$
$\begin{align}\exists M\text{ a polytime machine}\lim_{n\to\infty}P(\text{M solves a random instance of size $...
- 153
1
vote
0
answers
232
views
Converse form of Chernoff bound
Suppose $X_1,\ldots,X_n$ are i.i.d. random variables, all with mean $p$, and we have the statement that $\Pr\left[\sum_i X_i\geq 0.8n\right]\geq 0.9$, can we use this to conclude anything about $p$ (...
- 251
0
votes
1
answer
133
views
Derandomizing arbitrary width *read-many* and *ordered* branching programs?
Modifying following TedP
We know that derandomizing width $5\leq k\in O(1)$ read many branching programs is equivalent to $BPNC^1=NC^1$ and derandomizing width $k\in\Omega(n)$ read once ordered ...
- 12.8k
0
votes
0
answers
118
views
Creating a random tree (BST) on $n$ elements using a random sequence of zeroes and ones
We have a sorted list of $n$ numbers and we shall create a BST for these numbers.
We create a random sequence of zeroes and ones of length $n$.
We shall make use of this random binary sequence to form ...
- 137
1
vote
0
answers
109
views
Random variates generation in discrete-event simulation models
In discrete-event simulation, most university textbooks (e.g., Law & Kelton, Banks etc.) state that for generating variates for each random variable (e.g., interarrival time, service time etc.) in ...
- 21
10
votes
0
answers
188
views
Provable BPP Hierarchy
No Time Hierarchy theorem is known for $\mathsf{BPTIME}$, however, consider the following simple modification of the definition:
A language is in $\mathsf{ProvableBPTIME}[f(n)]$ if there is a ...
- 13.9k
3
votes
1
answer
188
views
Converting a Bernoulli to a Gaussian
It is not hard to see that, given one sample from a univariate unit-variance Gaussian $X\sim \mathcal{N}(\mu,1)$ with unknown $\mu$ s.t. $0<|\mu|\leq 1$, one can simulate one draw from a
"...
- 4,451
4
votes
1
answer
196
views
Generating $k$ random bits from a pdf with entropy $H(p) = k$
All the sources online say that, intuitively, a distribution with entropy $k$ has $k$ bits of pure randomness in it.
So can we formalize this as follows? Suppose I can only sample from my distribution,...
- 607
0
votes
1
answer
206
views
Upper bound on Independence Number of Random Regular Graph with degree $\Theta(\sqrt{|V|} \log^2 |V|)$
Let $G=(V,E)$ be a random $\Delta$-regular graph with $\Delta \in \Theta(\sqrt{|V|} \log^2 |V|)$. I'm analysing an algorithm having asymptotic running time crucially depending on the Independence ...
- 6,780
1
vote
1
answer
286
views
How come Wikipedia says that Random Turing Machines can provide uncomputable output?
Wikipedia article mentioned : Hypercomputation
The third paragraph starts off with:
Technically, the output of a random Turing machine is uncomputable; however, most hypercomputing literature focuses ...
- 173
12
votes
2
answers
368
views
Is there an assumption that implies $P=ZPP$ which is not known to imply $P=BPP$?
There are assumptions that are known to imply that $P = BPP$. For example, if there exists a function in $E = DTIME(2^{O(n)})$ that has circuit complexity $2^{\Omega(n)}$, then $P = BPP$ [1]. Clearly, ...
- 123
0
votes
0
answers
75
views
Randomized Reduction for Maximization Problem
I have two maximization problems $P_1$ and $P_2$ where the decision version $L_1 = \{(x, t) : \operatorname{Val}_1(x)\ge t\}$ of $P_1$ is $\mathsf{NP}$-complete. Let $f:P_1\to P_2$ be a randomized ...
- 101
-1
votes
1
answer
243
views
Does two-sided error have more capability than one-sided error?
From $P=RP$ extrapolation we might think $EXP=REXP$.
What evidence do we have $BPP\subseteq REXP$?
What consequence $REXP\subseteq BPP$ gives other than what $EXP\subseteq BPP$ gives?
- 12.8k
4
votes
0
answers
143
views
BPP fragment of a PSPACE complete problem
Consider a PSPACE-complete problem (e.g., TQBF).
Is there a sub-problem in BPP, that is not known to be in P?
Is there a general technique of finding such sub-problems? Are any of them "natural" (i.e....
- 5,531
0
votes
0
answers
87
views
Expected value of a random experiment in a graph
I need to find the expected value of R in the random experiment below.
$$
R = \frac{1}{K} \sum_{C \in \mathcal{H} } \ [\frac{1}{2} |V(C)| * (|V(C)| - 1) - |C|]
$$
$\mathcal{H}$ is a partition on ...
12
votes
1
answer
513
views
Deterministic error reduction, state-of-the-art?
Assume one has a randomized (BPP) algorithm $A$ using $r$ bits of randomness. Natural ways to amplify its probability of success to $1-\delta$, for any chosen $\delta>0$, are
Independent runs + ...
- 4,451
2
votes
1
answer
125
views
Lower bound on the worst-case unbiased coin flips to sample a distribution?
Say that we have a distribution $\mathcal{D}$ such that all probabitilities associated with it are $p$-bit fixed precision numbers, so:
$$
\Pr_{X\sim \mathcal{D}}[X = k] =\sum_{i = 1}^p \frac{k_i}{2^i}...
- 918
2
votes
1
answer
454
views
How to use a 𝑝-coin so a TM can decide an undecidable language in polynomial time? [closed]
In "Computational complexity- A modern approach" book (page 117) for the lemma 7.12 (following) the author mentioned that if the ρ is efficiently computable ρ-coin cannot give probabilistic algorithm ...
- 29
2
votes
1
answer
98
views
Robustness to non-uniform randomness vs. one-sidedness
Consider any problem where, fixing two (disjoint) subsets $\mathcal{Y},\mathcal{N}\subseteq \{0,1\}^n$ of the input space, the goal is to obtain a randomized algorithm $D$ which, given a uniformly ...
- 4,451
3
votes
1
answer
248
views
Optimal bounds for $k$-wise non-uniform random bits
Let $k\geq 2$ be a constant (in my case, $k=4$), and $n,t \geq 0$ be integers such that $2^t \leq n$.
What is the smallest sample space (or, equivalent, how many true independent random bits are ...
- 4,451
4
votes
1
answer
175
views
Strong seeded randomness extractors with low entropy loss
I would like to implement a strong seeded randomness extractor for flat sources as a part of my project.
Most of the literature on seeded extractors is concentrated on minimizing seed length. ...
- 141
4
votes
1
answer
234
views
Newman's lemma for distributional communication complexity
This may be obvious — sorry if it is.
Newman's lemma (Newman91] shows that any public-coin communication protocol to compute a Boolean function $f\colon \{0,1\}^n\times\{0,1\}^n\to\{0,1\}$ can be ...
- 4,451
0
votes
1
answer
61
views
What forms of randomness are 'allowed' in FPRASs?
I cannot seem to find a source describing randomized approximation schemes ((F)PRAS) that tells me exactly what sort of randomness a program is allowed to use. A priori it seems to me that being able ...
- 71
5
votes
1
answer
167
views
Sets of solutions which it is hard to uniformly sample from, but easy to integrate functions over? (Or compute expectations over?)
I'm curious if there is a problem (e.g. something like perfect matchings on a given graph, number of solutions to a boolean equation, etc. for precise frameowork see JVV86) such that:
1) It is hard ...
- 1,439
5
votes
1
answer
438
views
Distributions which are intractable to sample from?
I'm looking for an interesting family of probability distributions $P$ that is intractable to efficiently sample from.
I'm not sure what the right notion of intractable is, though I know the notion ...
- 1,439
4
votes
0
answers
162
views
research problem for undergraduate majoring in Computer Science and Mathematics
I am wondering if somebody can suggest a small research problem for undergraduate majoring in Computer Science and Mathematics. Would love to work with random matrices or wavelets.
- 141
1
vote
0
answers
140
views
Proof of Sipser-Lautmann Theorem
I have written the following answer as an attempt to prove a variation of Sispser-Lautmann theorem, but it was rejected without any comments. I would appreciate if anyone can find the flaws in this ...
- 21
2
votes
1
answer
196
views
Motivation for randomness extractors
I'm a maths masters student exploring how results in the geometry of finite fields, such as the finite field Kakeya conjecture, applies to randomness extractors. I'm not a computer scientist, and must ...
- 23
-1
votes
1
answer
168
views
Application of the inequality with expectations
Let $\Vert\cdot\Vert$ is a norm in $R^n$. Let $x_1,\dots,x_N$ non-independent Rademacher random variables random variables (variables which are uniform on $\{-1, 1\}$). . By $E$ we denote an ...
- 141
1
vote
2
answers
360
views
Is true randomness and the physical Church-Turing thesis incompatible?
As follow up to Does the physical Church-Turing thesis imply that all physical constants are computable?, I ask if true randomness (as predicted by QM) and the physical Church-Turing thesis are ...
- 471
9
votes
1
answer
202
views
What is the probability that a random Boolean function has a trivial automorphism group?
Given a Boolean function $f$, we have the automorphism group $Aut(f) = \{\sigma \in S_n\ \mid \forall x, f(\sigma(x)) = f(x) \}$.
Are there any known bounds on $Pr_f(Aut(f) \neq 1)$? Is there ...
- 1,572
1
vote
0
answers
139
views
Cluster Assignment in the Stochastic Block Model
Recently, numerous papers have been published about the stochastic block model (SBM). In the literature about SBMs, a plethora of different settings are considered. I am interested in how vertices are ...
- 143
1
vote
0
answers
208
views
An alternative model of a probabilistic Turing machine [closed]
A probabilistic Turing machine operates with an additional tape of random bits, and its output is a random variable with some distribution over the random bits. Is it also useful to talk about the ...
- 111
4
votes
0
answers
188
views
On earlier references for $P=BPP$ and Kolmogorov's possible view on modern breakthroughs involving randomness?
Kolmogorov and Uspenskii in this paper 'http://epubs.siam.org/doi/pdf/10.1137/1132060' speculate P=BPP in 1986. They do this without getting into circuit lower bounds and from a different view which ...
- 12.8k
2
votes
1
answer
450
views
Weighted balls and bins
Suppose I have $n$ balls and $n$ bins. Each ball $i$ has weight $w_i$. Let the total weight be $T = \sum_{i=1}^n w_i$. We throw the balls into the bins randomly, i.e., each ball lands into a random ...
6
votes
1
answer
450
views
Where does the "intuitive" understanding of Kolmogorov complexity fails
Often, the Kolmogorov complexity of some string $x$ is defined as the length of the shortest program producing $x$, for example on wikipedia.
So to give this more formal meaning, define
$$
K'(x) := ...
- 2,037
4
votes
1
answer
328
views
UnambiguousSAT reductions
Let $\Pi$ be an $\mathsf{NP}$-complete problem. It is standard that $3SAT$ and $\Pi$ are reducible from each other.
Let UnambiguousSAT, or USAT for short, denote the promise problem which is 3SAT but ...
- 12.8k
5
votes
1
answer
458
views
Connectivity of a random regular graph of degree $d$
An Erdos-Renyi graph over $n$ vertices and average degree $d$ is not connected whp iff $d < \log n$. I was wondering for what the degree $d$ would a random regular graph of degree $d$ be connected? ...
- 771
10
votes
1
answer
456
views
Can true randomness (provably) be replaced with Kolmogorov randomness for RP?
Have there been any attempts to show that Kolmogorov randomness would be sufficient for RP? Would the probability used in the statement "If the correct answer is YES, then it (the probabilistic Turing ...
- 3,033
2
votes
1
answer
181
views
Probability of random variable $X$ less than $max(Y_i)$
For $\lambda > \mu$, consider independent random variables (i) $X \sim Pois(\mu)$ and (ii) $Y_i \sim Pois(\lambda),\;i\in{1,2}$.
Question : Can we upper-bound the following?
$$\mathbb{P}\big(X\...
- 771
3
votes
1
answer
234
views
The average number of compressible strings in a random set of random strings
In the book Elements of Information Theory (p.446), it is stated:
...although there are some simple sequences, most sequences do not have simple descriptions. Similarly, most integers are not simple. ...
- 133
4
votes
0
answers
68
views
Embedding of "large" graphs into random graph
Let $G \sim G_{n,p}$ be a binomial random graph and consider a sequence of graphs $\{H_n\}_n$.
When $|H_n|=\mathcal{O}(1)$, then one knows the exact threshold $p_0$ for embeddabiliy of $H_n$ in $G$.
...
- 243
2
votes
1
answer
535
views
How to generate Extended Finite State Machines Randomly with some properties?
This is related to my academic project
An extended finite state machine is a tuple $SM=(I,S,T)$ (simplified):
$I$ is the set of identifiers and it's divided into two sets Inputs and outputs, for ...
- 87