Questions in probability theory

learn more… | top users | synonyms

2
votes
0answers
23 views

High-Probability bounds for Stochastic multi-armed Bandit Problems

This paper gives some high probability results for UCB algorithm of the form, \begin{align} \mathbb{P}(R_{n} > r_0.x) \leq O(n^{-2\rho x + 1} + x^{-2 \rho + 1} ) \end{align} where $\rho$ is a ...
0
votes
0answers
28 views

MRF vs CRF dependencies

If Markov random fields (MRF) model explicit short range dependence between features and implicit long range dependencies (knock-off effect), can we say that a Conditional random field (CRF) models ...
0
votes
0answers
20 views

On a Generalized Maximal Correlation

I posted this question in here last week, but did not get any response. Given a pair of random variables $(X,Y)$ over a product space $\mathcal{X}\times \mathcal{Y}$, the maximal correlation ...
4
votes
3answers
107 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 ...
4
votes
1answer
146 views

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

This question was previously posted at http://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
258 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)}$$
0
votes
1answer
49 views

Bounding Rademacher Averages, with and without chaining

One can bound the Rademacher average $R_n(A)$ of a finite set of vectors $A\subseteq\{0,1\}^n$ using Massart's Finite Lemma: $$ R_n(A)\le \max_{a\in A}\|a\|\frac{\sqrt{2\ln|A|}}{n} $$ where ...
0
votes
0answers
33 views

Establishing causality under conditions of certainty

I'm currently reading "Causality: Models, Reasoning, and Inference" by Judea Pearl. Early on, he states that the development assumes that there are no certain entailments, no 1 or 0 probabilities -- ...
2
votes
0answers
80 views

On a possible probabilistic log-rank conjecture

The communication matrix of a function $f$ is a $2^{n}\times 2^{n}$ matrix $M_f$ where the indices of the rows (columns) correspond to the inputs of Alice (Bob), and each entry $M_f (a,b)$ is the ...
1
vote
0answers
24 views

An upper bound for chi-square divergence in terms of KL divergence for general alphabets

In my research I need an upper bound for chi-square divergence in terms KL divergence which works for general alphabets. To make this precise, note that for two probability measures $P$ and $Q$ ...
0
votes
0answers
84 views

Orlicz Norm and a result on expectation

I am reading a paper which is mainly about Dobrushin's contraction coefficient and its generalization. In page 27, the following is defined: Consider an arbitrary, non-negative, convex function ...
3
votes
0answers
47 views

Probabilistic sorting given pairwise comparison probability

Let $X = \{x_1, \dots, x_n\}$ be a set, and $f:[1..n]^2 \to [0, 1]$ be a function, such that $$f(i, j) \cdot f(j, k) \le f(i, k)$$ For all $1 \le i, j, k \le n$. Does there exist a randomized ...
3
votes
0answers
66 views

One kind of dependence relation between a pair of random variables

I have been working on privacy and come across a neat problem. Suppose two random variables $X$ and $Y$, over finite alphabets $\mathcal{X}$ and $\mathcal{Y}$, are given with joint distribution ...
10
votes
3answers
323 views

Is there any known CCC closed under a probabilistic powerdomain operation?

Equivalently, is there a known denotational semantics for probabilistic higher-order functional programming languages? Specifically, is there a domain model of pure untyped $\lambda$-calculus extended ...
2
votes
0answers
104 views

Strong Dependence

I asked this question on MO, but no answer. I don't know if this definition has been already given. Suppose $X$ and $Y$ are two random variables over finite alphabets $\mathcal{X}$ and ...
6
votes
0answers
83 views

What are bounded-treewidth circuits good for?

One can talk of the treewidth of a Boolean circuit, defining it as the treewidth of the "moralized" graph on wires (vertices) obtained as follows: connect wires $a$ and $b$ whenever $b$ is the output ...
13
votes
2answers
309 views

What is the expected depth of a randomly generated tree?

I thought about this problem a long time ago, but have no ideas about it. The generating algorithm is as follows. We assume there are $n$ discrete nodes numbered from $0$ to $n - 1$. Then for each ...
0
votes
1answer
67 views

References to learn more about graph laplacian.

I have vaguely heard of this connection between random matrix theory and graphs (the spectral gap of their laplacians) on compact Riemann surfaces. Can someone give a pedagogic reference which ...
5
votes
0answers
101 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 ...
3
votes
0answers
90 views

Probability distributions and computational complexity

Some probability distributions are easier to work with than others. Consider the following two problems. Given a number $n$, return $i$ with $0 \leq i < n$ with uniform probability, i.e. ...
0
votes
1answer
172 views

Proving properties of Random Graphs

I am asking the question on a slightly abstract level and it may depend on the specifics but it would be great to have related references or ideas. Consider the random graph model $G_{n,p}$ where its ...
1
vote
1answer
54 views

Subspace-evasive set performance in the random case

A subspace evasive set is defined as a large subset of a vector space which has small intersection with any $k$ dimensional affine space. That is, it "evades" all affine subspaces of small enough ...
7
votes
2answers
229 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 ...
21
votes
1answer
555 views

A flowchart for concentration bounds

When I teach tail bounds, I use the usual progression: If your r.v is positive, you can apply Markov's inequality If you have independence and also bounded variance, you can apply Chebyshev's ...
0
votes
1answer
239 views

Calculate Huffman code length having probability?

Having an alphabet made of 1024 symbols, we know that the rarest symbol has a probability of occurrence equal to 10^(-6). Now we want to code all the symbols with Huffman Coding. How many bits will ...
0
votes
2answers
129 views

Determining the distribution of results of a simple algorithm

Setting Consider repeating the following process on the numbers $N=\{1, 2, 3, \ldots, n\}$: Pick an integer $k \in N$, uniformly at random. Pick a subset of $k$ elements from $N$, uniformly at ...
2
votes
1answer
74 views

Sufficient Statistics of $X$ from $Y$

I am reading the paper New Monotone and Lower Bounds in Unconditional Two Party Computation by Wolf and Wullschleger. In Definition 2 on the third page, they define $f(x):=P_{Y|X}(\cdot|x)$ and they ...
4
votes
1answer
67 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 ...
1
vote
0answers
146 views

Time-inhomogeneous Markov Chains

I'm trying to find out what is known about time-inhomogeneous ergodic Markov Chains where the transition matrix can vary over time. All textbooks and lecture notes I could find initially introduce ...
1
vote
0answers
31 views

randomness extraction of real valued sequences of numbers

I have a sequence of numbers $x_1, x_2, \dots, x_n, \dots \in \mathbb{R}$ I would like to extract fair bits from that sequence. My first thought was to use the Von Neumann extractor. For a ...
1
vote
1answer
56 views

Policy Adjustment in Markov Decision Process

I was using MDP on my work to make optimal decision. I used discrete time, finite state MDP. I assumed that I will have an initial parameters, like the Reward/Cost, state transition probabilities and ...
6
votes
2answers
528 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}$. ...
1
vote
0answers
177 views

What is the optimal strategy for this 2 player game?

Let some finite array of integers is given initially. There is a number k which is initially '0'. In a move, a player will select a number from the array arr[i] and change k to gcd(k,arr[i]). Also, ...
2
votes
0answers
113 views

How to find a merge tree for a set of words?

Consider a set $S \subseteq \Sigma^n$ where $\Sigma$ is a finite alphabet and $p : \Sigma \rightarrow [0,1]$ is a probability function. Let $T$ be a tree leaf-labeled by the elements of $S$. Consider ...
8
votes
1answer
106 views

$k$-wise independent probability spaces

I have been having a great deal of difficulty finding a reference that gives simple and straightforward explanation of the following: Suppose we have $n$ random variables $Y_1, \dots, Y_n$, each of ...
2
votes
0answers
65 views

Convergence of iterated stochastic matrices

(This question has been unsuccessfully asked on mathoverflow: http://mathoverflow.net/questions/161728/convergence-of-iterated-stochastic-matrices) It is well-known that for a stochastic aperiodic ...
5
votes
2answers
210 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}$, ...
6
votes
0answers
63 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
1answer
148 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 ...
1
vote
0answers
33 views

What is entropy of a variable described by Knightian uncertainty?

Given a discrete variable whose value is characterized by Knightian uncertainty, that is, belief and plausibility, as in Dempster-Shafer theory, what is its entropy?
3
votes
3answers
334 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 ...
0
votes
1answer
68 views

Multiple independent random number streams

Having multiple streams of pseudo-random numbers known to be independent and with a uniform distribution I want to do Monte Carlo simulations in parallel. In other words, one thread will have a ...
5
votes
2answers
133 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$, ...
-3
votes
1answer
63 views

Why is the zero value ignored while deriving a ranking function for query terms in Probabilistic IR?

Take for instance equation 67 and 68 from this chapter: the value of $P(q|R=1,q)$ can become zero if the term is not present in the document, and as all probabilities are multiplied, the ...
1
vote
1answer
46 views

A theorem regarding statistically-hiding commitment schemes

Let $C_n$ be a non-interactive statistically-hiding commitment scheme, able to commit to an $n$-bit string. To commit to $m \in \{0,1\}^n$, the sender picks a random $r$ (of proper length), and sends ...
5
votes
2answers
187 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 ...
6
votes
1answer
190 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 ...
4
votes
0answers
136 views

Sums of products of bernoulli random variables

Let $x_1 \ldots x_a,y_1 \ldots y_b$ be independent random variables taking values +1 or -1. Consider the sum $$S = \sum_{i,j} x_iy_j.$$ I wish to upper bound the probability $P(|S| > t)$. The ...
7
votes
1answer
695 views

Sum of Independent Exponential Random Variables

Can we prove a sharp concentration result on the sum of independent exponential random variables, i.e. Let $X_1, \ldots X_r$ be independent random variables such that $Pr(X_i < x) = 1 - ...
5
votes
0answers
123 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 ...