Questions tagged [probability-theory]
Questions about the branch of mathematics concerned with modelling and analysing random phenomena.
386
questions
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 diļ¬erent classiļ¬cation 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 ...
