Questions tagged [probability-theory]
Questions about the branch of mathematics concerned with modelling and analysing random phenomena.
429
questions
1
vote
0answers
33 views
Is quantum computing a serious usable instrument for the IT industry?
Following this latest and very exciting research object I can't find till now a usable computer in that style.
I would like to call actual quantum computing by the topic "researching of quantum ...
1
vote
1answer
23 views
Why does random noise in recurring task periods result in uniform period offsets?
I have a recurring task which finished just now. I schedule it to run every ten minutes; the task will reoccur $10n$ minutes from now for all positive $n$. If instead I choose 50/50 between ten ...
1
vote
1answer
24 views
Why is $\mathcal{D}^m(\{S:L_{(\mathcal{D},f)}(A(S))\gt \epsilon\})\leq \mathcal{D}^m\left(\bigcup^4_{i=1}F_i\right)$ true?
I am studying the book "Understanding Machine Learning:
From Theory to Algorithms". I am struggling to understand the solution to exercise 3 (2) on page 41.
Exercise:
An axis aligned ...
1
vote
0answers
11 views
Distributed Graph Consensus to fit a distribution?
$G$ is a strongly connected graph with nodes $V$ and edges $E$. Each node $v_i$ receives a sample $x_i$ from a Gaussian $\mathcal{N}(\mu,\sigma^2)$ with unknown mean and variance.
The objective is for ...
2
votes
1answer
27 views
Given only the expected runtime of an algorithm, what can Markov's inequality tell us about its worst-case runtime?
The following is exercise 3.8 from the first edition of Mitzenmacher and Upfal's Probability and Computing: Randomized Algorithms and Probabilistic Analysis.
Suppose that we have an algorithm that ...
2
votes
2answers
109 views
Question about "with high probability"
An event that occurs with high probability is one whose probability depends on a certain number $n$ and goes to $1$ as $n$ goes to infinity, i.e. it can be made as close as desired to $1$ by making $n$...
2
votes
2answers
88 views
Satisfiable CNFs where each clause contains logarithmically many different literals
Studying for my finals in Complexity theory. This question comes up in different variants and it requires to use probability.
A side note before, to be more clear: A CNF clause consists of $n$ clauses
...
1
vote
0answers
22 views
How long a graph random walk takes to hit every vertex?
I have a simply connected graph $G$. I start at a uniformly randomly chosen vertex, and from there, randomly walk through the graph by choosing a random edge to follow at each step.
On average, how ...
1
vote
0answers
32 views
Computing a threshold function
Let $f$ be any function from $\{0, 1\}^{n}$ to $\{-1, 1\}$. For a given $f$, let us define another function $g_f$ as
\begin{equation}
g_f(x) = \sum_{x \in \{0, 1\}^{n}} f(x).
\end{equation}
Let us be ...
2
votes
1answer
59 views
Deriving a lower bound on the conditional entropy, conditioned on an event
I came across Lemma 19 in Certifying Equality With Limited Interaction, which states the following for jointly distributed random variables $Z$, $W$, where $Z$ takes values in $\{0,1\}^n$, and some ...
1
vote
0answers
8 views
expected value of map generate algorithm
I designed a program to create a map in my 2D game program. And I have three questions...
algorithm:
step1:
...
1
vote
1answer
34 views
A small question about generating random variable with geometric distribution
I was reading Professor Knuth's Volume 2 (page 136) about generating a geometrically distributed random variable $N$ (with $p$ as the probability of success).
Basically, the idea is to generate a ...
4
votes
1answer
149 views
Count Sketch probability bound
I have been reading up on the Count Sketch algorithm, and I stumpled upon the Count Sketh algorithm explained in section 5 of https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf. Then, I ...
2
votes
2answers
36 views
Quicksort: Probability of an element being compared to fewer than $k$ pivot elements
Assume we want to use quicksort on some array $s$ with length $n$ consisting of only $n$ distinct elements.
Let $S_{(1)},S_{(2)},\dots,S_{(n)}$ be the sorted order of the elements in $S$.
Furthermore, ...
0
votes
1answer
28 views
Dynamic programming and probability - list of problems
Does anyone have a list of problems where you have to combine dynamic programming with probability?
4
votes
1answer
77 views
Probability of reaching a state in asymmetric random walk
Consider the following random walk:
Namely, if $S_i$ is the state at time $i$, then $\Pr(S_{i+1}=1|S_i=0)=1$, and for every $s>0$ we have
$$S_{i+1}|S_i=s=
\begin{cases}
s+1 & \text{w.p. }1-p\\
...
0
votes
0answers
22 views
Simple Bayesian Question
I have the following Bayesian Network.
I have worked out the following:
P(H) = P(H|D) + P(H|¬D) = 0.5 + 0.1 = 0.6
P(D|H) = (D)∗(P(H|D) +P(H|¬D)) = 0.3∗(0.5 + 0.1) = 0.18
How do I compute the ...
0
votes
1answer
18 views
How to sample Bivariate Normal Distribution with Accept reject method
I have to write python code in jupyter due to sampling bivariate normal distribution with 3 sampling methods:
Prior Sampling
Gibbs Sampling
Rejection Sampling
I have done the first two samplings and ...
1
vote
0answers
37 views
Concentration inequality of sum of geometric random variables taken to a power
Let $X_1, \cdots, X_n$ be $n$ independent geometric random variables with success probability parameter $p = 1/2$, where $X_i = j$ means it took $j$ trials to get the first success. Let $S_d = \sum_{i=...
0
votes
0answers
116 views
Average number of comparisons for a successful search of a prime number in a binary search tree
A binary search tree is constructed by inserting the following value sequentially:
$$3, 9, 1, 6, 8, 7, 10, 4, 2, 5$$
Let $p_v$ be the probability to search for the value $v$ in the binary search tree (...
1
vote
0answers
27 views
Why does attempting to estimate the entropy of text by randomly choosing chars in it and counting how often they are equal give wildly wrong results?
Why does attempting to estimate the entropy of a string, by randomly choosing pairs of (not necessarily adjacent) characters in it, and counting how often the selected characters in the pairs are ...
0
votes
1answer
33 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
19 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
161 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
17 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
80 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
30 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
46 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
39 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 \...
1
vote
0answers
59 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
89 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
39 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
16 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
27 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
75 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
99 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
60 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
21 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
50 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
38 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
35 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
33 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
120 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
28 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
43 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 ...
1
vote
0answers
67 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 &...
