Questions tagged [pr.probability]

Questions in probability theory

56 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
19
votes
0answers
497 views

Are monotone Boolean functions in P well-approximated by monotone polynomial-size circuits?

Question 1: Is it true that for every polynomial $p(n)$ and $\epsilon >0$ there is a polynomial $q(n)$ such that every monotone Boolean function on $n$ variables that can be expressed by a Boolean ...
16
votes
0answers
258 views

When does adding edges decrease the cover time of a graph?

When first learning about random walks on a graph $G$, one may have an intuitive feeling that adding edges to $G$ will decrease its cover time $C(G)$. However, this is not the case. The path graph $...
11
votes
0answers
409 views

Cheeger's inequality for directed graphs?

Cheeger's inequality can be used to relate the size of the worst cut in the graph to the eigenvalue gap of a simple random walk on that graph. I am wondering if it possible to extend this result to ...
11
votes
0answers
354 views

Is Bayesian updating computationally unfeasible?

Bayesian theory is a very popular theory of probabilities based upon a subjective framework of beliefs. However, subjects and beliefs have to be embodied, meaning to be feasible, it ought to be ...
9
votes
0answers
163 views

Fourth(?) moment method for minimum value

I would like to lower bound the quantity $\Pr[X\ge t, Y\ge t]=\Pr[\min(X,Y)\ge t]$ using the small moments of $X$, $Y$ and $XY$. In particular I am interested in the case where $E[X]=E[Y]=0$, but $E[X ...
9
votes
0answers
299 views

Beating Nonuniformity by Oracle Access

Informally, we say that a Turing machine $M(\cdot)$ approximates a function $f(\cdot)$ if their outputs on a series of inputs are indistinguishable. More formally, let $L$ be a language, $M(\cdot)$ ...
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
184 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
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
221 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
0answers
82 views

Is there a known notion of “stochastic dependent pair”?

I came upon this when thinking about the semantics of probabilistic programs. Say you have a generative model N ~ Poisson() for n = 1:N X[i] ~ Normal() Then the ...
5
votes
0answers
128 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
0answers
77 views

Strong data-processing inequality: bound $TV(T_{\#}P_0,T_{\#}P_1)$ if $\|T(x)-x\|_\infty \le \varepsilon;\forall x \in \mathbb R^p$

Disclaimer. I've moved this question from MO hoping that here is the right venue. Also, this is my first post on this channel, so please have some patience. So, Iet $X = (X,d)$ be a Polish space, ...
4
votes
0answers
233 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 ...
4
votes
0answers
208 views

The balls and bins model: bounding the marginal contributions in the m>>n regime

Consider the standard balls and bins process, where $m$ balls are thrown into $n$ bins, and consider the case where $m >> n$. Denote the load on bin $i$ by the RV $L_i$. Given a set $S \...
4
votes
0answers
147 views

Concentration Bounds for Dependent Rounding

Consider the following random process which is defined on $n$ numbers $0\leq x_1,\ldots,x_n\leq 1$: At each step, pick an arbitrary number, say $x_i$. Then randomly (and independently) change its ...
4
votes
0answers
68 views

Set-systems with some version of independence

Let $S \subset [N]$ be a fixed set of size $n$. Suppose $p$ is the probability that a random set $T$ of size $m$ intersects $S$ in $k$ or more points. That is, $$ \Pr_{\substack{T\subset [N]\\|T| = m}}...
4
votes
0answers
157 views

Adding noise to an assignment

Suppose I'm given a CNF formula with $m$ clauses (and $k$ literals in each clause), with a total of $n$ variables in the formula, where each variable is in at most $c$ clauses, along with a satisfying ...
3
votes
0answers
58 views

Probability of detecting small bias of a die in the low confidence regime / balls and bins

We are given a biased $m$-sided die: one of the sides has probability $\frac{1}{m} + \gamma$ and all the rest have probability $\frac{1}{m} - \frac{\gamma}{m-1}$ each. The goal is to figure out which ...
3
votes
0answers
201 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
73 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 $P_{...
3
votes
0answers
251 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. $\mathbb{...
3
votes
0answers
92 views

A sampling and learning question

Suppose there is an oracle that returns a number $b \in \mathbb{Z}_{n}$ whenever I press the button. We have $b = a + e$, where $a \in \mathbb{Z}_n$ is a fixed number and $e$ is sampled according to ...
3
votes
0answers
111 views

Sampling from a distribution with a given covariance matrix

Let $\bf X$ be a binary vector of $n$ (non-independent) random variables $X_1,\ldots, X_n$. Covariance of two random variables is defined as follows: $$\mathrm{cov}(X_i, X_j) = \mathrm{E}(X_i - \mu_i)...
2
votes
0answers
117 views

Can a tractable sequence distribution prefer satisfying to unsatisfying assignments?

Let $p(x)$ be a Boolean circuit on $n$ bits $x \in \{0,1\}^n$. Consider a program that computes a probability distribution over all sequences $x$, autoregressively factored as $$\pi(x | p) = \prod_{0 ...
2
votes
0answers
45 views

Is there a complete and finite axiom scheme for conditional independence? (Graphoids)

Note: This is a better-written version of an unanswered question asked before on MathOverflow. Question: Is there a complete and finite axiom scheme for conditional probability? If so, is there a ...
2
votes
0answers
68 views

Concentration Bounds for Thompson sampling

This paper gives concentration results around the mean of the regret for variants of UCB algorithm in multi-armed stochastic bandits. However, I could not find any similar results for Thompson ...
2
votes
0answers
147 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 ...
2
votes
0answers
111 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 ...
2
votes
0answers
130 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 $\mathcal{Y}$...
2
votes
0answers
224 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
122 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 ...
2
votes
0answers
92 views

Convergence of iterated stochastic matrices

(This question has been unsuccessfully asked on mathoverflow: https://mathoverflow.net/questions/161728/convergence-of-iterated-stochastic-matrices) It is well-known that for a stochastic aperiodic ...
2
votes
1answer
92 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
0answers
92 views

Weighted circular balls into bins

I would like to ask you for a help about modified balls into bins problem. Consider $n$ weighted balls such that each ball has a weight $w_i$ that is at most $W$. Furthermore, each of $m$ bins has a ...
1
vote
0answers
60 views

Mapping of entire balls using Locality Sensitive Hashing (LSH)

LSH functions are useful for approximate nearest neighbor search. They are usually defined, for distance metric $d$ and $c>1$ as follows: A family of hash functions is $(r, cr, p_1, p_2)$-LSH ...
1
vote
0answers
52 views

Problem dependent lower bound for stochastic bandits with full information

Suppose you have a $K$ armed stochastic bandit problem but with full information. There are $K$ arms with mean rewards $\mu_1,...,\mu_K$. At each step we have to select an arm, collect the reward from ...
1
vote
0answers
101 views

Percolation probabilities

I have a finite undirected graph with a probability $p_e$ given for each edge $e$. This gives a random graph by removing each edge e with probability $1-p_e$ independently of the others. I'm ...
1
vote
0answers
140 views

Maximal correlation vs correlation coefficient when one RV is Gaussian

Last week I asked a question on MOF (see here), but I got no reply. So I am asking my question here. Let a pair of random variables $(X,Y)$ be continuous random variables (i.e., they both have ...
1
vote
0answers
62 views

Computing the distribution from which this algorithm samples from

Assume we have a set of integers $X_0=\{x_1\ge x_2\ge\ldots\ge x_n\}$. Let $r\in(0,1]$ be a parameter and consider the ranking process: i=0 while ($X_i\ne\emptyset$) let $M = \max \{x\in X_i\}$ (...
1
vote
0answers
117 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 $\psi:\...
1
vote
0answers
775 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
56 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?
1
vote
0answers
167 views

Distribution of number of unique items in a sample

Suppose we're sampling a discrete random variable from a distribution f, n times. Is there a simple analytical formulation for the expected number of unique items we obtain, or for the distribution of ...
1
vote
0answers
243 views

application for the Kchinchine inequality in Computer Science

The classical Kchinchine inequality states that for vector $a=(a_1, \ldots, a_{2m})\in R^{2m}$, for $p\geq 2$, and for independent Rademacher random variables $r_1, \ldots, r_{2m}$, one has $$ E(|\...
0
votes
0answers
34 views

Expected value in case of Langevin dynamics

Let $U(\beta) = \exp(-f(\beta))$ where $f$ is $m$ strongly convex and $L$ Lipschitz smooth. I am trying to find an upper bound on $E[\|\beta_t \|^2]$ where $\beta_t \in \mathcal{R}^p$ is defined below ...