Questions tagged [probability-theory]

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

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5
9