Questions tagged [probabilistic-algorithms]
Questions about (typically randomized) algorithms that can produce no or an incorrect answer with a certain probability.
0
votes
0answers
4 views
Small space hash functions that are weakly but not strongly universal
This is a follow up to this this question about weakly universal hash functions
A family of hash functions $H_w$ is said to be weakly universal if for all $x \ne y$ :
$$P_{h \in H_w}(h(x) = h(y)) \...
2
votes
1answer
224 views
What is an example of a weakly universal hash function that is not pairwise independent?
A family of hash functions $H_w$ is said to be weakly universal if for all $x \ne y$ :
$$P_{h \in H_w}(h(x) = h(y)) \leq 1/m$$
Here the function $h:U \rightarrow [m]$ is chosen uniformly from the ...
1
vote
0answers
31 views
How to generate a random number in a given range with uniform probability [closed]
I have used programming languages which generate a random number in a given range.
Let's say we have a range of 1 to 10 each number has the probability of 1/10 to get selected. What is the criteria ...
1
vote
0answers
24 views
Probability lower bound on a double cycle on two vertices in random cuckoo graph
I have read Chater 17. Balanced Allocations and
Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got ...
2
votes
0answers
39 views
Probability of a double cycle in cuckoo graph
I have read Chater 17. Balanced Allocations and
Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got ...
2
votes
1answer
36 views
Why 2 different edge min-cuts in an undirected multigraph must be completely disjoint?
For the proof of a maximum of (n 2) min-cuts in any n-vertex undirected multigraph using the random contraction algorithm, we need to know that no min-cut shares an edge with another different one.
...
2
votes
1answer
27 views
HyperLogLog leading zeros distribution
I'm reading this article.
In particular I'm having some trouble trying to replicate the results of the first image in that article.
For x=9, the graph says that the probability is 0.20 aprox. But ...
4
votes
0answers
49 views
Distribution of pointer keys in a Skip-list node
Suppose we have a list of $N$ keys where the distribution of keys follows $f(x)$.
We construct a skip list over the keys.
Now if I pick a key (e.g. 31 in the ...
1
vote
1answer
20 views
Concentration bound for sum of dependent geometric random variable?
consider following persudocode:
i=0
while(i< k):
uniformly pick u,v in V
if(uv in E):
remove uv form E;
i++;
let $T$ be the number of ...
1
vote
1answer
27 views
Monte Carlo Algorithms : Are there any problems where two opposite Monte Carlo algorithms could solve it?
I started reading on Probabilistic algorithms and Monte-Carlo algorithms. Since a Monte-Carlo can only give a certain answer for either True or False, I was wondering if it's conceivable that for the ...
1
vote
2answers
111 views
Randomly Choosing a N-Bit Prime
I've been studying some number theory, and I came across this problem:
Lagrange’s prime number theorem states that as N increases, the number of primes less than $N$ is $Θ(N/ log(N))$.
...
2
votes
0answers
47 views
Insertion in 123 skip list
I had a problem in my exam dealing with 1-2-3 skip lists.
I have a problem with the insertion process in a 1-2-3 skip list. What I understand is that if the minimum of heights of 2 nodes in a 123 ...
1
vote
0answers
21 views
Extracting room voids in a house
I am looking to create a series of closed volumes that represent the empty voids made by rooms in a house.
In order to do this, all I have is the raw geometry of all the elements that encapsulate ...
1
vote
0answers
54 views
Finding subset of integer summing up above threshold
Given an array $|A|=n$ of integers, and $m,k \in \mathbb{N}$, I want to find $m$ elements $a_{i_1},...,a_{i_m}$ of $A$ such that $\sum a_{ij} \geq k$ (repitions allowd), or determine that no such ...
1
vote
0answers
30 views
Probabilistic linebreaking algorithm
I'm currently trying to implement this paper. Based on a bayesian network, the paper stays unclear about how to ultimately use it's content ("straightforward inference"). But after a lot of ...
5
votes
1answer
111 views
Is it possible to simulate a fair coin with a finite number of tossing of a biased one?
It is a classic problem to simulate a fair coin with a biased one.
According to Fair Coin (wiki),
John von Neumann gave the following procedure:
Toss the coin twice.
If the results ...
4
votes
2answers
58 views
Fast sampling from discrete space
Assume we are given a set $X = \{x_1,...,x_n \}$ of size $n$, and a probability distribution $P$ over $X$. I am interested in an algorithm $A$ which can sample from $X$ according to $P$, i.e. $\Pr(A=...
2
votes
1answer
70 views
SAT Solving + Turing Machines
I have a couple of questions based on how SAT solvers work. I understand that SAT solvers may employ any/all of the following techniques:
Randomness
Heuristics
Backtracking
SAT is just one example ...
1
vote
0answers
33 views
distinguishing two biased coins
I had a simple probability question: suppose we have two coins, coin 1 is heads with probability $= 10\epsilon$ and coin 2 is heads with probability $=\epsilon/10$. Given an unknown coin, how many ...
3
votes
1answer
51 views
Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?
Context, I have a geometric algorithm that is sensitive to collinear points and receives as input a list of points in 2D generated randomly. Suppose that I have a Boolean function nonCollinear(x,y,z) ...
3
votes
1answer
56 views
Choosing a random edge with restrictions
Given a bipartite graph $G = (V, U, E)$ such that $|V| = |U| =2^n$, one wants to sample an edge from $G$, uniformly at random, with the following operations:
1. One can sample $u \in U$ w.p $\frac{1}{|...
1
vote
1answer
47 views
Connection between probabilistic algorithm and distributional algorithm
A basic question about the connection between two notions. I am sure these are known notions in CS but I struggle with the basics:
First Definition:
A probabilistic algorithm $A(n)$ decides $L$ if for ...
1
vote
1answer
41 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 ...
2
votes
1answer
23 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 ...
0
votes
0answers
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,...
0
votes
2answers
403 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:
...
1
vote
1answer
36 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 $\...
0
votes
1answer
37 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).
...
0
votes
1answer
36 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}{...
1
vote
0answers
43 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?
2
votes
1answer
98 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}$...
1
vote
1answer
46 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 ...
1
vote
1answer
50 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$,
$$\...
3
votes
1answer
237 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 &...
2
votes
2answers
36 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
1answer
83 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
...
2
votes
1answer
159 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 ...
-1
votes
1answer
117 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 ...
0
votes
0answers
39 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 \...
1
vote
0answers
34 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?
2
votes
1answer
144 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:
...
0
votes
0answers
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 ...
1
vote
1answer
112 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 ...
1
vote
1answer
41 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 ...
1
vote
1answer
59 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/...
1
vote
0answers
56 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 ...
1
vote
1answer
81 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 ...
1
vote
1answer
37 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 ...
4
votes
1answer
43 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 ...
2
votes
2answers
115 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 ...
