# Questions tagged [probabilistic-algorithms]

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

202 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
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 ...
13 views

1 vote
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). ...
88 views

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 ...
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, ...
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 ... 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: ...