Questions tagged [probabilistic-algorithms]
Questions about (typically randomized) algorithms that can produce no or an incorrect answer with a certain probability.
154
questions
3
votes
1answer
40 views
Sizing a Cuckoo filter for a subset of elements
Question
I am considering the use of Cuckoo filter for a business case. To simplify the explanation here is an analogy of my needs:
There are over $n = 30 000$ first names that exists in the whole ...
2
votes
1answer
82 views
$k$-coloring in BPP, implies $k$-coloring in ZPP
Consider the next problem:
$k$-COL: Given a graph $G=(V,E)$, does it have a valid $k$-coloring?
I need to prove that if $k$-COL is in BPP, then it is also in ZPP. In other words, show that if there ...
3
votes
1answer
40 views
Is there a complexity class QPP?
The complexity class PP is not considered tractable, because the probability of success can get arbitrarily close to 50% from above as the problem instances get larger, so that (e.g. if this approach ...
2
votes
1answer
26 views
Recover a matrix with minimum number of queries
Alice has a matrix $A \in \{0,1\}^{n \times m}$ such that the sum of each row is $1$. Bob tries to find the indices of the ones (he knows that the sum of each row is $1$). The type of questions Bob ...
2
votes
1answer
44 views
Probability of terminating in a state in a probabilistic algorithm
Suppose i have a circular array of $n$ elements.
At time $t=0$ i am in position 0 of the array. The algorithm moves left or right with probability $p=1/2$ (since the array is circular when it moves ...
2
votes
1answer
28 views
Demonstrating that probability for every possible result is uniform at the end of an algorithm
I have memory of $k$ elements that you can imagine being represented by an array. One by one, the array receives a value corresponding to the time index, for example at $t=1$ the value will be $1$.
At ...
0
votes
0answers
21 views
Chernoff Bounds (upper tail)
For the proof of Chernoff Bounds (upper tail) we suppose δ<2e−1 .
Like in this paper ([see this link ]) 1. Can you tell me why ?
0
votes
0answers
70 views
Prove an estimator
Consider an undirected graph $G=(V,E)$ representing the social network of friendship/trust between students. We would like to form teams of three students that know each other. The question is to ...
0
votes
0answers
20 views
Find expectation and calculate Chernoff bound [duplicate]
We have a group of employees and their company will assign a prize to as many employees as possible by finding the ones probably better than the rest. The company assigned the same 2 tasks to every ...
3
votes
1answer
273 views
Find expectation with Chernoff bound
We have a group of employees and their company will assign a prize to as many employees as possible by finding the ones probably better than the rest. The company assigned the same $2$ tasks to every ...
1
vote
1answer
558 views
Derandomization of vertex cover algorithm
I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set:
Fix some order $e_1, e_2,...,e_m$ over all edges in the edge set E of G, and set $B_0=∅$.
Add to ...
3
votes
1answer
101 views
Grover's algorithm on probabilistic classical machines
As a starting point for this question, I came across this question, which AIUI is citing a construction showing how to simulate quantum circuits with a $PP$ algorithm, i.e. implying quantum ...
1
vote
1answer
16 views
Predicting the outcome of sporting events with multiplicative scoring
In the Olympic format for sport climbing, eight athletes compete in three rounds of climbing. Their final score is the multiplication of their rankings in each round. For example, an athlete who comes ...
4
votes
0answers
44 views
Understanding simulated annealing information theoretically
So I recently rediscovered simulated annealing though a path that others seem to be well aware of. I was aware of Metropolis-Hastings as a sampling algorithm that creates a Markov-Chain who's ...
0
votes
0answers
13 views
What is the probability that an expanding bipartite graph exists with the property, |V1|=|V2|?
I want to find a bound on the above problem, and show that a random graph has a positive probability of being an expanding bipartite with the property, |V1|=|V2|. I am not getting, where should I ...
2
votes
1answer
72 views
Why an error probability of 1/3 in BPP?
BPP is defined as the class of polynomial-time random algorithms which have an error probability of at most 1/3.
But why was 1/3 chosen? If we have an algorithm with some error probability less than ...
1
vote
1answer
31 views
Are there efficient probabilistic multiplication algorithms that use O(n log n) gates?
Recently Harvey and Hoeven published a paper proving that integer multiplication can be performed using at most O(n log n) operations. This algorithm is theoretically interesting, but in practice ...
1
vote
1answer
29 views
Polysize bounded depth circuit for modified MAJORITY problem
I am trying to show the existence of a polynomial size, bounded depth monotone circuit on the inputs $(x_1,\ldots, x_n)$ that gives $1$ if $\sum x_i \geq n/2 + n/\log n$ and $0$ if $\sum x_i \leq n/2 -...
1
vote
1answer
78 views
Can BPP be bounded around any constant other than 1/2?
A language $L$ is in BPP if there exists a randomised TM such that it outputs a correct answer with probability at least $1/2+1/p(n)$ for some polynomial $p(n)$, where $n$ is the length of the input. ...
2
votes
0answers
34 views
Correctness of Karger's min-cut Algorithm
tl;dr in the analysis for Karger's min-cut, the probability of an edge being in the min-cut in the $j$th iteration, $\frac{k}{0.5k(n-j)}$, neglects the fact that all the edges between the two ...
0
votes
0answers
34 views
Construction of hash function with a given distribution
Two questions about the construction of a hash function:
Let $U = \{u_1,...,u_n\}$ be a set of size $n$, and suppose that one is interested in a function $h\colon U \rightarrow [0,1]$ such that $h$ "...
0
votes
0answers
24 views
PCP variant in P with non 0 randomness and polynomial proof
I am trying to show that a particular language $L$ in PCP(log,q) is also in P. The PCP protocol works as follows: log many random bits and checks at q positions in a polynomial length proof. The ...
0
votes
0answers
30 views
Question on preventing k from reducing too quickly during KMV intersection
This question considers KMV, an algorithm that is able to estimate the cardinality (unique item) from a stream of data.
The way it does it is to first map the stream of data to a space that almost ...
0
votes
1answer
29 views
SVM with a priori information about class probabilities
Given are two 2-d sets, each with its own bivariate normal distribution. I need to build an SVM classifier. The a priori probabilities of each class corresponds to the size of its set (20/50 for the ...
3
votes
1answer
66 views
Determine number of values less than mean in one pass through list
The problem statement is as follows:
Can we determine precisely the number of elements less than the mean in a list $A$ of $n$ numbers in only one pass through the array (starting at $A_1$ and ...
1
vote
1answer
33 views
Singleton in a simple SBM
I can't work out the solution to the following exercise:
We have $2n$ vertices grouped in $2$ clusters of equal size. The probability of having an edge between $i$ and $j$ is $p$ if $i$ and $j$ are ...
2
votes
1answer
200 views
How does KMV (k minimum value) perform set intersection better than hyperloglog?
In this paper, the author seems to suggest that theta sketches(a variant of kmv) outperforms hyperloglog in cardinality estimation on the intersection of n way streams.
...
1
vote
0answers
125 views
Perfect Completeness of AM protocols?
I understand the idea behind making a MA protocol perfectly complete. In a MA protocol, Merlin sends a proof $\pi$ which Arthur checks with his machine $V$ by plugging in some random bits $r$ such ...
1
vote
1answer
158 views
Probabilistic r-way cut set algorithm
I am reading Probability and Computing, by Mitzenmacher and Upfal, and the exercise 1.24 asks for a generalized algorithm for finding the cut-set of a Graph.
In this generalized version, instead of ...
3
votes
0answers
37 views
Is the definition of $\textbf{BPP}$ robust for doubly exponential small (or even smaller) error?
$\textbf{BPP}$ is usually defined in terms of probabilistic polynomial-time TMs which have an error probability of at most $\frac{1}{3}$. Furthermore, using the Chernoff bound it can be proven that ...
3
votes
1answer
96 views
Small space hash functions that are weakly but not strongly universal
This is a follow up to this this question about weakly universal hash functions
A family of hash functions $H_w$ is said to be weakly universal if for all $x \ne y$ :
$$P_{h \in H_w}(h(x) = h(y)) \...
3
votes
1answer
351 views
What is an example of a weakly universal hash function that is not pairwise independent?
A family of hash functions $H_w$ is said to be weakly universal if for all $x \ne y$ :
$$P_{h \in H_w}(h(x) = h(y)) \leq 1/m$$
Here the function $h:U \rightarrow [m]$ is chosen uniformly from the ...
1
vote
0answers
44 views
How to generate a random number in a given range with uniform probability [closed]
I have used programming languages which generate a random number in a given range.
Let's say we have a range of 1 to 10 each number has the probability of 1/10 to get selected. What is the criteria ...
1
vote
0answers
32 views
Probability lower bound on a double cycle on two vertices in random cuckoo graph
I have read Chater 17. Balanced Allocations and
Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got ...
3
votes
0answers
57 views
Probability of a double cycle in cuckoo graph
I have read Chater 17. Balanced Allocations and
Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got ...
2
votes
1answer
72 views
Why 2 different edge min-cuts in an undirected multigraph must be completely disjoint?
For the proof of a maximum of (n 2) min-cuts in any n-vertex undirected multigraph using the random contraction algorithm, we need to know that no min-cut shares an edge with another different one.
...
2
votes
1answer
39 views
HyperLogLog leading zeros distribution
I'm reading this article.
In particular I'm having some trouble trying to replicate the results of the first image in that article.
For x=9, the graph says that the probability is 0.20 aprox. But ...
4
votes
0answers
73 views
Distribution of pointer keys in a Skip-list node
Suppose we have a list of $N$ keys where the distribution of keys follows $f(x)$.
We construct a skip list over the keys.
Now if I pick a key (e.g. 31 in the ...
1
vote
1answer
62 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 ...
2
votes
1answer
51 views
Monte Carlo Algorithms : Are there any problems where two opposite Monte Carlo algorithms could solve it?
I started reading on Probabilistic algorithms and Monte-Carlo algorithms. Since a Monte-Carlo can only give a certain answer for either True or False, I was wondering if it's conceivable that for the ...
1
vote
2answers
181 views
Randomly Choosing a N-Bit Prime
I've been studying some number theory, and I came across this problem:
Lagrange’s prime number theorem states that as N increases, the number of primes less than $N$ is $Θ(N/ log(N))$.
...
2
votes
0answers
67 views
Insertion in 123 skip list
I had a problem in my exam dealing with 1-2-3 skip lists.
I have a problem with the insertion process in a 1-2-3 skip list. What I understand is that if the minimum of heights of 2 nodes in a 123 ...
1
vote
0answers
22 views
Extracting room voids in a house
I am looking to create a series of closed volumes that represent the empty voids made by rooms in a house.
In order to do this, all I have is the raw geometry of all the elements that encapsulate ...
1
vote
0answers
56 views
Finding subset of integer summing up above threshold
Given an array $|A|=n$ of integers, and $m,k \in \mathbb{N}$, I want to find $m$ elements $a_{i_1},...,a_{i_m}$ of $A$ such that $\sum a_{ij} \geq k$ (repitions allowd), or determine that no such ...
1
vote
0answers
34 views
Probabilistic linebreaking algorithm
I'm currently trying to implement this paper. Based on a bayesian network, the paper stays unclear about how to ultimately use it's content ("straightforward inference"). But after a lot of ...
7
votes
1answer
193 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 ...
4
votes
2answers
91 views
Fast sampling from discrete space
Assume we are given a set $X = \{x_1,...,x_n \}$ of size $n$, and a probability distribution $P$ over $X$. I am interested in an algorithm $A$ which can sample from $X$ according to $P$, i.e. $\Pr(A=...
2
votes
1answer
257 views
SAT Solving + Turing Machines
I have a couple of questions based on how SAT solvers work. I understand that SAT solvers may employ any/all of the following techniques:
Randomness
Heuristics
Backtracking
SAT is just one example ...
1
vote
0answers
73 views
distinguishing two biased coins
I had a simple probability question: suppose we have two coins, coin 1 is heads with probability $= 10\epsilon$ and coin 2 is heads with probability $=\epsilon/10$. Given an unknown coin, how many ...
4
votes
1answer
134 views
Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?
Context, I have a geometric algorithm that is sensitive to collinear points and receives as input a list of points in 2D generated randomly. Suppose that I have a Boolean function nonCollinear(x,y,z) ...
