Questions tagged [probability-theory]
Questions about the branch of mathematics concerned with modelling and analysing random phenomena.
480
questions
0
votes
1
answer
747
views
ALOHA - Throughput and probabilities
I have a few questions regarding slotted-ALOHA. Assume a network have 25 users and transmission request probability = 0.25.
1) What is the throughput and what is the probability that a user will ...
2
votes
1
answer
63
views
Pseudo random permutation of a very large number of elements
Consider a file $\textbf{F}$ containing $n$ distinct elements, located on a hard drive. Given the large size of $n$, it's not feasible to load the entire file $\textbf{F}$ into main memory. Assuming ...
3
votes
1
answer
70
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,...
5
votes
1
answer
735
views
How to find a 2-wise independent hash family that is not 3-wise independent?
I'm trying to find a family of hash functions mapping $\{1, 2, ..., 2^n\}$ to $\{0, 1\}$ that is 2-wise independent but not 3-wise independent. Any ideas on that?
I know two 2-wise independent ...
0
votes
1
answer
208
views
information theory, find entropy given Markov chain
There is an information source on the information source alphabet $A = \{a, b, c\}$ represented by the state transition diagram below:
a) The random variable representing the $i$-th output from this ...
0
votes
0
answers
17
views
Analysis of Simon's Algorithm: Probability Expression for Matching Queries
The Simon's problem is that, given a function $f:\{0,1\}^n\to\{0,1\}^n$ such that, for all $x,y\{0,1\}^n$ t satisfies
$$
f(x)=f(y)\text{ iff }x=y\oplus s
$$
where $s\in \{0,1\}^n$, and the Simon's ...
0
votes
1
answer
77
views
Finding the first vertex in a recursively growing graph
I have an undirected graph which grew according to a recursive algorithm, i.e., it started with a single vertex and then, one after another, new vertices arrived and connected to existing ones.
Now, I'...
3
votes
3
answers
521
views
Probability of overflow in a summation of fixed-size signed integers
How can I estimate the probability that the sum $S_n$ of $n$ uniform random 48-bit signed integers overflows a 64-bit signed integer?
Edit: the overflow can occur at any step, not only on the final ...
0
votes
0
answers
56
views
Growth of the average numbers of peaks for the permutations of $n$ sticks
There are $n$ sticks of lengths $1$ to $n$ in a row. Upon permuting them randomly, we may calculate the average number of peaks viewed from left. A peak is a stick such that all sticks to its left are ...
1
vote
0
answers
23
views
Clustering 2D points with flavour
Problem Description
I have two sets of 2D points with flavours:
Noisy points $$p_i = (x_i, y_i, f_i) : p_i \in N : |N|\approx 10^8 $$
and true points $$p_{t_i} = (x_{t_i}, y_{t_i}, f_{t_i}) : p_{t_i} \...
0
votes
1
answer
56
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 ...
22
votes
11
answers
20k
views
How to simulate a die given a fair coin
Suppose that you're given a fair coin and you would like to simulate the probability distribution of repeatedly flipping a fair (six-sided) die. My initial idea is that we need to choose appropriate ...
0
votes
1
answer
23
views
Latent variable model from measure theory perspective
It's common in machine learning papers to see things like $p(x,z|\theta)$ or $p(x|z)$. Where $x$ is usually the data vector, $z$ the latent vector and $\theta$ the model parameter, like network ...
0
votes
1
answer
43
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 =...
2
votes
1
answer
155
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
2
answers
180
views
Analysis of QuickSort Expected Time Complexity: Without Counting the Number of Comparisons
While reading CLRS (4th ed.) regarding the analysis of the expected time for QuickSort, I encountered an alternative approach. The analysis involves the following steps:
Given an array of size $n$, ...
2
votes
1
answer
203
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 ...
0
votes
0
answers
29
views
If $NP \subseteq BPP$ then $NP = RP$. Confusion on the probability that M gives at least one wrong answer in BPP in n invocations
I was looking at the proof of if $NP \subseteq BPP$ then $NP = RP$ here.
At the end of the proof the author states:
"Note that if $M$ always gives correct answers on calls to $M$, then when $\phi$...
0
votes
0
answers
33
views
A probabilistic data structure based on flipping bits with probability $\frac{1}{2^x}$ for counting
How does this data structure work and what is its application?
...
1
vote
0
answers
31
views
Complexity class of a problem asking for a chance of receiving an item
I have asked a question on math.SE about if there is a way to do it better than by brute force, but this time I am interested in the complexity of the problem itself. I will repeat the problem, with a ...
2
votes
1
answer
104
views
How many random bits does this algorithm use on average?
Here, flip() is a function that returns 0 or 1 with equal probability. It can be proved ...
0
votes
1
answer
27
views
Cormen chapter 11 probability of two keys being assigned the same slot simple uniform hashing
I have been reading Cormen's chapter 11 and I stumbled upon the following statement on page 260 (3rd Edition):
Let xi denote the ith element inserted into the table, for i = 1, 2 ... n, and let ki = ...
1
vote
1
answer
53
views
Number of non-zero elements in intersection of two bloom filters
Let us assume I use bloom filters of size $m$ bits with $k$ hash functions.
Now I have two set $X$ and $Y$. Let $B(X)$ be bloom filter of the set $X$. In general I know that $B(X\cup Y)= B(X) \lor B(Y)...
0
votes
0
answers
17
views
Transductive Information Maximization vs classification with feature embedding in higher dimensional spaces?
Recent research work has shown that transductive learning/inference outperforms standard methods that were used before, where people embed features in a high dimensional space and then use the ...
2
votes
0
answers
76
views
Distribution of $k$-matchings in a random graph
Take the Erdos-Renyi random graph $G(n,p)$, i.e. the random graph with $n$ vertices and where each possible edge has an independent probability of $p$ of being present. Recall that a $k$-matching is a ...
1
vote
1
answer
103
views
What kind of bigram probability smoothing is this?
I hope it isn't off topic but I need to understand this example. Given the corpus 12 1 13 12 15 234 2526 and smoothing factor of ...
1
vote
0
answers
46
views
distribution choice for network latency
Consider this situation. A few clients are connected to a server over the internet.
I define network latency as the time between request leaving the client and reaching the server.
What distributions (...
1
vote
0
answers
69
views
How can the mutual information be equal to minus conditional entropy? [closed]
I am reading the following paper:
https://arxiv.org/abs/2301.06941
The authors in Eq.(8) have obtained a relation which has the mutual information, $i$, in the exponent of the exponential on the RHS ...
2
votes
1
answer
138
views
Dynamic programming: optimal order to answer questions to score the maximum expected marks
You have $n$ questions in an exam. Question $i$ is answered correctly with probability $p_i > 0$. If question $i$ is answered correctly, you get $R_i$ marks. You can choose to answer
the questions ...
0
votes
3
answers
188
views
Bayes theorem probability doesn't make sense
I try to use Bayes Theorem to calculate the probability of $P(A|B)$. I have $P(A)$ in column1, $P(B|A)$ in colmn2, $P(B)$ in column 3. I get the following:
my calculations were:
$$P(B/A) = 0.8\times ...
1
vote
1
answer
66
views
Generate uniform random vectors
Problem : Consider a random vector $v$ which is uniformly distributed over the sample space $S = \{v \in \mathbb{Z}^{n} : 1^Tv = a , v \ge 0\}$ . How to efficiently generate such random vector ?
note :...
0
votes
1
answer
316
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
1
answer
132
views
Distributing cards randomly given constraints
We want to distribute 3*n known cards among 3 players evenly given a set of constraints that prohibits some players from having certain suits.
For example:
We want to distribute 1H, 2H, 3S, 4S, 5D, 6D ...
3
votes
1
answer
105
views
Algorithm to select a random bit string with constraints
Problem Description
Given $a, b, n \in \mathbb{N}$ with $a < b < n$.
Let $M$ be the set of all possible bit strings of length $n$ which begin and end with one and have at least $a$ and at most $...
0
votes
1
answer
22
views
influence of neighourhood points
Im trying to understand the following question. Suppose $h,f:\{-1,1\}^n\rightarrow \{-1,1\}$ satisfy $\sum_x h(x)f(x)\leq 0.5$, then one can rewrite this as $\textsf{Pr}_x [h(x)=f(x)]\leq 3/4$. Can we ...
0
votes
1
answer
535
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
1
answer
40
views
Expected value of maximum of a matrix of size $n$
I have a square matrix (call it $A$) of size $n$ ($n$ is a positive integer). Each column is a permutation of $[1:n]$.
I take the first row of $A$, i.e. $A(1,:)$ and wonder what will be the frequency ...
4
votes
3
answers
2k
views
Randomly built binary search trees
In Introduction to Algorithms (CLRS) 3rd Edition, page 299, the section attempts to prove:
The expected height of a randomly built binary search tree on $n$ distinct keys is $O(\lg n)$.
We define "...
1
vote
2
answers
52
views
Probabilty of Elements being smaller than a specific value
Right now i am looking at the following statement, but i cant grasp why it is correct.
Can somebody help?
"If we look at F0 uniformly distributed (and, say, pairwise independent) elements of
[0, ...
-2
votes
3
answers
2k
views
Probabilty that quicksort partition creates an imbalanced partition
I have come across this question:
Let 0<α<.5 be some constant (independent of the input array length n). Recall the Partition subroutine employed by the QuickSort algorithm, as explained in ...
3
votes
0
answers
53
views
Edge length in an EMST
Consider a domain on a unit grid such that the grid nodes hold a point with probability $\frac12$. We construct a Euclidean minimum spanning tree on these points.
How could we compute the probability ...
2
votes
1
answer
87
views
Probability of this random selection
Suppose we have an array of $n$ integers. Suppose that we pick one of these elements uniformly at random and call it $x$. Suppose that $\log n$ elements are also sampled (uniformly at random) from the ...
3
votes
1
answer
754
views
Is it possible to randomly allocate items to bins such that each distinct allocation has equal probability?
I'm trying to randomly allocate N indistinguishable items over B indistinguishable bins with unlimited capacity. Each allocation should occur with equal probability. An allocation identifies the ...
1
vote
0
answers
68
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. By computer I understand a definitive switchable Hardware.
I would like to call actual "quantum ...
2
votes
0
answers
45
views
Generalizing Fano's Inequality [closed]
Fano's inequality says the following:
Theorem: Let $X$ be a random variable with range $M$. Let $\hat{X} = g(Y)$ be the predicted value of $X$ given some transmitted value $Y$, where $g$ is a ...
3
votes
2
answers
106
views
Rank in a Convex Combination
Given vectors $A, B \in \mathbb{R}^{n}$, $w \in [0,1]$ and $x \in \mathbb{R}$, let
$$
Rank(A,B,w,x)=\sum_{i=1}^{n} \boldsymbol 1 \{w A_{i} +(1-w) B_{i} < x\}
$$
denote the number of elements in the ...
1
vote
1
answer
339
views
Deriving the expected number of steps that is taken to perform the k'th operation
Consider a datatype whose objects will be sequences of elements that has the following two methods
prepend($x, T$) which will insert an element to x to the beginning of the sequence T
search($T, i$) ...
0
votes
0
answers
27
views
Conditional probability of making claim by insurance policyholder
In any given year,a male automobile insurance policyholder make a claim with probability $p_m$ and a female automobile insurance policy holder will make a claim with a probability $p_f$ where $p_f \...
29
votes
10
answers
22k
views
Generating uniformly distributed random numbers using a coin
You have one coin. You may flip it as many times as you want.
You want to generate a random number $r$ such that $a \leq r < b$ where $r,a,b\in \mathbb{Z}^+$.
Distribution of the numbers should ...
0
votes
1
answer
73
views
Expected value of Markov chain after nth steps
A Markov chain $\{ X_n, n \geqslant 0\}$ with states 0, 1, 2 has the transition probability matrix $$P= \begin{bmatrix} \frac12 & \frac13 & \frac16 \\ 0 & \frac12 & \frac23 \\ \frac12 &...