Questions tagged [probabilistic-algorithms]
Questions about (typically randomized) algorithms that can produce no or an incorrect answer with a certain probability.
183
questions
1
vote
1answer
24 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 ...
2
votes
1answer
34 views
Given only the expected runtime of an algorithm, what can Markov's inequality tell us about its worst-case runtime?
The following is exercise 3.8 from the first edition of Mitzenmacher and Upfal's Probability and Computing: Randomized Algorithms and Probabilistic Analysis.
Suppose that we have an algorithm that ...
2
votes
2answers
111 views
Question about "with high probability"
An event that occurs with high probability is one whose probability depends on a certain number $n$ and goes to $1$ as $n$ goes to infinity, i.e. it can be made as close as desired to $1$ by making $n$...
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$-...
2
votes
2answers
35 views
Approximate duplicate sampling from a stream
The following question (in two parts) comes from a homework sheet of the fall 2019 semester cs170 course taught at UC Berkely taught by professors Vazerani and Tal.
Design an algorithm that takes in ...
1
vote
0answers
32 views
Computing a threshold function
Let $f$ be any function from $\{0, 1\}^{n}$ to $\{-1, 1\}$. For a given $f$, let us define another function $g_f$ as
\begin{equation}
g_f(x) = \sum_{x \in \{0, 1\}^{n}} f(x).
\end{equation}
Let us be ...
6
votes
0answers
228 views
From coin flips to algebraic functions via pushdown automata
Background
Given a coin with an unknown probability of heads of $\lambda$, sample the probability $f(\lambda)$. This is the Bernoulli factory problem, and it can be solved only for certain functions $...
1
vote
1answer
36 views
Obtaining an expectation in uniform hashing
long shot question but I am super stuck.
Donald Knuth has proven (p. 8 here, equation 12) that the probability that the maximum value in uniform hashing is smaller than $n/2$ is equal to 0.288. I ...
1
vote
1answer
23 views
Property testing of a complete multipartite graph
Propose and prove an $\epsilon$-test for the following property in the dense graph model: $G=(V,E)$ is a complete multipartite graph. That is, there exists a partition $V=V_1\cup\ldots\cup V_\ell$ ...
0
votes
1answer
30 views
Dynamic programming and probability - list of problems
Does anyone have a list of problems where you have to combine dynamic programming with probability?
0
votes
1answer
18 views
How to sample Bivariate Normal Distribution with Accept reject method
I have to write python code in jupyter due to sampling bivariate normal distribution with 3 sampling methods:
Prior Sampling
Gibbs Sampling
Rejection Sampling
I have done the first two samplings and ...
3
votes
0answers
61 views
Noisy sorter: optimal algorithm
Given $n$ elements $x_1,\dots, x_n$, and algorithm $A$ which outputs $(r_1,\dots, r_n)=A(x_1,\dots, x_n)$, we say $A$ is $\epsilon$-sorting the list if $rank(x_i) \in (r_i-n\epsilon, r_i+ n\epsilon) $ ...
0
votes
1answer
27 views
Match unpaired points between two sets
I have two sets, let's call them C and T, of unpaired points, which could for example represent two types of cells. Hence, both points are drawn from the same underlying distribution, but the points ...
0
votes
0answers
17 views
Predictive score ? how?
let say I have a sequence of values ...
The values X and Y can be either number or data structures or states ... and so on ...
Example:
Value X can be followed by any of "n" other values Y1,...
2
votes
2answers
55 views
Probabilistic adaptive algorithm that can explore only $k$ bits of input can’t distinguish $k$-independent distribution from uniform
Definition: Distribution $D$ on $\{0,1\}^n$ is called $k$-independent if for every random variable $X$ with distribution $D$ and for all $i_1, \dots, i_k \in \{1,2,\dots,n\}$ random variable $X_{i_1,\...
4
votes
2answers
67 views
Why is tabulated hashing 3-wise independent but not 4-wise independent?
Tabulated hashing uses tables of random numbers to compute hash values.
Suppose $|\mathcal{U}| = 2^w \times 2^w$ and $m = 2^l$, so that the items being hashed are pairs $(x,y)$ where $x$ and $y$ are $...
2
votes
1answer
47 views
Is there a concept of probabilistic quantum computers?
Answering my question Yonatan N said a statement from which follows that there are computable functions of quantum time complexity strictly above polynomial.
Accordingly a Quora answer
Quantum ...
0
votes
1answer
34 views
How to simulate online matching algorithms (implementation)
I was reading about online algorithms and bipartite matching.
I found an implementation that works fine on several websites (like geeksforgeeks).
For the online version, I found this paper
https://...
0
votes
0answers
33 views
Techniques to prove lower bounds on randomized algorithms
I am interested in proving lower bounds for AM-like languages. The usual techniques for lower bounds in non-probabilistic machines don't work for probabilistic machines.
Intuitively, when I think ...
1
vote
0answers
62 views
kth smallest element using Randomized select
I have recently started studying Randomized algorithms on my own. I am refering to Rajiv motwani - randomized algorithms book.
Objective - find kth smallest element using radomized select in $O(n^\...
2
votes
1answer
30 views
Find dominated or subsumed linear inequalities efficiently
Problem statement
Given a set of $N$ linear inequalities of the form $a_1x_1 + a_2x_2 + ... + a_Mx_M \geq RHS$, where $a_i$ and $RHS$ are integers. The inequality $A$ dominates or subsumes inequality $...
0
votes
1answer
38 views
How to implement conditional probability distribution on set-valued Random Variables
I'm trying to implement conditional probability distribution when the events of two RVs are sets. If I try to extrapolate concepts from real or categorical variables to sets things become confusing ...
1
vote
1answer
59 views
Calculating a jackpot winner based on probabilities
Imagine a jackpot where users can bet as much as they want, and each bet increases their winning chance. Given a roll [0-100], how would you calculate the winner?
...
0
votes
1answer
52 views
Probability of loss using a binary symmetric channel
Today we talked about Information Theory and the binary symetric channel.
For newbies here is a little explanation :
For instance if I want to send a binary to someone :
The bit will be "flipped&...
1
vote
1answer
14 views
Populating a vector of numbers to expose an error in a function implementation
So lets say I'm writing an algorithm that takes a vector as input. I want to know that I'm writing this algorithm correctly however so I of course write tests to see if the output equals what I expect ...
1
vote
0answers
27 views
Distributional error probability of deterministic algorithm implies error probability of randomized algorithm?
Consider some problem $P$ and let's assume we sample the problem instance u.a.r. from some set $I$.
Let $p$ be a lower bound on the distributional error of a deterministic algorithm on $I$, i.e., ...
0
votes
1answer
32 views
Hash function, $h(k) = \lfloor km \rfloor$ is simple uniform for real $k$ independently, uniformly distributed in the range $0 \leq k < 1$
I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following statement:
If the keys are known to be random real numbers $k$ independently and uniformly ...
2
votes
1answer
48 views
Confusion about the Hiring Problem
I'm confused about where the probability from the hiring problem comes from.
For background:
We interview one person everyday who has a quality characteristic, x, from 0 to 1(distributed uniformly). ...
1
vote
1answer
34 views
Why Convolutional codes is easy to factor/handle the uncertainty of a bit being a 0 or a 1 into the decoding?
Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 208:
My question is about this part.
[Convolutional codes have been popular in ...
2
votes
1answer
159 views
What is an example of a Monte-Carlo algorithm for finding a Hamiltonian path?
I've recently been made aware that there exist Monte-Carlo algorithm(s?) for determining whether a Hamiltonian path exists in a graph. I am struggling to figure out how it would work. What is the ...
0
votes
0answers
45 views
Hashing algorithm which minimizes distribution
Consider applications A1, A2 .. AN having properties P11, P12,... PN1, PN2.. Also consider buckets ...
3
votes
1answer
61 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
110 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
62 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
27 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
69 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
32 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
25 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
74 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
21 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
322 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
615 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
108 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
22 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 ...
5
votes
1answer
77 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
17 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
219 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
52 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
38 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
173 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. ...
