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.

Filter by
Sorted by
Tagged with
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 ...

1
64 65
66
67 68
173