Questions tagged [probabilistic-algorithms]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
26 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 ...
rus9384's user avatar
  • 1,429
2 votes
0 answers
18 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 $...
chausies's user avatar
  • 532
3 votes
1 answer
88 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 ...
Ilkay Burak's user avatar
0 votes
1 answer
104 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 ...
diegodr02's user avatar
0 votes
0 answers
31 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 ...
Kumar A.'s user avatar
1 vote
1 answer
38 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)...
Galois group's user avatar
0 votes
0 answers
87 views

Is NP=RP(2^-n)?

I believe its true but struggle to prove. I know NP=union over positive c's of RP(2^-(n^c)) and from here to prove that RP(1/2^n) contained in NP is immediate. the other side is the problem. I've ...
Tomer Thaler's user avatar
1 vote
0 answers
36 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 ...
l4m2's user avatar
  • 249
3 votes
1 answer
94 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 $...
user13062187's user avatar
1 vote
2 answers
52 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, ...
Ilian kurt's user avatar
1 vote
0 answers
56 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 ...
Lightsong's user avatar
  • 239
4 votes
0 answers
27 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 ...
almostuseful's user avatar
2 votes
1 answer
86 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 ...
joeren1020's user avatar
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 ...
Student's user avatar
  • 219
0 votes
1 answer
409 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 ...
Equation_Charmer's user avatar
1 vote
0 answers
39 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 ...
user153219's user avatar
0 votes
1 answer
26 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. ...
rapt's user avatar
  • 113
1 vote
1 answer
59 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 ...
rus9384's user avatar
  • 1,429
0 votes
0 answers
37 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 ...
Ameer Jewdaki's user avatar
2 votes
1 answer
90 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 ...
AK-23's user avatar
  • 123
1 vote
2 answers
97 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 ...
Maltus's user avatar
  • 11
1 vote
0 answers
26 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 ...
Matplayerino's user avatar
1 vote
0 answers
22 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 ...
yarchik's user avatar
  • 125
1 vote
0 answers
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 ...
Xiobiq's user avatar
  • 161
3 votes
0 answers
123 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 ...
yarchik's user avatar
  • 125
1 vote
1 answer
108 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 ...
Alisa Sireneva's user avatar
0 votes
1 answer
45 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 ...
Chao Somnium's user avatar
1 vote
1 answer
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 ...
Jonas Kölker's user avatar
2 votes
1 answer
280 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 ...
Johnny's user avatar
  • 353
2 votes
2 answers
271 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$...
AspiringMat's user avatar
1 vote
0 answers
20 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$-...
user141088's user avatar
2 votes
2 answers
300 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 ...
heckeop's user avatar
  • 123
1 vote
0 answers
38 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 ...
Sid Meier's user avatar
  • 229
1 vote
1 answer
64 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 ...
fox's user avatar
  • 183
1 vote
1 answer
44 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$ ...
user136729's user avatar
0 votes
1 answer
162 views

Dynamic programming and probability - list of problems

Does anyone have a list of problems where you have to combine dynamic programming with probability?
Hilberto1's user avatar
  • 181
0 votes
1 answer
377 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 ...
Ashkan Khademian's user avatar
3 votes
0 answers
69 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) $ ...
Ameer Jewdaki's user avatar
0 votes
1 answer
33 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 ...
N8_Coder's user avatar
  • 133
2 votes
2 answers
61 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,\...
Grigori's user avatar
  • 95
4 votes
2 answers
435 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 $...
kings's user avatar
  • 141
3 votes
1 answer
120 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 ...
porton's user avatar
  • 433
0 votes
1 answer
72 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://...
aNormalPerson's user avatar
0 votes
0 answers
143 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 ...
nir shahar's user avatar
  • 11.5k
1 vote
0 answers
864 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^\...
Nascimento de Cos's user avatar
2 votes
1 answer
38 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 $...
Simon's user avatar
  • 232
0 votes
1 answer
53 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 ...
Nacho's user avatar
  • 1
-1 votes
1 answer
175 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? ...
Constantin's user avatar
0 votes
1 answer
167 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&...
Théo Exagon's user avatar
1 vote
1 answer
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 ...
Jake's user avatar
  • 3,790

1
2 3 4 5