# Questions tagged [probability-theory]

Questions about the branch of mathematics concerned with modelling and analysing random phenomena.

95 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
394 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$ ...
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 ...
135 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$. ...
217 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 ...
77 views

### Understanding simulated annealing information theoretically

So I recently rediscovered simulated annealing though a path that others seem to be well aware of. I was aware of Metropolis-Hastings as a sampling algorithm that creates a Markov-Chain who's ...
64 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 ...
387 views

23 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 ...
38 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 ...
44 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, ...
58 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/...
38 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 ...
78 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 ...
115 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 ...
62 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 ...
148 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 ...
99 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$ ...
41 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 ...
73 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 ...
160 views

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 ...
14 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 ...
68 views

61 views

### Show that if $\mathcal{H}$ is PAC learnable in the standard one-oracle model, then $\mathcal{H}$ is PAC learnable in the two-oracle model

This is a question $9.1$ from Understanding Machine Learning Chapter 3. It goes like this: Consider a variant of the PAC model in which there are two example oracles: one that generates positive ...
102 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 ...
73 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 ...
203 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} ...
56 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 ...
46 views

### Decomposition of Mutual Information

I came across a book where the author uses the following property of mutual information: Let $X$,$Y$,$Z$ be arbitrary discrete random variables and let $W$ be an indicator random variable.  (1)\ \ ...
61 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 ...
I'm attempting a question related to Bloom filters: Our Bloom filter uses $3$ different independent hash functions $H_1, H_2, H_3$ that each take any string as input and each return an index into a ...
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$) ...