Questions tagged [probability-theory]
Questions about the branch of mathematics concerned with modelling and analysing random phenomena.
468
questions
1
vote
0
answers
6
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
2
votes
1
answer
93
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 ...
- 23
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 ...
user157955
0
votes
0
answers
12
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
0
votes
0
answers
20
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
48
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
1
vote
1
answer
100
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 ...
- 11
3
votes
1
answer
71
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 $...
1
vote
1
answer
34
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 ...
- 183
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
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 ...
1
vote
2
answers
46
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, ...
- 13
0
votes
0
answers
33
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
3
votes
0
answers
47
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 ...
- 7,708
2
votes
1
answer
82
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 ...
- 73
3
votes
1
answer
678
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 ...
- 153
2
votes
0
answers
35
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
0
votes
0
answers
20
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 \...
3
votes
2
answers
88
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 ...
0
votes
1
answer
26
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 &...
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$, ...
- 113
1
vote
1
answer
96
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 ...
- 23
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)\...
- 313
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 ...
0
votes
0
answers
19
views
Probability Estimation with Chernoff Bound
Let's say there is an unfair coin with $P[head]=p$. We do not now $p$ but we know that $p \geq a$ for a known $a$. After $n$ trials we get $bn$ heads. Now, we want to estimate $p$ so that
$P[|p-b|\...
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 ...
1
vote
1
answer
32
views
Distribution maximizing ratio of expected maximum over the mean
I’m looking for a distribution that is non-negative, or has good tail bounds (so non-negative with high probability) and maximizes the ratio between the expected maximum of $n$ iid samples and the ...
- 13
2
votes
1
answer
52
views
Question about what exponentially small probability of success means in randomized algorithms
I am reading the book Randomized Algorithms By Motwani and Raghavan, and one of their exercises gives a modification of Karger's Min-Cut algorithm(Both is Monte Carlo) which picks two vertices and ...
- 169
1
vote
1
answer
45
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 ...
- 123
1
vote
1
answer
23
views
Distance bound for convex combination of inputs
Let $f$ be a function of 2 variables. Consider $f\colon X \times Y \rightarrow Z$.
Let $P_i$ (for $i=1,\ldots,n$) be $n$ probability distributions on $X$, and let $Q$ be a distribution on $Z$.
We ...
- 313
0
votes
1
answer
189
views
how many bits should I expect to flip, if I flip each bit with probability 1/n?
I am trying to work out some analysis for an algorithm I am trying to write, one step of what I am doing require knowing the answer to the above question.
I know it might sound a bit simple, but I am ...
- 310
1
vote
0
answers
35
views
Hashing for dot products
I've come across this problem that uses hashing to compute dot products (for non-negative vectors).
Suppose we are in $d$-dimensional space and $M$ will be our target for our hash. That is we have a ...
- 21
0
votes
1
answer
48
views
What is conditional probability?
I've been looking online and through a couple youtube videos but I cannot understand how exactly conditional entropy is being applied here. From what I'm understanding is that p(Y=1 | X=1) is 0 ...
- 11
1
vote
1
answer
23
views
Observable Markov Model: Expected number of observations
I have a question that asks me "What is the expected number of observations in a state?" with the note:
$$\sum^{\infty}_{d=1}d a^{d=1} = \frac{1}{(a-1)^2}\text{ when } |a| < 1$$
Prior to ...
- 121
0
votes
0
answers
12
views
Algorithmic Complexity of Enqueue and Dequeue of a Special Queue [duplicate]
The Canteen Queue Problem: There is a common canteen for $K$ hostels. Each hostel (co-ed) has some $N_1, N_2,...,N_K$ students. These students line up to pick up their trays in the common canteen, in ...
1
vote
0
answers
56
views
Most Likely Number of Winners - Dynamic Programming
You are given a team's win probability for each game on their schedule in the form P[1..n] where P[i] is the likelihood they win game i. Give a dynamic programming algorithm that returns the most ...
- 11
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 ...
2
votes
1
answer
100
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$. ...
- 1,042
2
votes
0
answers
57
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 ...
- 21
0
votes
1
answer
87
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 -...
- 101
2
votes
0
answers
70
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 ...
- 19
0
votes
1
answer
319
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
1
vote
0
answers
64
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 ...
1
vote
1
answer
31
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 ...
- 699
2
votes
1
answer
125
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 ...
- 155
1
vote
0
answers
13
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 ...
- 502
2
votes
1
answer
215
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 ...
- 303
2
votes
2
answers
220
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$...
- 593
3
votes
2
answers
201
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
...
- 223