Questions tagged [pr.probability]
Theory and applications of probability and stochastic processes: e.g. central limit theorems, large deviations, stochastic differential equations, models from statistical mechanics, queuing theory.
8,632
questions
0
votes
0
answers
160
views
Lower bound on probability of sum of independent random variables
I'm interested in estimating the following quantity
\begin{equation}\lim_{k \to \infty} \sum \limits_{i=1}^l \sum \limits_{l_1 = 0}^{i} {{nk-k}\choose{l_1}} \Big( \frac{1}{k}\Big)^{l_1} \Big( \frac{...
2
votes
0
answers
54
views
Cumulant of functions of weakly dependent random variables
Suppose $X_1,\dots,X_4$ are Gaussian random variables with mean and variance
$$\mathbf E X_i = 0,\quad \mathbf E X_i^2=1.$$
Furthermore suppose that the random variables have a certain weak ...
2
votes
0
answers
57
views
An upper bound on $\mathbb{E}\bigg[\bigg(\sum_{i=1}^{k}(X^{\top}A_{i}X)^{2}\bigg)^{q}\bigg]$
Let $X\in\mathbb{R}^{d}$ have independent, mean zero subgaussian entries, and $A_{1},\ldots,A_{k}$ be fixed $d\times d$ matrices that have zeros on the diagonal. I would like to upper bound the ...
0
votes
0
answers
52
views
A distribution of maximum of sums if add to the minimal
Consider a vector of $n$ integer variables with initial values of 0. Each step we take random $w_i\thicksim NB(q, l)$ (independent randon values with the same negative binomial distribution) and add ...
2
votes
1
answer
799
views
Bound on eigenvalues of sample covariance matrices in terms of $d, n$, where $n=$ sample size, $d=$ dimension of data
Let $Z=[z_1, \dots z_n]$ be a $d \times n$ matrix, where the $z_i$'s are iid random vactors with mean $\mu \in \mathbb{R}^d$ and $d \times d$ (population) covariance matrix $\Sigma$, but the entries $...
16
votes
2
answers
1k
views
How often two iid variables are close?
Is there a constant $c>0$ such that for $X,Y$ two iid variables supported by $[0,1]$,
$$
\liminf_\epsilon \epsilon^{-1}P(|X-Y|<\epsilon)\geqslant c
$$
I can prove the result if they have a ...
1
vote
0
answers
71
views
Approximating a Distribution with an Ising Model/pairwise MRF
I want to know if there are any results on approximating a distribution with an Ising model/pairwise Markov Random Fields (MRFs).
Formally, let $\mathcal{I}$ be the set of all Ising models/pairwise ...
1
vote
0
answers
115
views
Law of large numbers and Central Limit Theorem for eigenvalues of perturbed matrices
I'm looking for results where perturbation by iid random entries to a matrix will result in convergence of the eigenvalues to the original eigenvalues. More precisely,
Let $ \forall n \in \mathbb{N},...
2
votes
2
answers
268
views
An "obvious" probability lemma about random words
Fix some positive integers $p,n,k$. Let $w$ be chosen uniformly at random from $[k]^n$ (the set of $n$ length words/sequences where each entry is in $\{1,\ldots,k\}$). Let $A_i$ be the event that $...
2
votes
2
answers
349
views
Convergence of fraction of expectation values
Let $X_1,...,X_n$ be iid normal random variables.
I am looking for a strategy to establish the following limit for fraction of expectation values
$$\lim_{N \rightarrow \infty} \frac{E(\prod_{1\le i ...
-1
votes
1
answer
94
views
On bounding a certain discrepancy between probability distributions on the symmetric group
Disclaimer. This is a follow up to a question I asked and answered on SE https://math.stackexchange.com/q/3579311/168758. The question was about upper-bounds. Here I'm interested in lower bounds, and ...
2
votes
1
answer
384
views
Mean squared absolute value of inner product of unit vectors
Given a nonempty finite subset $S$ of the unit sphere of $d$-dimensional complex Hilbert space, let $\lambda(S) = \frac{1}{\lvert S \rvert^2} \sum_{x,y \in S} \lvert \langle x,y \rangle \rvert^2$ be ...
0
votes
1
answer
106
views
Renewal functions inequalities
I came along the statement that for $x \geq z$, if $U(x)$ is a renewal function, there exists a constant $K$ such that
\begin{align}
U(x) - U(x-z) \leq U(z) \leq K (z+1).
\end{align}
This is not ...
4
votes
0
answers
141
views
A possible generalization of Solomonoff's theorem
Assume that $P$ and $Q$ are probability distribution on the binary tree,
i.e. $P$ and $Q$ are functions $\{0,1\}^{*} \to \mathbb{R}$ such that:
for every $x$: $P(x)=P(x0)+P(x1)$ and $P( \text{empty ...
2
votes
1
answer
99
views
Convergence of estimator given by a fixed point
Let $X$ be a non-negative random variable with cdf $F$ and define
$$G(s) = E[\max(0,u(X)-sX)],$$ where $u$ is some real function.
Let $s_0$ be the unique fixed point of $G$.
Now let $X_1,\dots,X_t$ ...
2
votes
1
answer
881
views
Marchenko-Pastur Law under general covariance structure
Let $x_1,...,x_n\in\mathbb{R}^p$ be i.i.d. random vectors with mean 0 and covariance $\Sigma_p$. Let $S_{n,p}=\sum_{i=1}^nx_ix_i^T/n$ be the sample covariance. We consider the asymptotics of the ...
0
votes
2
answers
269
views
Last Inference in proof of conditional limit theorem
I read about the Conditional Limit Theorem from the book "Elements of Information Theory" by Thomas M. Cover and Joy A. Thomas, second edition, page 371. I can't understand the last inference in the ...
2
votes
1
answer
171
views
Marcenko-Pastur and Tracy-Widom laws for sample covariance and Gram matrices when the "features" are correlated: references
Let us assume we've a rectangular data matrix $X=[x_1 \dots x_n] \in \mathbb{R}^{p \times n}$, where the $x_i \in \mathbb{R}^{p \times 1}$ are iid column vectors. I'm not assuming here that the ...
4
votes
2
answers
501
views
Bounding an expectation involving i.i.d. standard Gaussians and Rademacher
I have tried to bound the following quantity, but cannot get the "right" (conjectured) bound:
$$
\phi(\gamma,d,n) = -1+e^{\frac{1}{2}n\gamma^2 d}
\mathbb{E}_{X}\left[\frac{\mathbb{E}_Z[\prod_{j=1}^n(...
5
votes
1
answer
993
views
A general formula for Gaussian integrals over matrix elements
The question I have is quite specific. So in the hope that this post might help others in the future, my problem boils down to solving the following integral:
$$I_\tau=\int \prod_{i, j=1}^{N} d J_{i ...
1
vote
0
answers
96
views
Minima of a random walk and an equality for a fraction
Let $S_n := X_1 + \dots + X_n$ denote a random walk with zero mean and finite variance and write $L_n := \min \{ 0, S_1, \dots, S_n\}$. The tail distribution of $L_n$ are well-known and in particular,
...
1
vote
0
answers
206
views
L2 norm of the diagonal entries of a random rotation of a fixed matrix?
Let $X\in\mathbb{R}^{d\times d}$ be the diagonal matrix with $d/2$ entries equal to $1$ and $d/2$ entries equal to $-1$. Let $F_U \triangleq \frac{1}{d}\|\operatorname{diag}(U^{\dagger}XU)\|^2_F$ ...
2
votes
0
answers
232
views
Reference for Borel $\sigma$-algebra of topology of convergence in probability
I'm pretty sure I can prove the "Theorem" given further below (without very much difficulty), but it seems way too basic not to have been noticed before.
So I'm wondering if there are any papers/...
0
votes
1
answer
96
views
Law of a step function and its generalization to two dimensions on an appropriate spaces
Let's consider two discontinuous functions defined on $D$ and $D \times [0,T]$, respectively:
A step function: $u_1(x)=\begin{cases}
u_{L}, x<c_1, \\[2ex]
u_{R}, x>c_1,
\end{cases}$
A "...
2
votes
0
answers
152
views
Maximizing $\iiint|(x-z)\times(y-z)|d\mu d\mu d\mu$ over probability measures on the unit sphere
This is a follow-up question to the one asked here (the unit circle case). What probability measure(s) maximize the quantity $\iiint_{\mathbb{S}^2}|(x-z)\times(y-z)|d\mu(x)d\mu(y)d\mu(z)$?
The ...
3
votes
1
answer
958
views
Chernoff-type bound for sum of Bernoulli random variables, with outcome-dependent success probabilities
Let $X = (X_1, X_2, \ldots, X_n)$ be a sequence of (not necessarily independent) Bernoulli random variables where for each $i$, the success probability $\Pr[X_i = 1]$ itself is a random variable ...
2
votes
0
answers
102
views
Convergence of Bayesian posterior
Let $\Delta [0,1]$ denote the set of all probability distributions on the unit interval.
Let $\mu \in \Delta [0,1]$ denote an arbitrary prior. Importantly, $\mu$ does not necessarily admit a density ...
1
vote
1
answer
129
views
Large scale analysis of matrix multiplications
Let $\mathbf{A}_{m\times n}$ and $\mathbf{B}_{m\times n}$ be two random i.i.d matrices with zero mean and unit variance. Then, are the following large-scale analysis true (m,n go to infinity with ...
1
vote
0
answers
74
views
Tracy Widom type results for asymptotic distribution of the $k$-th largest eigenvalue of the sample covariance when $n, p \to \infty$?
Earlier I asked a question: Distribution of the $k$-th largest eigenvalue of in the sample covariance matrix?, but I forgot to mention that I'd like results for asymtotic regime. So, I'm posting here ...
0
votes
0
answers
92
views
Distribution of the $k$-th largest eigenvalue of in the sample covariance matrix?
Let us assume we've a rectangular data matrix $X=[x_1 \dots x_n] \in \mathbb{R}^{p \times n}$, where the $x_i \in \mathbb{R}^{p \times 1}$ are iid column vectors. I'm not assuming here that the ...
0
votes
1
answer
250
views
Sum of sequences of random variables, with variable success probabilities
Consider two sequences of (not necessarily independent) Bernoulli random variables $X_1, X_2, \ldots, X_n$ and $Y_1, Y_2, \ldots, Y_n$. Suppose that for any $i$, we have $\Pr[X_i = 1] = \Pr[Y_i = 1] = ...
2
votes
1
answer
147
views
Volume computation using probabilistic approach
Let $\mathbb{S}^{d-1}=\{v\in\mathbb{R}^d:\|v\|_2=1\}$, namely $d-$dimensional sphere. It is well-known that if a random vector $X$ is distributed uniformly on $\mathbb{S}^{d-1}$, then there exists i.i....
1
vote
0
answers
164
views
A question about Stroock's notes on the Weyl lemma
On p.4 of these notes, D. Stroock gives a quick and efficient construction of the Markov transition functions of a certain diffusion. The idea of his construction (on page 4) is to 'freeze' the ...
2
votes
1
answer
664
views
Show the coordinate distribution has a very large sub-gaussian norm
Consider a random vector X with the coordinate distribution is uniformly distributed in the set $\{\sqrt{n}e_i : i = 1,..., n\}$, where $e_i$ denotes the n-element set of the canonical basis vectors ...
3
votes
3
answers
159
views
A stopping time that gives the metric
Let $\Omega$ a finite metric space with $\forall x,y,z\in \Omega:d(x,y)<d(x,z)+d(z,y)$. Does there exists a continuous-time Markov process $X$ on $\Omega$ such that $$\mathbb{E}_x(T_y)=d(x,y)$$ for ...
4
votes
2
answers
646
views
Hypercontractivity of two simple random variables, $E[XY]^s \le E[X^s]E[Y^s].$
For $\alpha,\beta\ge 0$, let $X\in\{1,\alpha\}$ and $Y\in\{1,\beta\}$ be two random variables such that $$XY = \begin{cases}
\alpha\beta \quad & \text{with probability} \quad p_{11}\\
\alpha \quad ...
8
votes
2
answers
430
views
Inductive definition of Bernstein polynomials
For $n\in \mathbb{N}$ let $B_n$ be the linear operator taking a function $f$ on the unit interval $I=[0,1]$ to its $n$-th Bernstein polynomial $B_nf$,
$$ B_nf(x):=\sum_{k=0}^n\binom{n}{k} f\Big(\...
9
votes
0
answers
796
views
Positive definiteness of matrix
This question is about the positive definiteness of a (non-random) matrix that is defined using random variables as follows:
We fix the vector $v=(1,1)$ (yet, it seems the final result does not ...
1
vote
1
answer
375
views
Size of minimum cut in random graph
Consider a uniform random tournament with $n$ vertices. (Between any two vertices $x,y$, with probability $0.5$ draw an edge from $x$ to $y$; otherwise draw an edge from $y$ to $x$.) The score of each ...
2
votes
0
answers
259
views
Explicit formula for this distance between positive semi-definite matrices?
Let $A$ and $B$ in $\mathbb{R}^{d\times d}$ be positive semi-definite (psd) matrices and let $d\tau$ be the uniform probability distribution on the unit sphere $\mathbb{S}^{d-1}$ in $\mathbb{R}^d$. I ...
2
votes
2
answers
741
views
Eigenvalue distribution of a random matrix
Is there any closed form distribution formula for the distribution of the eigenvalues of $\mathbf{X}^\mathrm{H}\mathbf{X}$ where the entries of $\mathbf{X}$ are independent Gaussian random variables ...
2
votes
0
answers
65
views
Properties of solution to Burger's equation using Cole-Hopf transformation
I am currently looking at a $1$D-Burger's equation defined by
\begin{equation} \label{ex burgers}
\left\{
\begin{array}{ll}
{} & \frac{\partial V_m}{\partial t} (t,x) = \frac{\sigma^2}{2} \...
0
votes
0
answers
262
views
Is there any relation between moments of random matrix and its eigenvalue distribution?
Let $\mathbf{X}$ be a random matrix with independent Gaussian random variable entries with different variances $v_{ij}$. Also define $\mathbf{A}=\mathbf{X}^\mathrm{H}\mathbf{X}$. Is there any relation ...
1
vote
1
answer
100
views
Limit of normalized sum of Dirac measures at first $\lfloor p/2\rfloor$ eigenvalues of the sample covariance matrix, with Marcenko-Pastur assumptions?
Let $\lfloor{*}\rfloor$ denotes the nearest integer $\le *$. I'm asking myself the question what's the limit of the part of the empirical spectral distribution corresponding to the first $\lfloor{p/2}...
14
votes
4
answers
4k
views
What are two independent, uniformly distributed random variables on the unit interval?
I have been dabbling in learning basic things about probability theory and (of course) being of the school of abstract nonsense I have tried to understand things in its language. I apologize if this ...
6
votes
2
answers
681
views
2D closed convex shape which minimizes average distance between points
For a 2D closed convex shape, with metric $d$ and fixed area $A$, we can calculate the average distance between random (interior) points. For different shapes, we will get different values for this ...
25
votes
3
answers
10k
views
L1 distance between gaussian measures
L1 distance between gaussian measures: Definition
Let $P_1$ and $P_0$ be two gaussian measures on $\mathbb{R}^p$ with respective "mean,Variance" $m_1,C_1$ and $m_0,C_0$ (I assume matrices have full ...
1
vote
1
answer
81
views
Disintegration associative
Is the disintegration of two borelian probabilities measures is associative ? It means if $\mu = \mu_{y}^{1} \oplus h_{\#}^{1}\mu$ and $ h_{\#}^{1}\mu = \mu_{y}^{2} \oplus h_{\#}^{2} h_{\#}^{1}\mu$. ...
1
vote
1
answer
164
views
Proof for an extension of Azuma's inequality
I am trying to understand a part of the proof of an extension of Azuma's inequality, where there is a small failure probability, as it appears in proposition 34 in "Random matrices: universality of ...
2
votes
2
answers
109
views
Difference between two largest degrees
Consider a uniform random tournament with $n$ vertices. (Between any two vertices $x,y$, with probability $0.5$ draw an edge from $x$ to $y$; otherwise draw an edge from $y$ to $x$.) Let $S$ be the ...