Questions tagged [probability-theory]
Questions about the branch of mathematics concerned with modelling and analysing random phenomena.
402
questions
0
votes
0answers
70 views
Fast factorial computation
I'm trying to solve this problem - https://codeforces.com/problemset/problem/711/E
I've already found and proved that the result is equal to:
$$
1 - \frac{2^n (2^n - 1) \cdots (2 ^ n - k + 1)}{2^{...
1
vote
1answer
32 views
The probability that a person succeeds to pick the longest stick from a randomly ordered n sticks of distinct lengths following the optimal strategy?
To begin with, consider two persons(Px and Py) are playing a game. Px is the organiser of the game who has n sticks of distinct lengths and displaying them one by one to Py in a random order, with ...
0
votes
1answer
11 views
Conditional probability in Expectation Maximization (EM)
I've got the following equation:
$p(j = 1 | x, \theta) = \frac{p(j=1,x | \theta)}{p(x | \theta)}$
Why does it hold? Or maybe, how do I use Bayes Theorem in this case, i.e. if we do not only have $p(j =...
0
votes
2answers
24 views
Does undecidability ever imply unmeasurability and make a notion of probability ill-defined?
Not sure precisely how to ask this question, but I want to understand if it is meaningful to ask about probabilities when aspects of the definition might be undecidable. My curiosity extends to ...
0
votes
1answer
38 views
Chebyshev’s inequality problem in one exercises I can't understand if I did it right or not
This is what do I have to solve:
Byron Book: Exercise 8.3 chapter 8
Verify the use of Chebyshev’s inequality in (8.6) of Example 8.16. Show that if the population
mean is indeed 48.2333 and the ...
1
vote
1answer
42 views
Is there an algorithm for random sampling from a priority queue with probability proportional to priority?
Suppose I want to randomly sample from a large set of items, each of which has a "score". I want my probability of sampling to be proportional to the score. One simple way to achieve this ...
0
votes
0answers
19 views
Applying Bayes rule in the context of reinforcement learning
I was watching this video on reinforcement learning. At 1:28, it says following:
$$Pr(s'|a,z,s)=\frac{Pr(z|s',a,s)Pr(s'|a,s)}{Pr(z|a,s)}$$
I was unable to get how this was obtained. I pondered a bit ...
1
vote
1answer
23 views
In counterfactual regret minimization, why are additions to regret weighted by reach probability?
I'm reading the algorithm on page 12 of An Introduction to Counterfactual Regret Minimization. On lines 25 and 26, we accumulate new values into $r_i$ and $s_i$:
$25.\space \space r_I[a] ← r_I[a] + \...
1
vote
1answer
18 views
Deterministic algorithms for computational distance between distributions
Computational distance between sequences of distributions $\{X_i\}_{i \in \mathbb{N}}$ and $\{Y_i\}_{i \in \mathbb{N}}$ can be defined as the maximum, over all probabilistic polynomial time algorithms ...
0
votes
1answer
42 views
oone exmple in hash topics?
Example: Suppose $H:${$1,...,n$} $\rightarrow ${$1,..,n$} be a uniform hash function. for input $x$, $z$ is equal to number of trailing zero in the right side of $H(x)$. for $0 \leq c \leq 1$ what is ...
1
vote
1answer
49 views
Optimal algorithm to distinguish given black box access
This is a variant of this question. Consider two probability distributions $D$ and $U$, over $n$-bit strings, where $U$ is the uniform distribution. Assume that $D$ and $U$ are far apart in total ...
0
votes
1answer
29 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
vote
1answer
27 views
Distinguishability given black box access to the distribution
Consider two probability distributions $D$ and $U$, over $n$-bit strings, where $U$ is the uniform distribution. We are not given an explicit description of $D$: we are only given black-box access, ie,...
0
votes
0answers
31 views
On the probability of randomized testing covering all combinatorial testing interactions
I'm interested in how fuzz testing and something called combinatorial testing. Combinatorial testing attempts to forgo exhaustive testing in favor of trying to test all possible "interactions&...
0
votes
0answers
23 views
Transition Function in MDP
I got a question about who and how sets the transation function values in markov decision processes?
I mean when some says that an agent, in real world grid, is going to step up by %80 and left/right ...
1
vote
1answer
35 views
Distinguishability of distributions that are not close given just one sample
Consider (over $n$-bit strings) the uniform distribution $U$, and another distribution $D$ such that
\begin{equation}
\text{Distance}(D, U) \geq \frac{1}{e},
\end{equation}
where $\text{Distance}$ ...
1
vote
1answer
21 views
Notation within gaussian function
On our lecture slides we have two different notations of the gaussian function.
First it gets introduced as follows:
$$p(x_n|\theta) = \frac{1}{\sqrt{2\pi}\sigma}exp\{-\frac{(x_n-\mu)^2}{2\sigma^2}\} \...
1
vote
1answer
39 views
Indistinguishability of exponentially close distributions
Let $D_{1}$ and $D_{2}$ be two probability distributions over $n$-bit strings such that the total variation distance between them is $\mathcal{O}\left(1/{2^{n}}\right)$. Given as input a polynomial ...
0
votes
0answers
27 views
Calculating E(x) where it is the count of triangles in a special graph with n vertices
Assume we have n people with names: $h1, h2, ... , hn$ and they are going to shake hands with each other. The chance for every pair to shake hands is $0.6$.
define $T$ the count of distinct triads of ...
0
votes
0answers
47 views
Pairwise independent hash function family?
I am looking for a family of pairwise independent hash functions $\mathcal{H} = \{h \mid h:[n]\rightarrow [m]\}$ that is easily computable.
As an example that doesn't seem to work, choose a prime $p &...
0
votes
0answers
13 views
Understanding deterministic capacity of AVC
In the paper by Csiszar & Narayanan where they proved the deterministic capcity of an AVC, can someone please explain the decoder logic?
The second condition used by the decoder is
$$ I(XY;X'|S) \...
1
vote
1answer
27 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 ...
2
votes
0answers
19 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}{...
1
vote
1answer
153 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
54 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
37 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
25 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 ...
1
vote
0answers
22 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
41 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
12 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 ...
2
votes
1answer
113 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 ...
4
votes
2answers
78 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
32 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
20 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
37 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
14 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
38 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
51 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
52 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
61 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
201 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
13 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
33 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
24 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 ...
1
vote
1answer
125 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$...
1
vote
1answer
184 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
138 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 ...
