Questions tagged [probabilistic-algorithms]
Questions about (typically randomized) algorithms that can produce no or an incorrect answer with a certain probability.
202
questions
1
vote
1
answer
199
views
Uniform sampling with constraints
Suppose one wants to uniformly sample a string $w$ of a given length over a finite alphabet, such $w$ satisfies a set of structural constraints (such as - "the third character has to be equal to the ...
- 13
2
votes
1
answer
26
views
Random award question
I'm assisting with the design of an algorithm over the next week to fit the following use case:
A person walking in a store has a tablet and approaches possible customers to notify them of a ...
- 123
0
votes
0
answers
13
views
Characterization of P in the context of probabilistically checkable proofs [duplicate]
The PCP theorem characterizes NP as the class of problems checkable probabilistically using log(n) bits and a constant number of random bits and yields $NP=PCP(O(log(n)),O(1))$ .
Is there a pair $(f,...
4
votes
2
answers
3k
views
Average Case Analysis for finding max and min value on an array
Given the following algorithm, to find the maximum and minimum values of an array - don't mind the language:
...
- 155
1
vote
1
answer
601
views
Does every language in BPP have a mapping reduction to ATM?
Does every language $C$ in the class $BPP$ have a mapping reduction to $A_{TM}$?
$(C\leq _{m} A_{TM})$
$BPP$ is the class of languages that have a probabilistic $TM$ that accepts them with an error $\...
- 335
1
vote
1
answer
75
views
Probability that a leaf with 1 will be selected in game tree evaluation
I am trying to understand randomized AND-OR Game Tree Evaluation. I am stuck with proving the most basic case, namely, an OR node with two leaves (AND node with two leaves is similar).
...
- 534
0
votes
1
answer
88
views
Expected number of nodes in the independent set produced by a coloring algorithm on a graph with maximal degree $k$
We have a graph with $n$ nodes and maximal degree $k$. On this graph we run a coloring algorithm that finds a maximum independent set. The algorithm colors every node green with probability $\frac{1}{...
- 209
1
vote
0
answers
91
views
How to select cuckoo filter parameters?
If I want a cuckoo filter to hold a dataset with N entries with a target false positive rate of ϵ, how do I select the sizes for the table, bucket, and fingerprint parameters?
- 169
2
votes
1
answer
105
views
Is there some mathematical properties of the distribution which is the output of a probabilistic polynomial-time Turing machine?
Let $S_{n}$ be an input set whose elements are length $n$, namely $S_{n} = \Sigma^{n}$. For every probabilistic polynomial-time algorithm $A$ and any $u \in \Sigma^{*}$, there exists a function $f^{A}$...
- 613
1
vote
1
answer
175
views
Are probabilisitc algorithms deterministic?
I got confused with deterministic and probabilistic algorithms. Am I right by assuming that algorithms are called probabilistic once they use some sort of randomness?
Initially, I thought only ...
- 111
1
vote
1
answer
63
views
If the difference between two oracles is negligible, is the difference between a PPT algorithm with these two oracles also negligible?
We say a negligible function is a function $\epsilon(n):\mathbb{N}\rightarrow \mathbb{R}$ such that for every positive integer $c$ there exists an integer $N_c$ such that for all $n > N_c$,
$$\...
- 613
3
votes
1
answer
717
views
Algorithm for finding cliques
Given an arbitrary undirected graph $G = (V,E)$, I am interested in a low-polynomial time algorithm which can find several moderately large (ideally $O(n^\epsilon)$ vertices per clique for $\epsilon &...
- 215
2
votes
2
answers
125
views
Cuckoo filters for non powers-of-2
The Cuckoo filters paper (https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf) claims a 95% load factor, however it seems to make an implicit assumption that the table size is a power of 2, and ...
2
votes
1
answer
199
views
Confuse on using bucket number to replace hashing multiple times in hyperloglog explanation
In this blog the author states that the following
So we now have a rather poor estimate of the number of values in the
dataset based on bit patterns. How can we improve on it? One
...
- 151
2
votes
1
answer
255
views
Proving $P=BPP$ under a assumption
Let suppose that there exists deterministic polynomial algorithm $A$ that approximates the probability that a given boolean circuit $C$ accepts random input with an error at most $\frac{2}{5}$. More ...
- 319
-1
votes
1
answer
282
views
Graph isomorphism in BPP implies it is also in RP
$$L=\{\langle G\rangle \#\langle H\rangle : H, G \text{ are directed isomorphic graphs }\}$$
$\langle G\rangle$ is adjacency matrix written row by row.
Show that if $L\in BPP$ then also $L\in RP$.
Can ...
- 379
0
votes
0
answers
54
views
Show that if language belongs to $BPP$ then also similar language belgons to $QP$
Prove that for each arbitrary set of natural numbers $A$ we have:
$$\{bin(n) | n\in A\} \in BPP \to \{0^n|n\in A\}\in QP$$ where $bin
(n)$ is binary representation of $n$ $$QP = \bigcup_{c\in \...
- 379
1
vote
0
answers
44
views
What's the polynomial involved in the PCP theorem?
Statements of the PCP theorem always speak of a proof of length $poly(n)$. But what polynomial is that exactly? Could you actually construct the PCP for some mathematical fact in real life?
- 1,048
3
votes
1
answer
738
views
proving $IP^\star = NP$
Consider the following complexity class $IP^\star$, a variant of $IP$.
A language $L$ is in $IP^\star$ if there's a proof system $(P,V)$ s.t.
$V$ is a verifier runs for a polynomial time and:
...
- 555
0
votes
0
answers
53
views
find a values of a array members
We have
Some big hashed array of data with boolean values, we know keys, but don't know values.
Oracle who have input of array of keys and can tell how much of them are ...
- 109
1
vote
1
answer
210
views
What does it mean for a problem to be solved in polynomial time "relative to" an oracle?
I came across the following theorem in page 12 of the following pdf :
There exists an oracle relative to which there is a problem solvable
in polynomial time (with bounded error probability) on a ...
- 488
1
vote
1
answer
162
views
Examples of difference between Hidden Markov Model and Bayesian Network?
I am trying to more deeply understand the difference between Hidden Markov Models and Bayesian Network? The general idea is that HMMs have a single variable which has probabilities of entering ...
- 668
1
vote
1
answer
273
views
Is $A_{PTM}$ a BPP-complete language?
The language $A_{PTM}$ is defined as the acceptance problem on a Probabilistic Turing machine.
$A_{PTM}=$ { $<M, x> | M$ on input $x$ accepts with an error probability less than or equal to 1/...
- 365
2
votes
0
answers
102
views
Stochastic Computing: What is "Bundle Processing"?
I'm puzzled by a short paragraph found in the article on Stochastic Processing in Wikipedia. There it says:
Bundle Processing involves sending a fixed number of bits instead of a stream. One of the ...
- 141
1
vote
1
answer
200
views
Does a computation tree for a probabilistic Turing machine have to be a binary tree?
Ever example of computation on a probabilistic Turing machine that I have read uses only a binary tree to show the computational branches of a probabilistic Turing machine. I know that an NTM may use ...
- 365
1
vote
1
answer
217
views
Using amplification lemma to decrease error probability gives 0 as divisor
I am attempting to work through an example of how to select an error bound, and then determine the number of simulations necessary by the amplification lemma to obtain the desired error bound. I have ...
- 365
3
votes
1
answer
78
views
Hidden Markov Model initial probability reestimate: Why $\pi^*_i = \gamma_i(1)$ instead of $\pi^*_i = \frac{\gamma_i(1)}{\sum_{j = 1}^N \gamma_j(1)}$
In the sources I consulted it states that in the Baum Welch algorithm the reestimate of the initial probability of state $i$ of the HMM is $\pi^*_i = \gamma_i(1)$. But $\gamma_i(t)$ is the probability ...
- 295
2
votes
2
answers
164
views
Markov chain probability in a complete graph
I'm having a hard time understanding the following. Assuming we have a complete graph with $n$ vertices, where initially, one of those has an information. At this point, all we care about is that in ...
- 43
2
votes
1
answer
323
views
Probabilistic Substring Match
I'm looking for an algorithm that will help me determine substring matches at scale.
I have a pool of 100+ million "needles" (strings). I can do as much pre-processing on them as I want, and storage ...
- 123
1
vote
1
answer
48
views
"Learning occupancy grid maps with forward sensor models, S.Thurn,2008" a formula that is difficult to overcome
I am reviewing the document" Learning occupancy grid maps with forward sensor models, S.Thrun, 2008" (http://faculty.iiit.ac.in/~mkrishna/ThrunOccGrid.pdf)
i am really confused about formula (26), ...
- 13
2
votes
0
answers
66
views
Box labelling game
I have a box of stickers. It contains $n$ stickers. Each sticker is labelled with a different number from $\mathbb{Z}$.
I have infinite supply of boxes.
Box labelling game: I pick a random sticker ...
- 1,731
3
votes
2
answers
133
views
Doesn't a quantum algorithm being deterministic contradict the superposition principle?
How can the EQP quantum complexity class exist? I mean, doesn't the superposition principle imply it is not possible to know with probability 1 whether a quantum algorithm will return a solution?
For ...
- 93
1
vote
1
answer
65
views
Recognizing vs Deciding in defining class BPP
In Sipser's text, he writes:
When a probabilistic Turning machine recognizes a language, it must
accept all strings in the language and reject all strings not in the
language as usual, except ...
- 557
5
votes
1
answer
771
views
Analysis of a randomized algorithm for independent set construction
Suppose that $G = (V,E)$ is a 3-regular graph on $n$ vertices and $m$ edges. Below I propose a randomized algorithm for obtaining an independent set for $G$.
Step $1$: Delete each vertex (...
- 309
0
votes
1
answer
219
views
Prove that we can change probability in definition of PP class
According to Wikipedia, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. If the answer ...
- 11
4
votes
1
answer
761
views
Prove that PP is closed under complement
I found this proof in Wikipedia, but one of the most important steps in it doesn't make any sense to me. I'll explain:
By the definition of PP there is a polynomial-time probabilistic
algorithm ...
- 311
0
votes
0
answers
141
views
Algorithm to sort elements of an array under uncertainty
I have an array of $n$ elements. Each element is basically the mean of gamma distribution and the actual value of the element is picked from that distribution. Assume the parameters of distribution (...
- 111
2
votes
1
answer
288
views
Clock solitaire game and principle of deferred decision
I have been reading the randomized algorithm book by Rajeev Motwani and Prabhakar Raghavan. In section 3.5 they have introduced principle of deferred decision which is a different probability space. ...
- 115
1
vote
0
answers
181
views
Proving that $BPP^{BPP}=BPP$ [duplicate]
I'm trying to prove that $BPP^{BPP}=BPP$.
$BPP\subseteq BPP^{BPP}$ is obvious. I'm struggling with $BPP^{BPP}\subseteq BPP$..
Can anyone help?
- 39
4
votes
2
answers
467
views
Are there any useful deterministic quantum algorithms for decision problems?
The vast majority of known interesting quantum algorithms are probabilistic. The only deterministic quantum algorithms that I know of (which aren't trivially equivalent to a classical algorithm) are (...
- 984
4
votes
2
answers
514
views
Why does Karger's algorithm work "with high probability"
I'm reading Karger 1993's "Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm" (link).
It states that a single round of contractions yields a min-cut with probability $\...
- 141
2
votes
1
answer
90
views
Replacing n with 2n in asymptotic bounds
I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al.
In the proof of the theorem $6$ of the paper on page 632, the authors go on ...
- 326
6
votes
1
answer
6k
views
Why is ZPP = RP ∩ co-RP?
I am trying to prove the theorem that ZPP = RP $\; \cap \; co-RP$. If $L \in \; \subseteq RP \; \cap \; co-RP$ then I can see that it belongs to $ZPP$. But I am unable to prove the reverse direction, ...
- 2,923
2
votes
1
answer
156
views
A clarification on $PP$
Wiki in https://en.wikipedia.org/wiki/PP_(complexity) says "a PP algorithm is permitted to do something like the following:
On a YES instance, output YES with probability $1/2 + 1/2^n$, where n is ...
user39969
3
votes
1
answer
5k
views
How can we get a Las Vegas algorithm from a Monte Carlo one?
I am trying to solve some exercises on random algorithms from this book, randomized algorithms. This is not a homework. I am only trying to improve my skills.
Here is the exercise:
Exercise 1.3: ...
- 960
8
votes
1
answer
3k
views
What does the "principle of deferred decisions" formally mean
I have encountered the phrase "Principle of deferred decisions" in Mitzenmacher and Upfal's book on Randomized Algorithms and several other courses online. Isn't it just conditional probability? In my ...
- 243
2
votes
1
answer
185
views
Probability bounds on size of smaller partition in randomized quicksort
Let $0 < a < 0.5$ be some constant. We have an $n$-element array as input. Randomized quicksort chooses one element from array uniformly at random as a pivot and partitions. With probability $1-...
-1
votes
1
answer
159
views
Random quadtrees
I have $N$ uniformly distributed 2D points and I want to find out
how many points lie in some small rectangular region. However,
the number of points can be arbitrarily large (e.g., $N=10^8$),
so I ...
- 1
5
votes
1
answer
140
views
Logarithmic Randomness is Necessary for PCP Theorem
I am trying to proof the following statement:
If $ {\rm SAT} \in {\rm PCP}[r(n),O(1)]$, where $ r(n)=o(\log n)$, then ${\sf P}={\sf NP}$.
Here are my ideas for the proof:
It can be easily worked ...
- 177
3
votes
1
answer
659
views
What is the best you can do with a noisy message?
You play a TV game in which you have to open one door out of $n$. Behind each door, there is a treasure with probability 1/2, independent of the other doors, so your apriori chance of winning is 1/2.
...
- 5,844