Questions tagged [probability-theory]
Questions about the branch of mathematics concerned with modelling and analysing random phenomena.
101
questions with no upvoted or accepted answers
13
votes
0
answers
425
views
Choosing a subset of binary variables to maximize the sum of the highest $K$
Consider the following problem:
Input:
integers $n > m > k$;
$n$ numbers $0 \leq p_1, \ldots, p_n \leq 1$;
$n$ numbers $r_1, \ldots, r_n$ where ($r_i \geq 0$).
Let $X_1,\dots,X_n$ be $n$ ...
- 231
11
votes
0
answers
1k
views
Alternative to Bloom filter for extreme parameters
A Bloom filter is a space-efficient probabilistic data structure to perform membership-tests on a set (see Wikipedia's page for a definition; I use the same notations below).
I am interested in a ...
- 391
8
votes
0
answers
196
views
Compute the expected size of an approximation of vertex cover
Consider the following randomized approximation algorithm of vertex cover:
Input: A graph G = (V, E).
Output: A set $C_G \subseteq V$ a vertex cover of $G$.
The algorithm:
Set $C_G := \emptyset$.
...
- 4,358
7
votes
0
answers
258
views
Correctness of a greedy Algorithm on Knockout Tournaments
You are given a function $\operatorname{rk}:\{1\dots 2^k\}\rightarrow \mathbb{N^+}$ representing the ranks of the players $1\dots2^k$ in a participating in a tournament. The tournament evolves in a ...
- 101
4
votes
0
answers
67
views
Peculiar MCMC sampling problem
I have two random variables, X and Y, and Y is a positive real number. I can sample from $p(y|x)$, but I need to sample from $p(x)$, which I know to be proportional to $\frac 1 {E[y|x]}$. I could ...
- 41
4
votes
0
answers
475
views
Mean and variance of number of buckets of length $i$ in hashing with chaining
Consider a hash table with $m$ buckets, with chaining as collision resolution policy. Given the set $S$ that will be stored in the hash table, let $X_i$ be the number of buckets whose chain length is $...
- 358
4
votes
0
answers
63
views
Infer probabilities, for concatenation of words
Fix an alphabet $\Sigma$, and a set of words, $W = \{w_1,\dots,w_n\} \subseteq \Sigma^*$.
I have a randomized model that works like this: Alice generates a random sequence of words, using some ...
D.W.♦
- 152k
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 ...
- 41
4
votes
0
answers
67
views
Adversarial bin packing
An adversary gives you a set of items whose total size is $x$ (he gets to choose how $x$ is distributed. e.g. there may be $k-1$ items of size $\frac{x}{k}$ and 2 items of size $\frac{x}{2k}$).
The ...
- 41
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 ...
- 8,742
3
votes
0
answers
140
views
Node depth in randomly built binary search tree
It can be proved that randomly built binary search trees of size $n$ are of depth $O(\log n)$ and it is clear that level $k$ has at most $2^{k}$ nodes (root's level is 0).
I have an algorithm that ...
- 131
3
votes
0
answers
92
views
Probability of a double cycle in cuckoo graph
I have read Chater 17. Balanced Allocations and
Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got ...
- 285
3
votes
0
answers
93
views
Output process of a G/M/1 queue
What is the output distribution of a GI/M/1 (general input process and exponential service times) queue.
The GI/M/1 is according to Kendall's notation: arrivals are independent but we do not know the ...
- 129
3
votes
0
answers
70
views
Should Expectation Maximization take into account the Naive Bayes' independence assumption?
Should the independence assumption on which the Naive Bayes (NB) classifier is based, be taken into account when applying Expectation Maximization(EM) to infer missing values?
The Naive Bayes ...
- 131
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$. ...
- 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
2
votes
0
answers
71
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
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 ...
- 155
2
votes
0
answers
108
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=...
- 453
2
votes
0
answers
43
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 \...
- 27
2
votes
0
answers
24
views
Algorithm to mapping given probabilities to empirical probabilities
Consider following problem statement:
You have given $n$ actions. You can perform any of them. Each action gives you success with some probability. The challenge is to perform given finite number of ...
- 225
2
votes
0
answers
48
views
Integer sampling with exponentially decreasing probability
Given a probability $p$ and an integer $N$, I would like to generate a sample $S$ of the population $P=\{0,1,...,N\}$ such that integer $m\in P$ is sampled with probability $p^m$.
It is trivial to do ...
- 119
2
votes
0
answers
82
views
In Universal Hashing- probability of poor performance is small and is the same for any set of keys of the same size
I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following claim:
Universal Hashing uses randomization.For the example of a compiler's symbol table, ...
- 1,042
2
votes
0
answers
186
views
How to estimate the number of elements inserted to a Bloom filter
A Bloom filter is a probabilistic data structure that allows encoding sets with false positives.
Parameterized by the number of bits $m$ in the array $A$ (initialized to zeros), and number of hash ...
- 141
2
votes
0
answers
62
views
Probability of colisson for classes of hash functions
I am going through some old exams in one of my courses, and I don't have access to solutions. I've found a problem which I am not sure how to tackle. I am not looking for the answer but some help/...
- 37
2
votes
0
answers
66
views
The No-Free-Lunch Theorem and K-NN consistency
In computational learning, The NFL theorem states that there is no universal learner. For every learning algorithm , there is a distribution that causes the learner to output a hypotesis with a large ...
- 21
2
votes
0
answers
135
views
Correctness of Karger's min-cut Algorithm
tl;dr in the analysis for Karger's min-cut, the probability of an edge being in the min-cut in the $j$th iteration, $\frac{k}{0.5k(n-j)}$, neglects the fact that all the edges between the two ...
- 151
2
votes
0
answers
120
views
What would be the probabilty of a randomly generated tree to be a Red-Black Tree
The question is not related to the homework
I was working on a homework, and the specification was to generate a random tree with n elements(n being in the thousands for the assignment) and asked me ...
- 171
2
votes
0
answers
66
views
Box labelling game
I have a box of stickers. It contains $n$ stickers. Each sticker is labelled with a different number from $\mathbb{Z}$.
I have infinite supply of boxes.
Box labelling game: I pick a random sticker ...
- 1,731
2
votes
0
answers
167
views
Universal lower semicomputable semimeasure and Coding Theorem
I'm following Li and Vitanyi's book "An introduction to Kolmogorov complexity and its applications" 3ed. I'll rewrite here the definitions I need for my question.
The authors define the reference ...
- 369
2
votes
0
answers
101
views
Optimal wagering to minimize expected time to reach a target payoff
Suppose for simplicity we start off with starting amount $S = 1$ and we wish to reach target amount $T$. To do this we sequentially wager a certain amount and then win that amount with probability $p$ ...
- 1,691
2
votes
0
answers
42
views
How to find number of occurences of specific distances in binary (search) trees?
I want to calculate the amount of tree structures that have a given maximal distance between two nodes given an amount n of nodes (or keys).
E.g. with ...
- 21
2
votes
0
answers
74
views
Which component sizes do we observe while randomly deconstructing a tree?
Suppose I have a connected graph with $n$ vertices and $n−1$ edges, that is in form of a tree. Now, I will add the number of vertices in the tree and uniformly randomly select a vertex. I break the ...
- 101
2
votes
0
answers
204
views
Exact Inference in Bayesian Networks
I'm doing some exam study and came across a question I'm not really sure on. Consider the Bayesian network below:
Let's denote "Disease" with $D$ and "Symptom" with $S$.
I want to find $P(D \mid S_A,...
- 21
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
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
0
answers
37
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
1
vote
0
answers
63
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
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 ...
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
1
vote
0
answers
36
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 ...
- 219
1
vote
0
answers
12
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:
...
- 11
1
vote
0
answers
33
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 ...
- 141
1
vote
0
answers
20
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 ...
- 183
1
vote
0
answers
689
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^\...
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,...
- 219
1
vote
0
answers
141
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 &...
- 860
1
vote
0
answers
104
views
Variance of chain length in hashtable
I have a hashtable with length $m$. Initially it's empty. Next, $n/2$ unique random numbers $\in [0, n]$ are added to it.
What would be variance of chain length when such $n/2$ numbers are being added ...
- 11
1
vote
0
answers
226
views
Channel coding and Error probability. Where are these probabilities from?
From where are the following probabilities?
We consider BSCε with ε = 0,1 and block code C = {c1, c2} with the code words c1 = 010 and c2 = 101. On the received word y we use the decoder D = {D1,D2} ...
- 51
1
vote
0
answers
93
views
Calculate probability in graphical model
I have the following graphical model, in which I wish to compute $p(Intelligence = 1|Letter = 1, SAT = 1)$
But I'm not sure how to rewrite $p(Intelligence = 1|Letter = 1, SAT = 1)$? I was told to ...
- 11