# Questions tagged [probabilistic-algorithms]

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

204 questions
Filter by
Sorted by
Tagged with
45 views

### PP and the most significant bit of functions in #P

I've found the following sentence (and some variants) in a lot of places, namely in Arora and Barak's Computational Complexity: A Modern Approach. Intuitively, PP corresponds to computing the most ...
• 391
1 vote
30 views

### How can $R_HL$ differ from $RL$?

https://complexityzoo.net/Complexity_Zoo:R RL: Randomized Logarithmic-Space Has the same relation to L as RP does to P. The randomized machine must halt with probability 1 on any input. It must also ...
• 239
71 views

• 221
1 vote
25 views

### RP with very small error = P

I was asked to show the equality $RP(1 − 2^{-2^{n}}) = P$, which seems wrong to me (?). The $\supseteq$ direction is obvious, and I want to show the other direction. My first intuition was to run ...
• 161
122 views

### Verify if array is orthogonal

Orthogonal arrays often appear in probabilistic algorithms. They can be efficiently constructed from, e.g., BCH codes. But is there an efficient algorithm that can verify if an array is orthogonal? I ...
• 125
1 vote
74 views

### Does the reliability of polynomial hashing depend on whether the modulus is prime, for coprime base and modulus?

A polynomial hash of a string $s$ with base $b$ and modulus $M$ is defined as $$H(s) = (s_0 + s_1 b + s_2 b^2 + \dots + s_{n-1} b^{n-1}) \mod M.$$ I have proven (and this is quite obvious) that ...
• 11
42 views

### Are turing machines & equivalents with infinite sized random programs still turing machines?

Are turing machines with an infinite program tape that is completely random, or another example is a Game of Life simulation on an infinite randomly initialized grid, still turing machines, so to ...
1 vote
31 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 ...
• 699
215 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 ...
• 303
220 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$...
• 595
1 vote
19 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$-...
128 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 ...
• 123
1 vote
35 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 ...
• 219
1 vote
59 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 ...
• 183
1 vote
32 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$ ...
78 views

### Dynamic programming and probability - list of problems

Does anyone have a list of problems where you have to combine dynamic programming with probability?
• 181
252 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 ...
67 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)$ ...
30 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 ...
• 133
58 views

• 141
74 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 ...
• 413
62 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://...
109 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 ...
• 11.4k
1 vote
345 views

• 232
52 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
141 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? ...
• 111
134 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
22 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 ...
• 3,758
1 vote
32 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., ...
120 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 ...
• 1,042