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
1answer
26 views

Distribution of $(X_1,X_2)$ if $X_1\pm X_2$ are two independent $N(1,4)$

$X_1+X_2$ and $X_1-X_2 $ are i.i.d. $N(1,4)$. What is the distribution of $X = (X_1,X_2)^T$? I know i.i.d. is an independent and identically distributed random variable but I don't know how to use it ...
2
votes
1answer
16 views

How Data Compression relates to Estimating Distribution?

I recently read this paper Mahoney, 1999. And encountered this line, optimal compression of a probabilistic language L with unknown distribution (such as English) using an estimated distribution M (...
1
vote
0answers
14 views

Degree of regularity of a Markov chain

A Markov chain with transition matrix $P$ is termed regular if for some $n$, all entries of $P^n$ are positive. Is there a known notion of degree of regularity quantified in terms of how soon all ...
3
votes
2answers
148 views

Proving a certain hypothesis class on a given distribution is not learnable

I had this question in Learning theory, but it's really just a question in probability theory to be honest, so I'm gonna try to rephrase it in a way that really emphasizes what I was trying to do to ...
0
votes
0answers
15 views

Problem on probability given frame sizes and their error correction probabilities in a wireless system

I am stuck trying to solve the following question for a while Bit error rate after demodulation in an wireless system = 1.0e-03. The system has 4 possible frame sizes – 48 bytes, 96 bytes, 72 bytes ...
0
votes
1answer
28 views

what is the relationship between entropy and variance?

Consider a simple Bernoulli variable X X = 1 with probability p X = 0 with probability (1-p) The variance is simply p(1-p). The ...
1
vote
1answer
20 views

Computational indistinguishability for any distribution using a Chernoff bound

I had a question about a general statement regarding finding a computationally indistinguishable distribution given any distribution, observed (in the third paragraph of Section 11, page 31) here. ...
1
vote
1answer
25 views

How to show independence and uniform distribution of hash codes from k-wise independent hash functions?

Most definitions of a $k$-wise independent family of hash functions I have encountered state that a family $H$ of hash functions from $D$ to $R$ is k-wise independent if for all distinct $x_1, x_2,\...
2
votes
0answers
38 views

Whether there exists a probabilistic automaton satisfying $\Pr \{ x \in L\}=\frac{\Pr \{ x \in L_1\}}{\Pr \{ x \in L_1\}+\Pr \{ x \in L_2\}}$

Suppose that there are two probabilistic automata $A_1$ and $A_2$ with a same finite alphabet $\Sigma$. The languages of them are $\mathcal{L}_{1} \subseteq \Sigma^*$ and $\mathcal{L}_{2} \subseteq \...
0
votes
0answers
31 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^\...
0
votes
0answers
84 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^{...
0
votes
1answer
38 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
13 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
25 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
42 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
59 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 ...
1
vote
1answer
39 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
20 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
45 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
34 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
1answer
60 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
36 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
25 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
42 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
53 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
30 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
23 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
185 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
120 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
42 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
56 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
25 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
47 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
13 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
116 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
79 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
35 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, ...
0
votes
1answer
24 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
38 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
15 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
44 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
60 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
2 3 4 5
9