# Questions tagged [probabilistic-algorithms]

Questions about (typically randomized) algorithms that can produce no or an incorrect answer with a certain probability.

183 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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$...
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$-...
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 ...
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 ...
228 views

67 views

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 $... 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 ... 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? ... 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&... 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 ... 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., ... 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 ... 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). ... 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 ... 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 ... 0answers 45 views ### Hashing algorithm which minimizes distribution Consider applications A1, A2 .. AN having properties P11, P12,... PN1, PN2.. Also consider buckets ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ? 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 -...
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. ...