# 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
Filter by
Sorted by
Tagged with
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$ ...
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 ...
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$. ...
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 ...
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 ...
475 views

43 views

1 vote
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 (...
1 vote
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
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 ...
1 vote
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 ...
1 vote
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
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 ...
1 vote
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 ...
1 vote
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: ...
1 vote
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 ...
1 vote
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 ...
1 vote
689 views

1 vote
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 ...
1 vote
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 ...