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.
9,027 questions
7
votes
2
answers
623
views
What is the liminf of a sum of i.i.d. random variables with heavy tails?
Let $\{X_i\}_{i=1}^{\infty}$ be i.i.d. random variables such that: i) $X_i > 0$; and ii) $\textrm{Pr}[X_i > x] \sim x^{-\alpha}$ at large $x$ for some $\alpha \in (0, 1)$. Define the quantities
\...
- 73
7
votes
1
answer
427
views
Regularity for the sum of iid random variables
Let $(X_i)_{i\in \mathbb{N}}$ iid random variables such that there exists $\alpha>0$ where $\mathbb{P}\left(X_1\in [x,x+1]\right)\leq \alpha$ for all $x\in \mathbb{R}$. Assume $\alpha$ small ...
- 4,361
7
votes
2
answers
647
views
Moments of a positive random variable
Suppose one is handed a list of $K$ numbers, with a claim that these numbers are the first $K$ moments of a positive random variable $X$ (meaning there is 0 probability that $X<0$).
What is the ...
- 361
7
votes
1
answer
1k
views
Properties of convolutions
Consider the function
$$f_{n}(x)=e^{-x^2}x^n.$$
and the function
$$h_p(x):=e^{-\vert x \vert^p}.$$
My goal is to analyze
$$ F_p(y):=\frac{(f_2*h_p)(y)}{(f_0*h_p)(y)}- \left(\frac{(f_1*h_p)(y) }{(f_0*...
- 173
7
votes
3
answers
3k
views
expected value of squared infinity norm of vector of iid gaussians
Given a random vector
\begin{equation}
x=(x_1, \ldots, x_n)
\end{equation}
with independent and identically distributed entries $x_i \sim \mathcal{N}(0,\sigma^2)$, I would like to find a lower ...
- 237
7
votes
1
answer
857
views
Trace of inverse of random positive-definite matrix in high dimension?
Consider a random matrix $A \in \mathbb{R}^{n\times n}$ with i.i.d. entries, with symmetric law and finite variance. I am curious about the behavior of $$\mathrm{Tr}( (A^T A + \lambda \mathrm{Id})^{-1}...
- 2,306
7
votes
1
answer
975
views
Prove an anti-concentration inequality for a martingale
My problem can be described easily:
I have a sequence $(X_l)_{l \in \mathbb{N}}$ of r.v. adapted to some filtration $(\mathcal{F}_l)_{l \in \mathbb{N}}$, such that
$\left|X_{l+1}-X_l\right|\le R$ a. ...
- 73
7
votes
2
answers
626
views
What is the strongest known RSW result in planar percolation?
One of the weakest estimates conjectured to hold for critical planar percolation models (and proved in many cases) is the so-called RSW estimate. RSW estimate is the statement that the probability of ...
- 18.7k
7
votes
1
answer
342
views
Upper Bound for the Difference of Even Probability and Odd Probability in Hypergeometric Distribution
Let $X$ be a random variable following the hypergeometric distribution with parameters $N,K,n$, where
\begin{equation}
Pr(X=k) = \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}.
\end{equation}
To ...
- 183
7
votes
2
answers
234
views
Ising model on lattices with (vertical side length) $\neq$ (horizontal side length)
Consider the Ising model with nearest neighbours interactions on a rectangular lattice $L\times M$.
If $L=M$ ($2$-dimensional square lattice), it is known (e.g., by Peierls' argument or Onsager's ...
- 311
7
votes
1
answer
2k
views
What is the continuous limit of characteristic functions of probability measures in infinite dimensional spaces?
As we all know that
If $\{\varphi_n\}$ is a sequence of characteristic functions of probability measures $\{ \mu_n \}$ on $\mathbb{R}$. And $\lim\varphi_n(t)$ exists for each $t\in \mathbb{R}$. Set ...
- 321
7
votes
1
answer
753
views
Is every submartingale a convex function of a martingale?
Is every submartingale a convex function of a martingale?
- 71
7
votes
3
answers
542
views
Markov Processes with Given Marginals
Let $\mu_t, t \geq 0,$ be a family of probability measures on the real line. One can assume whatever one wishes about them, although typically they will be continuous in some topology (usually at ...
- 315
7
votes
3
answers
995
views
Kolmogorov probability axioms without non-negativity condition
What is a minimal consistent modification of probability axioms to include negative values?
Is it enough to use a minimal modification of axioms obtained by
formal exclusion of non-negativity ...
- 211
7
votes
5
answers
514
views
Probability of $\operatorname{Bin}(n,p)=\operatorname{Bin}(n,q)$ is decreasing when $n$ increases
$\newcommand{\Bin}{\operatorname{Bin}}$I would like to show that $\mathbb P(\operatorname{Binomial}(n,p) = \operatorname{Binomial}(n,q))$ decreases when $n$ increases for a fixed pair $(p,q)$. This ...
- 243
7
votes
1
answer
556
views
A variation on the Borel–Cantelli lemma theme
Let $X,X_0,X_1,\dots$ be nonnegative independent identically distributed (i.i.d.) random variables. Let
\begin{equation*}
E:=\bigcap_{n\ge0}B_n,
\end{equation*}
where
\begin{equation*}
B_n:=\...
- 128k
7
votes
1
answer
618
views
Is there any categorical version of central limit theorem?
I'm not sure if the question even makes sense, but I wonder if there's any categorical reason that explains importance of Gaussian/normal distribution. In the ordinary probability theory, I guess ...
- 2,215
7
votes
1
answer
509
views
An order statistics problem with some interesting geometry
Let $a_n$ be a given sequence of positive numbers, and $X_n$ a sequence of independent random variables with each $X_n$ uniformly distributed on $[0, a_n]$.
Question: Let $N \geq 2$ be an arbitrary ...
- 6,323
7
votes
2
answers
393
views
On a von Bahr–Esseen-type inequality for pairwise independent zero-mean random variables
For $p\in(1,2)$, let $C_p$ be the smallest constant factor $C$ in the von Bahr–Esseen-type inequality
\begin{equation}\label{eq:pair}\tag{1}
E\Bigl\lvert\sum_{j=1}^n X_j\Bigr\rvert^p\le C\sum_{j=1}...
- 128k
7
votes
2
answers
1k
views
Why is the spectrum of Erdős–Renyi random graph approximately symmetric?
I am recently self-learning random matrix theory and made some simulations about the spectrum of Erdős–Renyi random graph $G(n,p)$ when $np\to\infty$,
and $np\to c=2,3$.
The plots above are already ...
- 715
7
votes
4
answers
476
views
What does $\mathbb E_V \max_{x \in V,\,\|x\|=1} x^T Ax$ evaluate to when $V$ is random $k$-dim suspace of $\mathbb R^n$ and $A$ is fixed psd matrix?
Let $G_{k,n}$ be the grassmannian of $k$-dimensional vector spaces of $\mathbb R^n$. By the Courant–Fisher characterization, the $k$th largest eigenvalue of an $n \times n$ psd matrix $A$ is given by
$...
- 6,853
7
votes
2
answers
2k
views
Proof of extended supermartingale convergence theorem
There is a supermartingale convergence theorem which is often cited in texts which use Stochastic Approximation Theory and Reinforcement Learning, in particular the famous book "Neuro-dynamic ...
- 183
7
votes
1
answer
261
views
Comparison of several topologies for probability measures
Let $X$ be a compact metric space and denote $\mathcal M(X)$ the set of probability measures on $X$. For $\mu\in\mathcal M(X)$ we write $\operatorname{supp} \mu$ for the support of $\mu$. As is well ...
- 243
7
votes
2
answers
460
views
Gaussian Surface Area of Positive Semidefinite Cone
Let $\mathbb{R}^n$ be the Euclidean space and $A \subseteq \mathbb{R}^n$ be a sufficiently regular set, e.g., one that has smooth boundary or is convex. We define the $\epsilon$-neighbor of $A$ in the ...
- 1,127
7
votes
2
answers
186
views
Do successive maximum permutations pick latin squares uniformly?
Suppose we start with a $n\times n$ matrix with entries sampled independently and uniformly at random from $[0,1]$. The weight of a set of entries will simply be the sum of those entries. A ...
- 85.6k
7
votes
1
answer
265
views
Is this simple-looking moment inequality true?
Let $p \ge 1$ be an integer. Does there exist a constant $C_p$ such that for every random variable $X \ge 0$,
$$
\mathbb{E} \left[ \left(X - \mathbb{E} \left[ X \right] \right)^{2p} \right] \le C_p \...
- 562
7
votes
2
answers
606
views
Gaussian and the convex hull of moment curves
Let $c_1,\dots, c_d$ be the first $d$ moments of the standard normal distribution. Does the point $(c_1,\dots, c_d)$ lie in the convex hull of the set $\{(t,t^2,\dots,t^d)\colon t\in[-b,b]\}$, for a ...
- 1,127
7
votes
1
answer
583
views
Inequality for the maximum of Gaussian variables
Let $X=(X_1,\dots,X_n)$ and $Y=(Y_1,\dots,Y_n)$ be centered Gaussian vectors
with variance matrix $\Gamma_X$ and $\Gamma_Y$. We assume that the matrix
$\Gamma_Y-\Gamma_X$ is positive definite. Is it ...
- 103
7
votes
1
answer
757
views
Length of nearest neighbor path in travel salesman problem
Given $n$ nodes uniformly distributed in $[0,1]^2$, consider the nearest neighbor algorithm to solve traveling salesman problem, i.e., each time I select the nearest neighbor not visited so far as the ...
- 367
7
votes
3
answers
896
views
A balls and urns model for a hashing problem
Fix $N \in \mathbb{N}$. Suppose we throw $N$ numbered balls into $N$ numbered urns, so that for each $b \in \{1,\ldots,N\}$, ball $b$ lands in urn $j$ with equal probability $1/N$. Choose a number $c \...
- 11.2k
7
votes
3
answers
413
views
Constructing a Bernoulli random variable for ratio of Bernoulli weights
$X$ and $Y$ are Bernoulli random variables with weights $0 < \alpha < 1$ and $0 < \beta < 1$. Is it possible to construct a sampler for the Bernoulli random variable with weight $\min(\...
- 73
7
votes
1
answer
319
views
Why aren't operator semigroups studied from a dynamical perspective?
Often times one talks about iterating a continuous map to get discrete topological dynamics, or having a 1-parameter family of continuous maps to get continuous topological dynamics.
When studying ...
- 277
7
votes
1
answer
3k
views
What is characteristic function of maximum of i.i.d. random variables?
Is is possible to get characteristic function of maximum of i.i.d. random variable sequence? Such as $X_1, X_2$ are two i.i.d random variables, then what is characteristic function of $X=\max(X_1,X_2)$...
- 83
7
votes
1
answer
482
views
Continuous dependence of the expectation of a r.v. on the probability measure
$\newcommand{\bsV}{\boldsymbol{V}}$ $\newcommand{\bsE}{\boldsymbol{E}}$ $\newcommand{\bR}{\mathbb{R}}$ Suppose that $\bsV$ is an $N$-dimensional real Euclidean space. Denote by $\newcommand{\eA}{\...
- 34.7k
7
votes
1
answer
499
views
How similar are discrete stable RVs to their continuous analogues?
The generalized central limit theorem of Gnedenko-Levy describes the asymptotic behavior of a sum of IIDRVs which may not have finite mean or variance. Only a small class of limit laws can be realized,...
- 15.4k
7
votes
2
answers
232
views
Local view of setting p*n out of n bits to 1
For p a constant in (0,1) and n going to infinity such that pn is an integer,
consider the distribution on n bits that selects a random subset of pn bits, sets those to 1, and sets the others to 0.
...
- 393
7
votes
2
answers
617
views
Fractional Brownian motion of Riemann-Liouville type is not a semimartingale
Given a filtered probability space $(\Omega,\mathcal{F},\mathbb{F},\mathbb{P})$ satisfying the usual conditions, $B$ a standard one-dimensional Brownian motion and $H\in(0,1/2)$. Consider the process $...
- 199
7
votes
1
answer
630
views
Local limit theorem for random walks on $\mathbb Z^d$
I'm looking for a reference for the following claim.
Let $W(n)$ be a centered random walk on $\mathbb Z^d$ with $W(0)=0$.
Suppose that $W(n)$ has a finite second moment.
Let $n\ge 1 $ and $k \in \...
- 723
7
votes
1
answer
328
views
What is the correct notion of morphism between statistical manifolds?
Given two statistical manifolds, is there a notion of "isomorphic"? What are morphisms?
- 133
7
votes
1
answer
463
views
Boundedness of total current in electrical network
Consider the following symmetric matrix (adjacency matrix):
$$A=(a_{ij})_{1\leq i,j\leq n}$$
such that $a_{ij}=a_{ji}, a_{ii}=0$ and $a_{ij}=0$ for $|i-j|\geq k$ where $k\geq3$. We also have $1\leq a_{...
- 1,495
7
votes
2
answers
211
views
Support of closed random walk on $\mathbb Z$
I am researching closed random walks on graphs and have the following problem that I haven't been able to find a reference for.
Consider a random walk on $\mathbb Z$ starting at 0 and at each step ...
- 175
7
votes
2
answers
890
views
Optimisation: $H(X_1) + H(X_2) +H(X_3) - H(X_1+X_2+X_3)$
Consider the following optimisation.
$$\max [H(X_1) + H(X_2) +H(X_3) - H(X_1+X_2+X_3)],$$
where H denotes the Shannon entropy, + denotes addition over real numbers, ...
user83947
7
votes
2
answers
259
views
Slowest initial state for convergence of finite birth-and-death Markov chains
Consider the continuous-time birth-and-death Markov chain on $\{1,\cdots,n\}$ with all rates equal to $1$. Is it true that the convergence to equilibrium, in total variation distance, is slowest when ...
- 4,653
7
votes
1
answer
311
views
E[X|Y] and E[Y|X]
Suppose $x, y$ are random variables jointly distributed on $[0,1]^2$. The marginal distribution of $x$ is uniform. It is also known that $E[y]=E[x]=\frac12$ and $E[x|y]=y$, so $y$ second-order ...
- 157
7
votes
1
answer
374
views
Sampling uniformly from the vertices of a polytope
I'm looking for a reference on how to sample uniformly (and preferably efficiently, elegantly, etc.) from the vertices of a polytope. I gather that enumerating vertices is hard. I also note the MO ...
- 15.4k
7
votes
4
answers
3k
views
Upper bound of the expectation of sum of the absolute value pairs
We have two arrays $A,B$ of length $n$. All values are i.i.d drawn from same distribution on $[0,1]$. If we sort $A,B$ in non-decreasing order and let $A_{(i)},B_{(i)}$ denote the i-th value in the ...
user124861
7
votes
1
answer
466
views
Martingale version of Bernstein-type inequality for (slightly) heavy-tailed distributions?
It is known that for sub-exponentially distributed martingale difference sequence, the following Bernstein-type inequality holds:
$$
ℙ\left(\left|
\sum_{i=1}^N a_i X_i
\right| \ge t \right)
\le
2\...
- 719
7
votes
2
answers
469
views
One dimension random walk. Is hitting time Lipschitz with respect to target?
Consider a random walk $S_t = \sum_{i=1}^{t} X_i$, with $X_i$ i.i.d.. Assume that $X_i \in [0,1]$. Define $\tau(y) := \inf\{t: S_t\geq y\}$, i.e., $\tau(y)$ is the hitting time of $[y,\infty)$. Is ...
- 103
7
votes
2
answers
1k
views
Edge probability for connected Erdős–Rényi model
Consider the Erdős–Rényi model $G_{n,p}$ with corresponding probability measure $\mathbb{P}_{n,p}$. For any two vertices $x,y$, $\mathbb{P}_{n,p}[E_{x,y}]=p$, where $E_{x,y}$ is the event that there ...
- 71
7
votes
1
answer
1k
views
Moment bounds on exponential martingale
Consider the exponential martingale used in the Girsanov transformation of
measure:
$$Z(t) = \exp\Big(\int_0^tXdW - \frac{1}{2}\int_0^t|X|^2ds\Big)$$
so that $Z$ solves the sde $dZ = ZXdW$ where $W$ ...
- 143