Questions tagged [probability-theory]

Questions about the branch of mathematics concerned with modelling and analysing random phenomena.

Filter by
Sorted by
Tagged with
1
vote
1answer
21 views

Distribution of random Fourier coefficients

Let $f : \{0, 1\}^{n} \rightarrow \{-1, 1\}$ be a Boolean function. Let the Fourier coefficients of this function be given by $$ \hat f(z) = \frac{1}{2^{n}} \sum_{x \in \{0, 1\}^{n}} f(x)(-1)^{x \cdot ...
1
vote
0answers
18 views

Algorithm to mapping given probabilities to empirical probabilities

Consider following problem statement: You have given $n$ actions. You can perform any of them. Each action gives you success with some probability. The challenge is to perform given finite number of ...
1
vote
1answer
23 views

AEP with a Twist!

We know by AEP that if random variables $X_1,X_2,...$ are i.i.d. drawn from $P_X$ then the probability of the vectors in the weak typical set $$A_{\epsilon}^n = \{\vec x \in \mathcal{X}^n: |\frac{-1}{...
-2
votes
0answers
22 views

Probability of false positive for lookup in hashtable

I am going over Mikkel Thorups notes on hashing, as revision, and I came to the following exercise that i cannot see how to tackle (even initially - I know this is not ideal for a question.) $$ \...
1
vote
1answer
98 views

Count subset divisible by 3

I'm trying to solve this puzzle but I get stuck. I thought about trying to use the law of total probability to solve intermediate problems with subset of size $k$ but it didn't helped me that much. Is ...
1
vote
1answer
23 views

Efficiently selecting a random subset of size $m$ from a set of size $n$

This is a cross post of my question here on math.se. I have a list of $n$ items and would like to randomly select an $m$ set from it efficiently (in terms of time complexity). Also, I want all ...
2
votes
0answers
35 views

Integer sampling with exponentially decreasing probability

Given a probability $p$ and an integer $N$, I would like to generate a sample $S$ of the population $P=\{0,1,...,N\}$ such that integer $m\in P$ is sampled with probability $p^m$. It is trivial to do ...
0
votes
1answer
35 views

Sampling from the uniform distribution

Is there an efficient classical algorithm that generates samples from the uniform distribution (or a distribution that is close to the uniform distribution in total variation distance), over the set $\...
0
votes
0answers
23 views

Weird normal graph, what's happening?

This appears to be a very basic question for this Stack Exchange, but hopefully still welcome. I am a math teacher and wanted to write a program to demonstrate normal distributions. I wrote a simple ...
2
votes
1answer
55 views

Probability of winning a turn-based game with a random element

I am preparing for a programming exam on probability theory and I stumbled across a question I can't solve. Given a bag, which contains some given amount of white stones $w$ and some given amount of ...
0
votes
0answers
21 views

Double Hash Family Universality

Here I am given 2 hash families and I need to prove the universality of the double hash, but I am stuck as to how to prove this. I know the properties of an epsilon-universal family is that the ...
1
vote
1answer
35 views

Show that if $\mathcal{H}$ is PAC learnable in the standard one-oracle model, then $\mathcal{H}$ is PAC learnable in the two-oracle model

This is a question $9.1$ from Understanding Machine Learning Chapter 3. It goes like this: Consider a variant of the PAC model in which there are two example oracles: one that generates positive ...
0
votes
0answers
11 views

course suggestions to learn background for sensor fusion

Specifically what topics in probability would give me the background I need to understand sensor fusion? I'm looking for a college class that would include these topics, so I'm wondering what the ...
1
vote
1answer
109 views

Is any randomized Algorithm a probability distribution over the set of deterministic Algorithms?

If there is a finite set of Instances of size n and the set of (reasonable) deterministic algorithms is finit. Can any randomized Algorithm be seen as a probability distribution over the set of ...
1
vote
0answers
20 views

Calculate the probability of undetected errors for the whole file (not packets) in the CRCs

If we have a large file, I want to know how this will affect the probability of undetected errors, especially in CRCs. I know that undetected error rate (packet or chunk) is BitR * BER * 0.5k where k ...
4
votes
2answers
76 views

If I can efficiently uniformly sample both $A$ and $B\subset A$, can I efficiently uniformly sample $A-B$?

As posed in the question; the statement naively seems like it should be self-evident but there are no algorithms that come immediately to mind. Suppose I have some domain $A$ (in my case a subset of $\...
2
votes
0answers
30 views

In Universal Hashing- probability of poor performance is small and is the same for any set of keys of the same size

I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following claim: Universal Hashing uses randomization.For the example of a compiler's symbol table, ...
1
vote
1answer
13 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 ...
2
votes
1answer
30 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). ...
0
votes
0answers
12 views

Joint typicality and distance between the vectors

In the book by Cover and Thomas,the author says that We first review the single-user Gaussian channel studied in Chapter 9. P Here Y = X + Z. Choose a rate R < 12 log(1 + N ). Fix a good ($2^{nR}$ ...
2
votes
1answer
27 views

Adaptive arithmetic coding confusion

I'm confused about the point of adaptive arithmetic coding. I understand that static arithmetic coding involves using preset probabilities of symbols that remain static during the whole process. I ...
1
vote
1answer
44 views

Proof that if P=PSPACE, RP=BPP

Like the title says. I can't figure out how to prove this. I think it probably has to do with the polynomial hierarchy collapsing but I'm not sure.
1
vote
0answers
42 views

How to estimate the number of elements inserted to a Bloom filter

A Bloom filter is a probabilistic data structure that allows encoding sets with false positives. Parameterized by the number of bits $m$ in the array $A$ (initialized to zeros), and number of hash ...
1
vote
0answers
60 views

Variance of chain length in hashtable

I have a hashtable with length $m$. Initially it's empty. Next, $n/2$ unique random numbers $\in [0, n]$ are added to it. What would be variance of chain length when such $n/2$ numbers are being added ...
1
vote
0answers
198 views

Channel coding and Error probability. Where are these probabilities from?

From where are the following probabilities? We consider BSCε with ε = 0,1 and block code C = {c1, c2} with the code words c1 = 010 and c2 = 101. On the received word y we use the decoder D = {D1,D2} ...
0
votes
0answers
11 views

How Joint Probability Distributions are used to solve the problem of missing inputs in Classification

With n input variables, we can now obtain all 2^n different classification functions needed for each possible set of missing inputs, but the computer program needs to learn only a single function ...
1
vote
1answer
32 views

Is there an efficient algorithm for determining the probability a large randomly chosen integer is not divisible by any integer of some set?

Given a set of 10 integers $A = a_1, a_2, \cdots a_{10}$, is there an efficient algorithm which can tell me what's the probability a randomly chosen integer between $1$ and $10^{10}$ is NOT divisible ...
0
votes
0answers
23 views

Fundamentals of sampling without replacement

I would like to ask a question about fundamentals that are used intuitively in solving a simple probabilistic task about sampling with replacement. However, when I start to think about underlying ...
0
votes
1answer
123 views

Average number of inspections

Consider a set of n elements whose key values are $$0, 1, ..., n−1.$$ Let $p(i) (0 ≤ i ≤ n−1) $ be the probability that the element with key i is searched. Assume the following distribution of $p(i)’s$...
0
votes
1answer
59 views

How do I calculate the probability of a PCFG rule in a parser?

I'm quite struggling with calculating the probability of a rule for a PCFG. I've been looking for examples online and more information, but I am none the wiser. Here is an image of the slides. I ...
1
vote
1answer
113 views

Analyzing a randomized algorithm for finding an approximate median of an array

I'm given an array $A$ = ($a_1, a_2, \cdots a_n$), where n is uneven. For an element $a_i$ we denote its position in the array with $p(a_i)$. This element would be an $ε$-approximate median of the ...
2
votes
1answer
13 views

How to implement random sampling with continuous variables?

How functions like rnorm in R (and similar functions) create a random sample ? If I want to implement one algorithm to simulate this procedure what can I do? When you have the pdf or pmf of a ...
0
votes
1answer
26 views

Probability of data loss for mirrored,3 disk system

I am reading the book Database Systems the Complete Book 2nd Edition. A slightly modified Question 13.4.5 states: Suppose we use three disks as a mirrored group; i.e., all three hold identical ...
1
vote
2answers
359 views

Probability that two elements are compared in randomized quicksort

I am having an issue in a specific part of the randomized quick-sort analysis. As per the randomized quick-sort algorithm the pivot is chosen from the given subset on which it is called from a random ...
1
vote
1answer
43 views

Worst-case expected running time for Randomized Permutation Algorithm

I have an algorithm which, when given a positive integer N, generates a permutation of the first N integers (from 1 to N) using a method called randInt(x,y). The method randInt(x,y) will generate a ...
1
vote
1answer
69 views

Amount of expected loop iterations when searching an array by random index

Lets say we have an array A of size n. It has 1 as its first index and n as its last index. It contains a value x, with x occurring k times in A where 1<=k<=n If we have a search algorithm like ...
0
votes
1answer
27 views

An algorithm to determine probability of one string appearing earlier than another string in an evenly distributed binary sequence

Given two binary strings of length $n$ and $m$, determine in polynomial time the probability of the first appearance of one string being earlier than the first appearance of the other one in an evenly ...
3
votes
1answer
65 views

generalizing ball-bin problem to k-universal family

I am trying to solve a question in the book on Probability and Computing by Michael Mitzenmacher, Eli Upfal. The question asks to generalize ball-bin problem for 2-universal hashing to $k$-universal ...
4
votes
2answers
957 views

Generating random words by grammar

A bit of context I was writing a parser for a grammar, and for testing purposes I come up with idea to generate some random inputs. The grammar I was dealing with was much more complicated, in this ...
0
votes
0answers
42 views

how many parameters do we need to estimate for a general probabilistic model

Its a question from a test in machine learning. I have 3 binary variables x1,x2 and x3 (which means that each one of them can be either 1 or 0), each one of them has a binary output y (can be 0 or 1). ...
0
votes
1answer
45 views

Expected number of coins

Alice and bob play a game. Bob has a well-shuffled deck of $M=4999$ white cards and $N=4999$ green cards. Each permutation of cards in the deck is equally likely. Alice has set some rules for Bob. ...
1
vote
0answers
48 views

Calculate probability in graphical model

I have the following graphical model, in which I wish to compute $p(Intelligence = 1|Letter = 1, SAT = 1)$ But I'm not sure how to rewrite $p(Intelligence = 1|Letter = 1, SAT = 1)$? I was told to ...
1
vote
0answers
45 views

Decomposition of Mutual Information

I came across a book where the author uses the following property of mutual information: Let $X$,$Y$,$Z$ be arbitrary discrete random variables and let $W$ be an indicator random variable. $$ (1)\ \ ...
0
votes
1answer
38 views

Reservoir Sampling vs Round Robin

You are given a List of numbers (length unknown). Let's say the length is 10. GetRandom(List) is called once. If implemented correctly, each number has 1/10 probability of being returned. GetRandom(...
2
votes
1answer
22 views

Why there is no polynomially large sequence of polynomial large weights that derandomize the isolation lemma?

I was studying the paper Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size by Arvind and Mukhopadhyay and came across the following claim (Observation 1.2 on page 3): "More ...
1
vote
1answer
13 views

Probability of selecting a particular set, by sampling without replacement from a categorical distribution

Suppose I have a categorical distribution on items $1,\dots,n$, that assigns probability $p_i$ to item $i$. I now repeatedly sample from this distribution, until I have obtained $k$ unique objects. ...
-1
votes
1answer
33 views

From a randomized algorithm with expected time $O(n)$ to a reliable with determined running time

Let $A$ be a randomised algorithm and $F$ be a function such that $A$ returns $F(x)$ on any input $x$. Furthermore suppose that, for input $x$ of size $n$, the $\textbf{expected}$ running time of $A$ ...
3
votes
0answers
48 views

Node depth in randomly built binary search tree

It can be proved that randomly built binary search trees of size $n$ are of depth $O(\log n)$ and it is clear that level $k$ has at most $2^{k}$ nodes (root's level is 0). I have an algorithm that ...
2
votes
1answer
46 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 ...
1
vote
1answer
51 views

What kind of bigram probability smoothing is this?

I hope it isn't off topic but I need to understand this example. Given the corpus 12 1 13 12 15 234 2526 and smoothing factor of ...

1
2 3 4 5
8