Questions tagged [probabilistic-algorithms]
Questions about (typically randomized) algorithms that can produce no or an incorrect answer with a certain probability.
193
questions
1
vote
1
answer
59
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 ...
- 21
1
vote
0
answers
122
views
Non-adaptive ϵ-tester to check existence of a "ring"
A non-adaptive tester is a tester which queries are selected and defined without assuming anything in the input. In other words, for every input given - the tester performs the exact same queries.
An $...
- 21
1
vote
1
answer
35
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
22
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
14
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
0
votes
0
answers
15
views
Frequency moments
I have a question about the second algorithm of N. Alon, T. Matias, and M. Szegedy. The space complexity of approximating the frequency moments that specifically concerns computations of the second ...
- 125
0
votes
0
answers
17
views
Learner Algorithm Time & Sample Complexity
Let $X=R^{2}$. Let $u=\left(\frac{\sqrt{3}}{2},-\frac{1}{2}\right),\
w=\left(-\frac{\sqrt{3}}{2},-\frac{1}{2}\right),\ v=\left(0,1\right)$
and $C=H=\left\{h\left(r\right)=\left\{\left(x_{1},x_{2\ }\...
- 221
1
vote
0
answers
24
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
116
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
1
answer
58
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
0
votes
1
answer
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 ...
- 11
0
votes
0
answers
51
views
Find minimum cost cycle in graph G=(V,E) that visits vertices in required subset V′⊂V exactly once & covers edges in required subset E′⊂E atleast once
I have been researching about general routing problems and came across a problem similar to the Travelling Salesman Problem:
Find a minimum cost cycle in a graph $G = (V, E)$ which visits vertices in ...
- 101
1
vote
1
answer
27
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 ...
- 659
2
votes
1
answer
149
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
2
votes
2
answers
159
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$...
- 503
1
vote
0
answers
16
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
83
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 ...
- 23
1
vote
0
answers
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 ...
- 309
1
vote
1
answer
51
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 ...
- 171
1
vote
1
answer
28
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$ ...
- 13
0
votes
1
answer
48
views
Dynamic programming and probability - list of problems
Does anyone have a list of problems where you have to combine dynamic programming with probability?
- 171
0
votes
1
answer
85
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 ...
- 128
3
votes
0
answers
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) $ ...
- 521
0
votes
1
answer
27
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
2
votes
2
answers
58
views
Probabilistic adaptive algorithm that can explore only $k$ bits of input can’t distinguish $k$-independent distribution from uniform
Definition: Distribution $D$ on $\{0,1\}^n$ is called $k$-independent if for every random variable $X$ with distribution $D$ and for all $i_1, \dots, i_k \in \{1,2,\dots,n\}$ random variable $X_{i_1,\...
- 65
4
votes
2
answers
113
views
Why is tabulated hashing 3-wise independent but not 4-wise independent?
Tabulated hashing uses tables of random numbers to compute hash values.
Suppose $|\mathcal{U}| = 2^w \times 2^w$ and $m = 2^l$, so that the items being hashed are pairs $(x,y)$ where $x$ and $y$ are $...
- 141
3
votes
1
answer
65
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
0
votes
1
answer
43
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://...
0
votes
0
answers
59
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 ...
- 10.8k
1
vote
0
answers
192
views
kth smallest element using Randomized select
I have recently started studying Randomized algorithms on my own. I am refering to Rajiv motwani - randomized algorithms book.
Objective - find kth smallest element using radomized select in $O(n^\...
2
votes
1
answer
33
views
Find dominated or subsumed linear inequalities efficiently
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 $...
- 232
0
votes
1
answer
47
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
1
vote
1
answer
89
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
0
votes
1
answer
108
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
1
answer
20
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,728
1
vote
0
answers
30
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., ...
0
votes
1
answer
65
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,034
2
votes
1
answer
71
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). ...
1
vote
1
answer
40
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 ...
2
votes
1
answer
216
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 ...
- 143
0
votes
0
answers
51
views
Hashing algorithm which minimizes distribution
Consider applications A1, A2 .. AN having properties P11, P12,... PN1, PN2.. Also consider buckets ...
- 101
3
votes
1
answer
66
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 ...
- 141
2
votes
1
answer
125
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 ...
- 127
3
votes
1
answer
89
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 ...
- 954
2
votes
1
answer
31
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 ...
- 53
2
votes
1
answer
96
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 ...
- 79
2
votes
1
answer
33
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 ...
- 79
0
votes
0
answers
31
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 ?
- 17
0
votes
0
answers
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 ...
- 17
0
votes
0
answers
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 ...
- 17