Questions tagged [probability-theory]
Questions about the branch of mathematics concerned with modelling and analysing random phenomena.
470
questions
0
votes
1
answer
53
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 ...
CommunityBot
- 1
0
votes
1
answer
37
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 =...
CommunityBot
- 1
2
votes
1
answer
110
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$. ...
CommunityBot
- 1
2
votes
1
answer
139
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 ...
CommunityBot
- 1
0
votes
1
answer
669
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 ...
CommunityBot
- 1
1
vote
1
answer
57
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,...
CommunityBot
- 1
4
votes
1
answer
666
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 ...
CommunityBot
- 1
0
votes
0
answers
8
views
Does optimal input distribution for $W^{\otimes n}_{Y|X}$ tell us anything about the optimal input distribution for $W^{\otimes n-1}_{Y|X}$?
Suppose I have $n$ i.i.d. copies of some channel $W_{Y|X}$ for some finite $n$. I wish to send the maximum number of messages over these $n$ copies such that the error in decoding the message is at ...
- 262
0
votes
0
answers
27
views
If $\overline{3SAT}\in BP\cdot NP$ then $PH=\Sigma_3^P$
I have the problem
If $\overline{3SAT}\in BP\cdot NP$ then $PH=\Sigma_3^P$
To solve this I am using a result $BP\cdot NP\subset NP/poly$ which I can prove (not doing here). I have two solutions but ...
- 123
0
votes
1
answer
186
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 ...
CommunityBot
- 1
1
vote
0
answers
15
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 (...
- 111
1
vote
0
answers
66
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 ...
CommunityBot
- 1
2
votes
1
answer
107
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 ...
- 38.2k
0
votes
3
answers
170
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 ...
- 113
0
votes
0
answers
24
views
Universal hash functions and prime number modulus scheme
Definition of a universal hashing function $h: U \rightarrow[m]$ (where $[m]=\{0, \ldots, m-1\}$) is that for any given distinct keys $x,y \in U$, when $h$ is picked at random (independently of $x$ ...
- 101
1
vote
1
answer
96
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 ...
CommunityBot
- 1
0
votes
0
answers
22
views
Manipulating a binary tree representation
I am designing a discrete probability distribution with a string of binary values as an input $\{s_i\}\in\{S_i\}$, and binary outputs $e\in E$ with Bernoulli probability $P(E=1|\{S_i\})=XOR[\{S_i\}]=...
- 1
1
vote
1
answer
51
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 :...
- 117
0
votes
1
answer
289
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 ...
CommunityBot
- 1
1
vote
1
answer
103
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 ...
- 12k
3
votes
1
answer
75
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 $...
- 41
0
votes
1
answer
20
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 ...
CommunityBot
- 1
0
votes
1
answer
480
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 ...
CommunityBot
- 1
1
vote
1
answer
35
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 ...
- 274k
4
votes
3
answers
1k
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 "...
0
votes
0
answers
15
views
The RAM invalid object estimation problem
The following problem is originated from my research work in my startup.
Suppose we have a collection of $k$ memory objects, where object $i$ has size $d_i$ bytes. We consider a process where the ...
- 367
1
vote
2
answers
47
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, ...
- 438
0
votes
0
answers
42
views
In two level perfect hashing from CLRS we use m = n at the first level for expected space<=3n. Instead if we choose m = αn can space be decreased
In two level perfect hashing scheme shown in CLRS 3rd edition 11.5, this also has a great explanation here
We set m = n at
the first level and then for secondary hash tables we set mi = n^2. This ...
- 57
-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
49
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 ...
- 592
2
votes
1
answer
85
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 ...
- 304
3
votes
1
answer
685
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 ...
D.W.♦
- 152k
1
vote
0
answers
65
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 ...
22
votes
10
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 ...
- 740
2
votes
0
answers
36
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 ...
- 21
3
votes
2
answers
90
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 ...
- 2,195
1
vote
1
answer
308
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$) ...
CommunityBot
- 1
0
votes
0
answers
22
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
21k
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 ...
- 27.4k
0
votes
1
answer
32
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 &...
0
votes
2
answers
42
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 ...
- 261
1
vote
1
answer
44
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 ...
- 261
4
votes
2
answers
214
views
Average vs Worst-Case Hitting Time
Consider a simple random walk on an undirected graph and let $H_{ij}$ be the hitting time from $i$ to $j$. How much bigger can
$$ H_{\rm max} = \max_{i,j} H_{ij}, $$ be compared to
$$ H_{\rm ave} = \...
- 261
1
vote
1
answer
48
views
Average and max. hitting time to a specific vertex [closed]
Consider simple random walks that stop when reaching a given node $x$ in an undirected, unweighted and connected graph on $n$ nodes.
Let
$H(i,x)$ denote the (expected) hitting time from $i$ to $x$, ...
- 261
1
vote
1
answer
97
views
Sample a set of N numbers without replacement, each element taken from N different weighted sets
Here's my problem: I have $N$ sets of integers $S_i$ where $|S_i| = n_i \forall i \in [1,N]$ each with non-uniform weights $W_i = \{w_{i,1}, ..., w_{i,n_i}\}$ such that $\sum_{j}{w_{i,j}} = 1$. I want ...
D.W.♦
- 152k
1
vote
1
answer
21
views
Conditional entropies of sum relations
Let $(X_1,Y_1)$ and $(X_2,Y_2)$ be identically and independently distributed. Also consider $Z=X_1+X_2$. I am trying to prove the following inequality:
$$ H(X_2 \vert Y_1 Y_2 Z) \leq H (X_1 \vert Y_1)\...
- 274k
0
votes
0
answers
28
views
Tight bounds for expected maximum of k binomial(n,p) IIDs
What is the tightest lower and upper bound for the expected maximum value of k IID Binomial(n, p) random variables
I tried to derive it :
$$Pr[max \leq C] = (\sum_{i = 0}^C {n \choose i}p^i(1 - p)^i)^...
- 13
0
votes
0
answers
23
views
Entropy of a single Hint
Assume that the probability that a woman is above 80 years old is 3 times that of a man. How much information (in bits) do you get if you are given that a 80 year old person is a male?
How should I ...
1
vote
1
answer
48
views
Influence of a variable in composition of Boolean functions
Suppose $f$ and $g$ are Boolean functions without a constant term, and where every variable has the same influence. How to show every variable will have the same influence in $f \circ g$?
To me it ...
- 274k
1
vote
0
answers
44
views
Bloom filter creating different arrays from two input sets
Assume a bloom filter that is composed of $H = \{H_1, ..., H_k\}$ hash functions, and uniformly maps elements from an input set $X$ to an array $A$ of size $n$. Let $X_1, X_2$ (not same) be two input ...