Questions tagged [pr.probability]
Questions in probability theory
1
vote
0answers
41 views
Are there any continuous-time stochastic processes in which transition probabilities are discontinuous functions over time? [closed]
In stochastic processes, like homogeneous Markov processes, Poisson processes, Queueing systems etc., the functions that represent (transition) probabilities are continuous over time. This is also ...
7
votes
2answers
184 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 $\...
2
votes
1answer
62 views
Empirical Rademacher averages versus Hoeffdings bound
Let $M$ be finite set with $n$ distinct elements. I want to probalistically approximate the relative counts $\frac{|P(Q)|}{|M|}$ of $Q \subseteq M$, where $P(Q) = |P \cap M|$.
An upper-bound for ...
2
votes
1answer
91 views
Sample Complexity for Order Statistics
I have a sample complexity question which seems fairly basic, but for which I'm having trouble finding a reference.
Let $F$ be an unknown distribution over $[0,1]$. Denote by $X_{k:n}$ the $k$th of $...
2
votes
1answer
101 views
A coupon collector type problem with changing probabilities
Suppose we are flipping coins starting at some time $t$. At time $t$ the probability we obtain heads is $\frac{1}{\sqrt{t}}$. If the coin lands tails, at time $t+1$ the probability of heads is now $\...
2
votes
1answer
111 views
Recovering a rank-one matrix from its eigendecomposition after randomized rounding
Let $A = xy^T$ be a rank-$1$ matrix, and suppose every entry of $A$ is in $[0,1]$. We can create a binary matrix $A_{\rm rounded}$ by setting
$$ [A_{\rm rounded}]_{ij} = \begin{cases} 1 & \mbox{ ...
4
votes
1answer
97 views
Probability of a $k$-path in a random graph
Assume that $G\in G(n,p)$; if $p=\frac{\ln n +\ln \ln n +c(n)}{n}$,
the following fact is well known:
\begin{eqnarray}
Pr [G\mbox{ has a Hamiltonian cycle}]=
\begin{cases}
1 & (c(n)\...
0
votes
0answers
26 views
Expected size of the min-cut, under edge perturbations
Suppose we have a graph $G(V, E)$.
Assume that the min-cut of this graph is given $C=(A/B)$ and denote the size of the cut with $|C|$.
Create a random modification of the graph:
Drop each ...
5
votes
1answer
121 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 ...
1
vote
1answer
79 views
Using a probability distribution in the fooling set technique for communication complexity
I'm reading through the communication complexity book of Kushilevitz and Nisan, and in the section about fooling sets I encountered this proposition:
Let $\mu$ be a probability distribution of $X\...
0
votes
0answers
75 views
A question on linear separability after random projection
Let $R \in \mathbb{R}^{n,d}$ be a random Gaussian matrix comprised of independent $\operatorname{N}(0,\frac{1}{n})$ entries, and let the data set $S = \{($ $\textbf{x}_i$ $\in \mathbb{R}^{d}, y_i \in ...
3
votes
1answer
121 views
Tighter Probability Bounds
Let $\mathcal{F}$ be a class of binary functions on a probability space $\Omega$. For $f \in \mathcal{F}$, let $P(f) =\mathbb{E}(f(Z))$ and $P_n(f) = \frac{1}{n} \sum_{i=1}^n f(Z_i)$ where $Z_i$'s are ...
-1
votes
1answer
145 views
Application of the inequality with expectations
Let $\Vert\cdot\Vert$ is a norm in $R^n$. Let $x_1,\dots,x_N$ non-independent Rademacher random variables random variables (variables which are uniform on $\{-1, 1\}$). . By $E$ we denote an ...
4
votes
1answer
135 views
Support size lower bound for $k$-wise uniform distribution
So I have this question which I can't seem to find a solution to:
Prove that if $X = (X_1, ... X_n)$ is $k$-wise uniform* and each $X_i$ is Boolean then $\left|\operatorname{Supp}(X)\right| \geq \...
2
votes
1answer
82 views
Other Uniform Bound
In theoretical machine learning, VC-dimension (VCD) and Rademacher average (RA) are two frequently used uniform bounds, providing better sample complexity than bounds such as Chernoff bound and ...
2
votes
0answers
39 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 ...
0
votes
1answer
69 views
Does this pairwise independent random process have expected max load $\sqrt{n}$?
This is an extension to the question about balls into bins: Example of pairwise independent random process with expected max load $\sqrt{n}$ . There the following question is asked and answered in ...
7
votes
1answer
125 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)...
4
votes
1answer
264 views
Janson-type inequality, limited dependence
So I am trying to figure out an upper bound on the probability of the following...
This is a question related to a problem I am working on (not for a class, just for fun)
Let $\Omega=\{X_{1},\dots,...
1
vote
0answers
31 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 ...
13
votes
1answer
643 views
What is the proof of this nonstandard version of Azuma's inequality?
In Appendix B of Boosting and Differential Privacy by Dwork et al., the authors state the following result without proof and refer to it as Azuma's inequality:
Let $C_1, \dots, C_k$ be real-valued ...
4
votes
2answers
197 views
Hardness of exact binomial tail bounds
Chernoff bounds, in their various forms, bound the tails of a Binomial$(n,p)$ random variable $B$. Define the function $F(n,p,t):=P(B>t)$. Naively, computing $F$ requires exponential (in $n$) time. ...
6
votes
1answer
184 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 ...
4
votes
1answer
208 views
Relation between variance and mutual information
Given two discrete random variables $X,Y$ such that $X,Y \in \mathbb{R}$ and $0 \leq X,Y \leq 1$, is it true that $$|\text{Cov}[X,Y] \leq \sqrt{\frac{1}{2} \text{I}[X,Y]}|. $$
This bound may be ...
6
votes
1answer
122 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 ...
9
votes
0answers
144 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 ...
4
votes
1answer
159 views
Lower bound on probability of getting two close points in a sample of $n$ points
Let $D\subseteq \mathbb{R}^k$. Assume that $Pr_{u,v\leftarrow U_D}[|u-v| <B]>p$ for some $B,p$, where $|u-v|$ is the L1 distance of the vectors.
$S\subseteq D$ is obtained by sampling $n$ ...
7
votes
2answers
237 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
2answers
257 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 ...
3
votes
3answers
161 views
Approaches for Theoretical Analysis of Estimates of Probability Distributions
Consider that you have a probability distribution p of some quantity X and you have obtained (via some algorithm) an estimate q of p according to some definition of closeness. Are there methods/papers ...
7
votes
1answer
307 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
1answer
231 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^{...
2
votes
1answer
156 views
Probability of random variable $X$ less than $max(Y_i)$
For $\lambda > \mu$, consider independent random variables (i) $X \sim Pois(\mu)$ and (ii) $Y_i \sim Pois(\lambda),\;i\in{1,2}$.
Question : Can we upper-bound the following?
$$\mathbb{P}\big(X\...
7
votes
1answer
278 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)...
9
votes
2answers
480 views
Statistical distance between uniform and biased coin
Let $U$ be the uniform distribution over $n$ bits, and let $D$ be the distribution over $n$ bits where the bits are independent and each bit is $1$ with probability $1/2-\epsilon$. Is it true that ...
1
vote
1answer
81 views
Issue with inequalities involving probablities
I'm reading this paper http://eccc.hpi-web.de/report/2016/044/download/, at page 7 you can see this equation:
$$ \sum_t \mathbb{E}_{w \in W} [|p_t - p_{t|w,w}|] = 2 \sum_t \mathbb{E}_{w \in W} [\max(...
8
votes
2answers
209 views
Can the “mutual independence” condition in the Lovász local lemma be weakened?
The Lovász local lemma, as stated in Corollary 5.1.2 here, is given as follows.
Lemma. Let $A_1, \ldots, A_k$ be events such that each $A_i$ has probability at most $p$ and such that each $A_i$ is ...
1
vote
1answer
105 views
The noise distribution on $F_2^n$: probability of landing in a subspace versus a coset
Let $V = F_2^n$ be the $n$-dimensional vector space over the field of two elements. The $\epsilon$-noise distribution on $V$, denoted $\mu_\epsilon$, is a probability distribution on $V$ for which ...
1
vote
0answers
95 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 ...
14
votes
1answer
372 views
Expected minimum influence of a random Boolean function $f\colon\{-1,1\}^n \to \{-1,1\}$
For a Boolean function $f\colon\{-1,1\}^n \to \{-1,1\}$, the influence of the $i$th variable is defined as
$$
\operatorname{Inf}_i[f] \stackrel{\rm def}{=} \Pr_{x\sim\{-1,1\}^n}[ f(x) \neq f(x^{\oplus ...
1
vote
0answers
99 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
1answer
103 views
Average Regret Bounds for Linear Stochastic Bandits
I am reading this paper on linear stochastic bandits :
http://papers.nips.cc/paper/4417-improved-algorithms-for-linear-stochastic-bandits.pdf
All the results are stated in a high-probability ...
8
votes
1answer
395 views
Exponential Concentration Inequality for Higher-order moments of Gaussian Random Variables
Let $X_1,\ldots, X_n$ be $n$ i.i.d. copies of Gaussian random variable $X \sim N(0, \sigma^2)$. It is known that
\begin{align}
\mathbb{P}\Bigl( \Bigl|\frac{1}{n}\sum_{j=1}^n X_j \Bigl| >t\Bigr) &...
6
votes
1answer
196 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 ...
16
votes
0answers
242 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 $...
4
votes
1answer
452 views
Orlicz norm of random variable and variance
In probability and statistics Orlicz norms are frequently used in concentration inequalities. For example, for Bernstein's inequality, we have versions for sub-exponential random variables using $\...
22
votes
1answer
374 views
Which graph parameters are NOT concentrated on random graphs?
It is well known that many important graph parameters show (strong) concentration on random graphs, at least in some range of the edge probability. Some typical examples are the chromatic number, ...
2
votes
1answer
180 views
Squared Hellinger distance between Binomial(n,p) and Binomial(n+1,p)
I came across a claim in a paper Trace reconstruction revisited (in Lemma 11), which is basically that the squared Hellinger distance between Binomial$(n,p)$ and Binomial$(n+1,p)$ grows as $O(1/n)$. $...
5
votes
1answer
228 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'...
6
votes
1answer
147 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 \...
