Questions tagged [probability-theory]
Questions about the branch of mathematics concerned with modelling and analysing random phenomena.
434
questions
1
vote
1answer
14 views
Question about Markov Chains
The following question is taken from the book titled "Probability models for Computer Science" written by Sheldon M. Ross.
Question:
A particle moves along n + 1 vertices that are situated ...
2
votes
1answer
32 views
Analysis of a calculation of expected number of collisions in hashing
For a formal problem statement, I quote from the text Introduction to Algorithms by Cormen et. al
Suppose we use a hash function $h$ to hash $n$ distinct keys into an array $T$ of length $m$. ...
2
votes
0answers
52 views
Decision problem solution monte carlo
I have a rather straightforward question for this community (that I am not able to solve). Assume there is a probability of Tom having a bag of candy. If Tom has a bag, he says the truth 4/5 times and ...
0
votes
0answers
17 views
Computer network graph design
In the following question, we need to suggest a graph design and a routing algorithm.
Routing from $A$ to $B$ is done by returning an edge sequence in the graph that will lead us from $A$ to $B$
...
0
votes
1answer
21 views
Algorithm best compare similarities between two data sets in percentage
I'm trying to create an algorithm that finds the percentage of similarity between two subjects with sets of survey questions.
Example:
Q1: Do you prefer physically demanding tasks?
A1: Nope Maybe Yes -...
2
votes
0answers
48 views
questions about queuing delay
I am learning computer network, and confused by the queuing delay. In my textbook, it says that when La/R approaches 1, and with random inter-arrival times, then the average queuing delay is closer to ...
0
votes
1answer
201 views
If the probability of frame being lost is $P.$ Then, calculate the mean no. of transmission for the frame to make it success$.$ [closed]
Here the probability of frame being lost is $P.$ So the probability of frame reaching safely would be $(1-P).$
Now lets consider that the frame will reach safely in $k$-th transmission. That means ...
1
vote
0answers
41 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
26 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 ...
2
votes
1answer
40 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
69 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
136 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
108 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
24 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
33 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
78 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
9 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
35 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
158 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
42 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
42 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
91 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
38 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
53 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
176 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
34 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
22 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
15 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
168 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
23 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
240 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
42 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
63 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
40 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
113 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
104 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
43 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
21 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
32 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
120 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
144 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
76 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
23 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
47 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
51 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
40 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
37 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,...