Questions tagged [pr.probability]

Questions in probability theory

Filter by
Sorted by
Tagged with
8
votes
1answer
179 views

Looking for a reference: equivalence of (semi)computable (semi)measures and PTMs

I'm working with computable probability distributions over all finite strings. These are usually formalized as the space of all semicomputable semimeasures. Informally: a probability distribution is ...
7
votes
3answers
1k views

Order of drawing colored balls from a bag

We're looking for an upper bound on (or a method to compute) probabilities of the following type: Suppose I put 12 yellow balls, 18 red balls, 7 white balls, and 2 green balls in a bag. Then I start ...
7
votes
2answers
269 views

What is the connection between moments of Gaussians and perfect matchings of graphs?

Today, I heard the following statement in a talk: The 4th moment of a $1$-dimensional Gaussian distribution with mean $0$ and variance $1$ is the same as the number of perfect matchings of a ...
7
votes
1answer
150 views

Upper bound on Chaitin's constant for lambda calculus and SKI combinatory logic

I'd like to have proof that Chaitin's constant for lambda calculus and/or SKI combinatory logic is pretty small. I've found some approximations (accurate to about 63 binary digits) for truing machines ...
7
votes
2answers
227 views

Is uniform convergence faster for low-entropy distributions?

Let $\mathcal D$ be a probability distribution on $\{0,1\}^d$. Let $X_1, \cdots, X_n \in \{0,1\}^d$ be i.i.d. samples from $\mathcal D$. Let $\mu \in [0,1]^d$ be the mean of $\mathcal D$ and let $\...
7
votes
1answer
701 views

Reservoir sampling of distinct values

I'm faced with a situation where I need to get m samples from a data stream (without replacement). Only one pass through the data is possible. In my case, the stream contains many duplicate values, ...
7
votes
1answer
347 views

expected number of sets generated by greedy set cover ?

I see most of the analysis for the greedy set cover analyses the approximation ratio. However, assume that each element in $T$ belong with a constant probability to one of the sets of $S$ (where $S = \...
7
votes
1answer
136 views

Random Deterministic Automata

I am familiar with the term of random graphs, such as $G(n,p)$- a distribution over simple undirected graphs with $n$ vertices, where each edge appears in a graph w.p. $p$. That is, each graph $G=(V,E)...
7
votes
1answer
317 views

Minimum Spanning tree on a complete “random” graph

Consider a complete undirected graph with $n$ vertices, $K_n$. Let weight of an edge between vertices $i\; \& \;j$ be a random variable $E_{ij}$. Let $E_{ij} \sim exp(\lambda)$, where $exp(\lambda)...
7
votes
2answers
265 views

Maximizing the number of heads in $N$ tosses by choosing which coin to toss

Assume you have two coins $A,B$ with biases $P_A,P_B$ respectively. We would like to make $N$ coin tosses and get the maximal number of heads possible. Unfortunately, we know $P_B$, but $P_A$ is ...
7
votes
0answers
126 views

Convergence speed in Lévy’s continuity theorem

I suppose the answer to my question follows from the proof of the Lévy’s continuity theorem, but probably one could suggest me a direct reference to the corresponding answer. The question is as ...
7
votes
0answers
183 views

Testing the degree of a vertex

Let's say we have a graph $G$ with $n$ vertices. Given $\epsilon>0$ and a specific vertex $v$, consider the problem of deciding whether $\mathrm{deg}(v) < \frac{\epsilon}{3}n$ or $\mathrm{deg}(v)...
6
votes
4answers
568 views

Small $\epsilon$-nets for points and half-planes without VC dimension

I have recently learned the proof of Haussler and Welzl of the following theorem. Theorem. Suppose we have a set system $\mathcal{F} \subseteq 2^X$, where $X$ is a finite set. Suppose $\mathcal{F}$ ...
6
votes
3answers
1k views

Computational complexity of random sampling

I am using some randomized algorithms (particle filters) and I would like to know what is the computational complexity of obtaining one random sample of a continuous distribution (for instance from a ...
6
votes
2answers
501 views

Reference for the number of samples needed to distinguish two probability distributions

I am looking for a reference (and/or a full proof) for this statement: $O(1/\epsilon^2)$ samples suffice to distinguish any two probability distributions with variation distance $\epsilon$. I ...
6
votes
1answer
231 views

Graph that maximizes minimum hitting time?

Let $G$ be some connected bidirectional (or undirected) graph. We define a random walk as a walk that begins at a vertex chosen uniformly at random, and at each step proceeds to one of its current ...
6
votes
1answer
260 views

Expected Kolmogorov complexity under Kolmogorov complexity distribution

If $K(w)$ is the Kolmogorov complexity of a string $w$, where programs are prefix-encoded so $\sum_{w} 2^{-K(w)} \leq 1$, what is $$\lim_{n\to\infty} \frac{\sum_{|w|=n}2^{-K(w)} K(w)}{\sum_{|w|=n} 2^{...
6
votes
2answers
516 views

The probability by which Bloom filters preserves the order relation given a similarity measure on sets

A Bloom filter is a data structure for probabilistic set-membership. When adding an item to the set, $k$ bits (whose indices are determined by $k$ different hash functions) are set to 1. To check if ...
6
votes
1answer
211 views

Big-O bounds on the k-th largest element of iid Gaussians

I'm interested in the following problem. Let $X_1, \dots, X_n$ be iid samples with a $N(0,1)$ distribution. Let $X_{[k]}$ be the $k$-th largest element of $\{X_1, \dots, X_n\}$, so e.g. $X_{[1]} = \...
6
votes
2answers
277 views

Infinite process balls in bins problem

Given $n$ balls and $m$ bins, let us consider an infinite process, where in each time slot we throw a ball at a random bin. When all $n$ balls are thrown, we take the balls from the bin with the ...
6
votes
1answer
738 views

Independent set size in triangle-free graphs

Consider a triangle-free graph $G$. The notations used are: $\alpha(G) = $ the size of a largest independent set of $G$. $n(G) = $ the number of vertices in $G$. Theorem (Ajtai et al.): For a ...
6
votes
1answer
127 views

Directed graph with bounded in-deg can be partitioned in a balanced way

I want to prove that for all $n$, there exists a constant $c(n)$ such that if $G=(V,E)$ is a directed graph with in-degree bounded by $n$, it is possible to partition the set of vertices $V$ into two ...
6
votes
1answer
157 views

Are bins with more black than white balls negatively 1-correlated?

Suppose we throw $m_b$ black balls and $m_w$ white balls independently and uniformly at random in $n$ bins. Let $\left\{ B_i \right\}_{i \in \left\{ 1,\ldots,n \right\}}$, $\left\{ W_i \right\}_{i \...
6
votes
1answer
344 views

Understanding proof of Theorem 3.3 in Karp's “Probabilistic Recurrence Relations”

Background: In Karp's paper on Probabilistic Recurrence Relations, he develops tail-bounds for random variables satisfying the following recurrence: $$ T(x) = a(x) + T(h(x)) $$ where $T(x)$ is a ...
6
votes
2answers
3k views

What is the probability of a virus spreading through a network given a virus source node?

Model: Consider an infinite undirected connected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$. At time $t=0$, a given virus node $s\in\mathcal{V}$ starts infecting the network $\mathcal{G}$. ...
6
votes
1answer
250 views

correlation in an almost independent set of random variables

Suppose I have a set of $n$ binary random variables $X_1, \ldots, X_n$ that sit on a line, and assume that $\Pr(X_i=0)=\delta$ for all $i$. In addition, assume that any two subsets of variables that ...
6
votes
0answers
72 views

Fast convergence of a contagion process in special graphs

The process: Given is a clique $C_n$ of size $n$. Consider the following synchronous process, also known as the (synchronous) voter model (e.g., Even-Dar and Shapira): Define an indicator variable $...
6
votes
0answers
181 views

Squares of random binary matrices

Are there results/techniques pertaining to the analysis of squares of random matrices ? More specifically, let $A$ be an $n\times n$ matrix such that each entry is $1$ or $-1$ independently and with ...
6
votes
0answers
188 views

Tree search guided by a probabilistic oracle

I'm trying to find a solution for the following problem. I have a tree $T$ of branching factor $b$ and depth $d$. For the moment, I only care about the case where I restrict $b=2$, but I would be ...
6
votes
1answer
217 views

A random walk that moves to less-visited nodes

Consider a random walk on an undirected graph that keeps track of how many times it has visited every node. At each step, it moves to the node among its neighbors which has been visited the least ...
5
votes
2answers
1k views

Multiplication of normal distributions

Suppose X_1, ..., X_k are iid standard Gaussian variables, for some k > 1. Then, what is the distribution of X := X_1 * ... * X_k ? Can it be approximated by a Gaussian, maybe for large k ?
5
votes
3answers
897 views

The use of crossovers in Genetic Algorithm

My questions concern the use of crossovers in genetic algorithms. The three basic ingredients of genetic algorithms are: selection mutation crossover If we think of genetic algorithm acting on ...
5
votes
2answers
168 views

Concentration inequality for function of independent Bernoulli r.v.'s (related to random graph)

Consider a random undirected graph on a set of $n$ nodes, say $\{1,2,\ldots,n\}$, such that the probability of edge between nodes $i$ and $j$ is $p_{ij}$ (we may assume $p_{ij}=o(1)$ for all $i,j$, i....
5
votes
2answers
120 views

Statistical Distance Growth Given K Independent Copies

Let $X$ and $Y$ be distributions with statistical distance (total variation distance) at most $d$. What is the best upper bound you can give on the statistical distance between $k$ independent copies ...
5
votes
2answers
178 views

Heterogeneous Hoeffding/McDiarmid

Hoeffding's inequality for independent random variables $a_i\le X_i\le b_i$ states that their sum has sub-Gaussian tails, decaying as $\exp(-2t/\sum_i (b_i-a_i)^2)$. Question: Are there any ...
5
votes
3answers
256 views

Probability for an element to appear in at least one set

Say that we have $k$ sets, each with cardinality $N$, where the elements in each set are taken at random from $M \ge N$ possible ones. The elements in each set are known to be distinct. What is the ...
5
votes
2answers
167 views

Behaviour of Labelled Markov Processes

Labelled Markov Processes (LMP) seem to be a generalization of Probabilistic Automata (PA) studied by Segala to the case of the general state space. Namely, any LMP is given by a be a finite set of ...
5
votes
1answer
250 views

Random walk returning probability

Consider a two-dimensional random walk, but this time the probabilities are not $1/4$, but some values $p_1, p_2, p_3, p_4$ with $\sum_{i=1}^4 p_i=1$. For example, from $(0,0)$, it goes to $(1,0)$ ...
5
votes
1answer
168 views

Complexity of finding the most likely edge

Consider a connected, unweighted, undirected graph $G$. Let $m$ be the number of edges and $n$ be the number of nodes. Now consider the following random process. First sample a uniformly random ...
5
votes
1answer
108 views

Majority function stability under deletion and addition of entries

It is well known that the majority function is stable under random flipping of bits. That is, if $v$ is a random binary vector, and then we re-sample each bit of $v$ with probability $\delta$ and get $...
5
votes
2answers
847 views

Subgraph of G whose maximum degree and minimum degree are of the same order

Consider a graph $G$ with max degree $\Delta_G$, min degree $\delta_G$ and average degree $d_G$. Is it possible to obtain a subgraph of $G$, say $G'$, such that $\Delta_{G'} = c_1d_{G}$, $\delta_{G'...
5
votes
1answer
257 views

About a random walk with constant spectral gap

The existence of a graph with certain strange-looking properties will imply a counterexample to something I am playing with. I'm stuck on figuring out whether such a graph can exist and so I thought I'...
5
votes
0answers
125 views

Spectrum of absorbing random walk for regular graphs

I have a symmetric Markov chain given by the matrix $P$. Let $M$ be a set of special states of the chain (called marked states, they correspond to solutions to some problem). We can write $P$ as \...
5
votes
0answers
136 views

Sampling small separators

Is there a tractable way to define an approximate distribution over small vertex separators of the graph? I'm looking for something along the lines of [Bayati,2008], a way to turn a single "this is a ...
5
votes
0answers
309 views

Geometric / Visual explanation that the average height of a random binary tree of given size $n$ is asymptotically $2\sqrt{\pi n}$

I just finished reading the proof that the average height of a random binary of given size $n$ is asymptotically $2\sqrt{\pi n}$. I'm now searching for an intuitive, or geometric, or visual proof of ...
4
votes
3answers
211 views

Approximating distributions from samples

One claim I find in many papers about identity testing, and closeness testing is that any distribution over $[n]$ can be approximated to within $\ell_1$ distance $\epsilon$ in $O\left(\frac{n}{\...
4
votes
1answer
165 views

Why is differential privacy defined over the exponential function?

For adjacent database $D,D'$, a randomized algorithm $A$ is $\varepsilon$-differential private when the following satisfies $$\frac{\Pr(A(D) \in S)}{\Pr(A(D') \in S)} \leq e^\varepsilon,$$ where $S$ ...
4
votes
1answer
603 views

Example of pairwise independent random process with expected max load $\sqrt{n}$

This question was previously posted at https://math.stackexchange.com/questions/1220292/example-of-pairwise-independent-random-process-with-expected-max-load-sqrtn where it has no answers. I now ...
4
votes
1answer
851 views

Upper and lower bound of binomial summation

For $n>1$ and $~0<p \leq 1$, can we upper and lower bound the following binomial series in terms of $n$ and $p$ $$\Sigma_{i=\lceil p n \rceil}^n {n \choose i} (p )^i(1-p)^{(n-i)}$$
4
votes
1answer
274 views

Expected Halt Time

I'm sorry if the following question seems too obvious. In fact, I oversimplified a much harder problem to this one. Consider the following algorithm, where $0 < p \le 1$ is a constant: ...