Questions tagged [probabilistic-algorithms]
Questions about (typically randomized) algorithms that can produce no or an incorrect answer with a certain probability.
226 questions
0
votes
1
answer
60
views
Bounded probabilistic log-space which halts with probability $1$
It is known that BPL $\subseteq$ P where BPL is the class of languages that have a probabilistic Turing machine which decides input correctly with probability $\ge \frac{2}{3}$ and always halts ...
- 3,413
1
vote
1
answer
80
views
Randomised Algorithm for Maximum Matching
Consider the following randomised distributed algorithm for computing (constant-approximation) maximum matching. The algorithm
has $\log ∆$ iterations indexed by $i∈{0,1,2,\ldots,\log ∆−
1}$. We ...
- 21
0
votes
0
answers
76
views
What is the expected number of layers in a skip list?
Skip lists work in layers. My question is no more than that: What is the expected number of layers in a skip list with the parameter $p \in (0,1)$? My best attempt to so far is
$$\sum_{i = 1}^\infty i ...
- 60
1
vote
0
answers
58
views
Why is this probability $o(1)$ as $m \to \infty$ in a proof of a randomized algorithm for solving $k$-CNF ($k$-SAT) ? A mistake in a famous book?
This is about the proof of Lemma 5.13 in the well-renowned book Motwani R, Raghavan P. Randomized Algorithms. Cambridge University Press; 1995. Access with institutional login: link.
(The lemma is in ...
- 11
5
votes
1
answer
217
views
Basic question about parallel repetition in IP protocol
The book Arora and Barak defines class IP (interactive protocol) by making the verifier have private coins. Before proceeding to public coin proofs and showing they are the "same," the book ...
- 3,413
0
votes
0
answers
36
views
Communication complexity in Linear PCP
I wonder how should I state the communication complexity when having a linear PCP combined with another protocol?
May I ask that if I have a protocol that utilizes a linear PCP that has proof length n,...
- 101
0
votes
0
answers
34
views
Why does HyperLogLog use P(at least max zeroes) instead of P(exactly max zeroes)?
In HyperLogLog, we estimate cardinality using the Harmonic Mean of the maximum number of leading zeroes observed across hashed values. The final estimate is derived using P(at least max_zeroes) rather ...
- 1
1
vote
3
answers
213
views
Comparison of Two Algorithms for Finding a Position of 1 in an Array with Equal Zeros and Ones
Given an array 𝑎[1..𝑛] containing half zeros and half ones, we need to find a position in 𝑎 that contains the value 1. Consider the following two algorithms:
Algorithm 1
...
- 11
0
votes
0
answers
75
views
Question Related to Probabilistic Turing Machine
Q) Assume that the success probability of a probabilistic algorithm $M$. In other words, a
probabilistic Turing machine, satisfies $p_{succ} \geq \frac{1}{p(n)}$, for some polynomial $p(n)= O(n^c)$ ...
3
votes
1
answer
134
views
Two-Level (Perfect) Hash Tables in Practice
For $n$ elements, a two-level hash table contains an $O(n)$ top-level hash table whose entries are hash tables also. Each table samples from a 2-universal family. To hash an element $x$, we first hash ...
- 31
4
votes
0
answers
85
views
Approximation algorithm to estimate diameter of points in metric space
Given an arbitrary metric space $M=(X,d)$, is there a $(1+\epsilon)$-approximate algorithm (maybe probabilistic or randomized) that can estimate the diameter of $X$? This algorithm should be faster ...
- 141
1
vote
0
answers
36
views
Distribute and merge HeavyKeeper
I'd like to disribute the HeavyKeeper algorithm. So far I couldn't find resources on how to merge two HeavyKeeper data structures. Is this even possible without scraficing accuracy?
- 111
0
votes
1
answer
54
views
Choosing random sample of requests from stream
Suppose that I would like to divert 10% of requests coming into an API to some other service. The request needs to be sent to the service at the time the request is processed. The requests should be ...
- 131
2
votes
0
answers
50
views
Picking from a categorical distribution such that the selection is stable
Let's say I have a random variable $V$ which takes values from the finite set $V = \{v_1, v_2,...,v_N \}$. I want to pick one value randomly based on given probabilities $p_i = \Pr(V=v_i)$. Let's call ...
- 121
3
votes
1
answer
166
views
Complexity class BPP, but with only expected polynomial running time
The complexity class BPP requires that the running time be guaranteed polynomial, though with only a 2/3 chance of the correct output.
ZPP, on the other hand, guarantees correct output, but now only ...
- 1,081
2
votes
0
answers
98
views
Approximate Set Intersection datastructure
I'm working on a project involving set-like data structures. For one of the algorithms I am using that does a merge-like operation on two of these structures I can take a very big shortcut if I know ...
- 21
1
vote
0
answers
44
views
Information on sample pooling strategies
I am looking for information about a specific sort of problem: There is a set of samples, and some subset of them are positive. It is possible to combine samples and test if the combination contains ...
- 183
4
votes
0
answers
83
views
Generate random points such that no 4 lie on a circle
In $\tilde{O}(n)$ time, can I generate $n$ random lattice points so that no four lie on the same circle? You can assume we pick points from a grid of side length $k \gg n$ (say, take $k=n^2$).
I have ...
0
votes
1
answer
58
views
Understanding the last algebra step of this proof
Could someone help me understand why in the below proof, if $k > log_{2}n$, then $P(N_i=1)< \frac{1}{n}$?
0
votes
1
answer
64
views
What is the largest "allowed" seed for a PRNG to not give any extra power to a deterministic machine?
Suppose a polynomial time machine that has an access to a polynomially long string of bits independent on the input. On average, it's impossible to compress this string to a subpolynomially long ...
- 2,151
2
votes
0
answers
51
views
Windowed LogLog/HyperLogLog algorithm to get a count of the cardinality of the set of the last $k$ elements?
LogLog/HyperLogLog provides a great way for estimating the cardinality of the set of $n$ objects. At its simplest, you hash all $n$ objects into binary strings, find the largest number of leading 0's $...
- 652
2
votes
1
answer
140
views
How many random bits does this algorithm use on average?
Here, flip() is a function that returns 0 or 1 with equal probability. It can be proved ...
- 367
0
votes
1
answer
234
views
Finding the error probability of a Monte Carlo algorithm
Let's say I have a Monte Carlo algorithm $A$ that gives the correct answer with a probability $p$ > $1/2$. I don't have any information on if it's decisional or not.
I understand that I can make ...
0
votes
0
answers
63
views
Probabilistic Pathfinding
Here an interesting graph problem I've recently saw:
After a heist in New York City, a group must reach Miami within a set timeframe to catch an escape boat. Their vehicle's GPS shows U.S. routes with ...
- 1
1
vote
1
answer
110
views
Number of non-zero elements in intersection of two bloom filters
Let us assume I use bloom filters of size $m$ bits with $k$ hash functions.
Now I have two set $X$ and $Y$. Let $B(X)$ be bloom filter of the set $X$. In general I know that $B(X\cup Y)= B(X) \lor B(Y)...
- 113
1
vote
0
answers
76
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 ...
- 247
3
votes
1
answer
196
views
Algorithm to select a random bit string with constraints
Problem Description
Given $a, b, n \in \mathbb{N}$ with $a < b < n$.
Let $M$ be the set of all possible bit strings of length $n$ which begin and end with one and have at least $a$ and at most $...
- 63
1
vote
2
answers
73
views
Probabilty of Elements being smaller than a specific value
Right now i am looking at the following statement, but i cant grasp why it is correct.
Can somebody help?
"If we look at F0 uniformly distributed (and, say, pairwise independent) elements of
[0, ...
- 13
1
vote
0
answers
88
views
Combine Las Vegas and Montecarlo probabilistic algorithms to improve chance of finding correct answer
Let's say that I have a Las Vegas algorithm for a given problem (whose answer is true/false for simplicity) with a chance of ...
- 239
4
votes
0
answers
42
views
Error correcting codes for transmitting a real value $x$ in [0,1], minimizing the reconstructed distance to the original $x$
I have been thinking a bit about error correcting codes, in particular the following problem:
Consider the problem of transmitting a single real number $x \in [0,1]$ over a lossy connection, where ...
- 41
2
votes
1
answer
125
views
Probability of this random selection
Suppose we have an array of $n$ integers. Suppose that we pick one of these elements uniformly at random and call it $x$. Suppose that $\log n$ elements are also sampled (uniformly at random) from the ...
- 195
10
votes
4
answers
2k
views
Probabilistic methods for undecidable problem
An undecidable problem is a decision problem proven to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. I wonder if there are examples of probabilistic ...
- 241
0
votes
1
answer
845
views
Time complexity analysis for Searching in a Hash table
I want to analyse the time complexity for Unsuccesful search using probabilistic method in a Hash table where collisions are resolved by chaining through a doubly linked list. And the doubly linked ...
- 105
1
vote
0
answers
58
views
Probability that an Algorithm Deviates from Its Behaviour after Multiple Rewindings
I do have a seemingly fundamental question that I somehow struggle to intuitively make sense of.
Setting:
Let us consider a randomized algorithm $R$ that has $t$ steps. In each step, it is fed with ...
- 11
0
votes
1
answer
79
views
Algorithm for allocating resources; one resource per one user who accepts it
I am looking for an algorithm for the following problem:
I have a set of users and a set of books.
Every user has their own set of favorite books, which may be empty, and is a subset the set of books.
...
- 113
1
vote
1
answer
102
views
Semi-bounded probabilistic polynomial-time, is it equal to BPP?
The complexity class $\mathsf{BPP}$ is typically defined as the class of all problems for which:
Running an algorithm once takes polynomial time at most.
The answer is correct with the probability at ...
- 2,151
0
votes
0
answers
63
views
Rank of random binary string with Bernoulli distribution
For $1\ge p_1 \ge \dots \ge p_n \ge 0$, and for $i\in[n]$ draw $k$ iid binary strings with $m$ length:
$$X_{i,1},\dots,X_{i,k}\stackrel{iid}{\sim} \text{Bernoulli}(p_i)^m.$$
Viewing these binary ...
- 539
2
votes
1
answer
174
views
Lower bound for ϵ-tester with one-sided error for the "2-injective" property of functions
An $\epsilon$-tester given an input and a property, is defined as follows:
If the input holds the property then the tester should accept with probability at least $\frac 2 3$. Otherwise if the input ...
- 123
1
vote
2
answers
164
views
Weighted sample of ~k elements from array in O(n) time?
I have an array $a$ with $n$ elements, all of which have an associated weight. For example:
$a = \{ (A,2), (B,5), (C,9), ..., (Z,1) \}$, such that element $A$ has weight $w_A=2$, element $B$ has ...
- 11
1
vote
0
answers
53
views
What are practical applications for markovs algorithm(string rewriting systems)
:)
Currently I am browsing through the internet on the hunt for a topic for my bachelors thesis. Whilst being on Reddit I discovered an interesting repo (https://github.com/mxgmn/MarkovJunior) for a ...
- 11
1
vote
0
answers
36
views
Usage cases of AMS algorithm
This question is about the second frequency algorithm described in N. Alon, T. Matias, and M. Szegedy The space complexity of approximating the frequency moments. Specifically, I am asking about the ...
- 125
1
vote
0
answers
53
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
3
votes
0
answers
143
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
2
votes
1
answer
287
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 ...
0
votes
1
answer
75
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
1
answer
82
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 ...
- 729
2
votes
1
answer
442
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 ...
- 373
2
votes
2
answers
456
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$...
- 623
1
vote
0
answers
36
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$-...
- 11
2
votes
2
answers
452
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