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
22 views

Size of the second largest strongly connected component in random directed graphs with fixed in- and out-degree sequences

It has been known for long (Molloy and Reed 1995) that in a supercritical undirected configuration model, that is when $E[D(D-2)]>0$, $D$ degree of a uniform vertex, the size of the second largest ...
  • 56
3 votes
0 answers
169 views

Approximating any $d$-dimensional convex shape that occupies a constant fraction of its bounding box with a polytope having $\mathrm{poly}(d)$ facets

Given any convex set $A\in\mathbb{R}^d$, we denote by $V(A)$ its $d$-volume. Furthermore, given any two convex sets $A_1,A_2\in\mathbb{R}^d$, we denote by $V_{A_1,A_2}$ the $d$-volume of the symmetric ...
-1 votes
0 answers
71 views

Markov chain + variable

Consider $P(X,Y)$ discrete and a Markov chain $Y_0 \rightarrow Y_1 \rightarrow \dotsc \rightarrow Y_{L-1} \rightarrow Y_L$ with $Y_0 := Y$. The chain $Y_L \rightarrow Y_{L-1} \rightarrow \dotsc \...
  • 187
4 votes
1 answer
123 views

Decreasing tail integrals for nonnegative random variable $X$

Let $X$ be a nonnegative random variable with density function $f(x)$, distribution function $F(x)$, survival function $S(x)=1-F(x)$ and finite first and second moments. Let also $$\ell(x):=\frac{1}{...
7 votes
0 answers
137 views

Approximating any convex shape in $\mathbb{R}^d$ with a polytope having $\mathrm{poly}(d)$ facets

We denote by $V(A)$ the $d$-volume of any convex set $A$. Furthermore, given any two convex sets $A,B\in\mathbb{R}^d$, we denote by $V_{A,B}$ the $d$-volume of the symmetric difference $V\left(A \...
3 votes
1 answer
68 views

Quasi-random vs pseudo-random graphs

My question is somehow concerning terminology on extremal graph theory. Is there any difference concerning the notion of quasi-random graph and the notion of pseudo-random graph? My feeling is that ...
  • 1,356
4 votes
2 answers
169 views

Vague convergence: confusion about the regularity of a signed Radon measure and that of its variation

I'm reading a proof of below theorem from this paper. Theorem A.3. Let $\Omega$ be a locally compact normal Hausdorff space. Let $\left\{\mu_n\right\} \cup\{\mu\} \subset \mathcal{M}(\Omega)$ and ...
  • 339
9 votes
2 answers
413 views

Sum of a Poisson point process

Let $Z_1, Z_2, \dots$ be a Poisson point process on $[0, 1]$ with intensity function $1/z$. What is the distribution of the sum $Z = \sum_{i=1}^\infty Z_i$? One can construct $Z_1, Z_2, \dots$ by ...
1 vote
1 answer
47 views

Lower bound $L_{1}$-metric with $L_{2}$-metric for bounded pdfs, on common support

Setup To clarify, let constants $0 < a < b < \infty$, and $p \in \mathbb{N}$ be fixed. Further let $B \subset \mathbb{R}^{p}$ be a fixed compact support. We then define the space of bounded (...
0 votes
0 answers
55 views

Modification of a lemma on the boundness of a stochastic process

Lemma 1 is widely used in the stability proof of stochastic process. Lemma 1 Assume that $\xi_k$ is a stochastic process and there is a stochastic process $V(\xi_k)$ as well as real numbers $\upsilon_{...
0 votes
0 answers
50 views

Probability of polynomials products to be bounded by a given bound

I am given a quotient ring $R=\frac{\mathbb{Z}[x]}{\left< x^n +t\right>}$ for $t\in\mathbb{Z}$, and two polynomials from $R$, $A$,$B$ and let $C$ to be there product. Defining the norms $$\Vert ...
0 votes
0 answers
14 views

Associated $\alpha$-stable moving averages are (BL, $\theta$)-dependent

Setting and definitions This is a follow-up question on "Are infinite-variance associated processes are (BL, $\theta$)-dependent?". The answer to that question was no in general. So maybe a ...
2 votes
2 answers
200 views

Minimal conditions on random vector $X \in R^n$ to ensure that $\lim_{t\to 0^+}\sup_{\|w\|_p = 1}\sup_{u \in \mathbb R}\mathbb P(|X'w-u| \le t)=0$

Let $X$ be a random variable on $\mathbb R^n$ and let $S_p^n := \{w \in \mathbb R^n \mid \|w\|_p = 1\}$ be the unit-sphere w.r.t to the $\ell_p$-norm in $\mathbb R^n$. We will be particularly ...
  • 6,094
5 votes
0 answers
125 views

Concentration inequalities for random measures

For random variables $X_1,\dots,X_n$ with common mean $\mathbb{E}[X_i]=\mu$ and common bounds $a\leq X_i\leq b$, we have the very useful Hoeffding's inequality: $$\mathbb{P}\left(\left|\mu -\frac1n\...
  • 81
3 votes
1 answer
118 views

When are the total variation distance and Hellinger distance comparable?

The total variation distance between (say discrete) probability distributions, represented as vectors over their support, is defined to be $$\Delta(\vec p,\vec q) = \frac{1}{2}\lVert \vec p-\vec q\...
  • 1,033
3 votes
1 answer
138 views

A linearly distributed version of the balls into bins problem

Some years ago, I found a paper with all the formulas for the balls into bins problem when the "areas" (i.e., probabilities to capture a ball) of the bins are all different. However, the ...
2 votes
1 answer
40 views

Infinite-variance associated processes are (BL, $\theta$)-dependent

Setting and definitions Let $X = \{X(t), t \in T \}$, $T \subset \mathbb{Z}$, be an infinite-variance associated stochastic process, i.e. $$ \text{Cov}(f(X(I)), g(X(J))) \geq 0 $$ for all finite ...
0 votes
1 answer
201 views

Deduce that a function is zero on interval $[0,M]$

I have been thinking about this for the last few days but I was not able to produce a definitive answer. Take an integrable function $g$ that maps in $\mathbb{R}$ and with domain contained in $[0,M]$ (...
0 votes
0 answers
77 views

For fixed $f \in L^2$ and $T>0$, choose $g$ so that $ \mathbb{E}^x[g(T-\tau)\chi_{X_\tau=1}]=-\mathbb{E}^x[f(X_T)\chi_{\tau \ge T}]$

Let $f \in L^2(0,1)$ and $T>0$ be fixed. How can I choose $g \in L^2(0,T)$ such that \begin{align*} 0\equiv \mathbb{E}^x\left[f\left(X_T\right) \chi_{\tau \geqslant T}+g(T-\tau) \chi_{X_\tau=1}\...
  • 9
0 votes
1 answer
68 views

Ito-Levy decomposition for $\alpha$-stable processes?

The Ito-Levy decomposition is well-known as a characterization of Levy processes. What does it give for the specific case of $\alpha$-stable Levy processes?
  • 9
0 votes
0 answers
17 views

Generalization of covariance of random (eigen)vectors to $k-$variance

Recently I got interested in "random Gaussian eigenvectors": Fix a large matrix $A\in \text{GL}_d(\mathbb{C})$ and denote the orthogonal projector to a fixed eigenspace by $P$. One can ...
2 votes
1 answer
66 views

Distribution of scaled Johnson-Lindenstrauss transforms

Suppose that $\mathcal{D}$ is a Johnson-Lindenstrauss (JL) distribution on $\mathbb{R}^{r\times n}$ ($1 \le r \le n$), meaning that there exist constants $\epsilon, \delta \in(0,1)$ such that $$ \...
  • 221
0 votes
1 answer
39 views

Do we have the universal property of the edge of the spectrum for the Wigner matrix?

In Chapter 3 of the textbook: An Introduction to Random Matrices, we have that for normalized GUE/GOE/GSE and ordering its eigenvalues $\lambda_1\le \lambda_2\le \cdots \le \lambda_n$, we have that $$ ...
  • 136
0 votes
1 answer
101 views

Abstract Wiener spaces for pinned processes (e.g., Brownian Bridge)

In introductions to abstract Wiener spaces, the sample paths usually form a Banach space; so, in particular, the sum of two sample paths is a valid sample path and also an element of the Banach space. ...
0 votes
0 answers
104 views

$\mathbb{P}(\|A^Tx\| \ge \epsilon \|A\|\|x\|) \ge \delta$ for all $x \in\mathbb{R}^n$

Let $r$ and $n$ be integers such that $1 \le r \ll n$, and $\|\cdot\|$ denote the Euclidean norm of vectors or the spectral norm of matrices. Suppose that $\mathcal{D}$ is a probability distribution ...
  • 221
0 votes
0 answers
22 views

Sufficient conditions on the density of a random vector $X$ to ensure that the density of $X^\top w$ is Holder-continuous for all $w \in \mathbb R^d$

Let $X$ be a random vector $\mathbb R^d$, with density $f$. For any any unit-vector $w \in \mathbb R^d$, let $\rho_w$ be the density of the random vector $X^\top w$. Question 1. Under what minimal ...
  • 6,094
1 vote
1 answer
160 views

Forgery theorem: the Brownian motion stays close to any curve with positive probability

In a paper I am reading the authors claim that, if $B$ is a standard BM in $\mathbb{R}$ and $f\in C([0,1],\mathbb{R})$, then for any $\epsilon>0$ $$ \mathbb{P}(\sup_{t\in [0,1]}|B_t-f(t)|<\...
  • 701
3 votes
1 answer
155 views

Is the limit of compound Poisson random variables a compound Poisson r.v.?

Let $Y$ be an infinitely divisible (I.D.) random variable. Let $\nu$ be any measure not necessarily finite: $\nu(\mathbb R)\leq \infty$. Suppose that $Y \sim (0, \nu,0)_0$ according to the notation on ...
  • 175
1 vote
1 answer
63 views

An inequality involving the Wasserstein distance and chi-squared distance

$\newcommand{\N}{\mathbb N}$Let $P$ be the set of all probability mass functions on $\N_0:=\{0\}\cup\N$, where $\N:=\{1,2,\dots\}$. Let $P_{>0}$ denote the set of all $q=(q_0,q_1,\dots)\in P$ such ...
3 votes
1 answer
72 views

Mutual information in large deviation theory

Many information theoretic quantities such as entropy and relative entropy appear in rate functions in large deviation theory (LDT). Is there any result in LDT that relates mutual information and rate ...
1 vote
1 answer
106 views

Upper bound Wasserstein distance by $\chi^2$ distance

Given two random variables $X,Y$ which are both $\mathbb{N}$-valued and have the same expected value (which is some fixed positive constant), and denote their probability mass functions by ${\bf p} = (...
  • 464
2 votes
1 answer
172 views

Estimating the volume of a convex shape in higher dimensions based only on normal sections

We are given a $d$-dimensional convex shape $S$ inscribed in the hypercube $[-1,1]^d$. We want find an approximation of its volume based only on a set of curves given by the intersection of the $S$ ...
-1 votes
1 answer
91 views

Distribution of root with Poisson leaves

We have a pool of items, termed as item A, generated following a Poisson distribution. We use a pair of items A to produce an item B with success rate $r\in(0,1)$. My question is: is B Poisson ...
  • 439
3 votes
0 answers
183 views

Probabilistic optimization problem on tree vertex selection without replacement proportional to the degree

We are given a tree $T(V,E)$ with $|V|=n$ vertices, where $V=\{v_1,v_2,\ldots, v_n\}$. We denote by $d_i$ the degree of vertex $v_i$ for all $i\in\{1,2,\ldots,n\}$. In a sequential fashion, we select ...
1 vote
1 answer
75 views

Tight upper-bounds for the Gaussian width of intersection of intersection of hyper-ellipsoid and unit-ball

Let $\Lambda$ be a positive-definite matrix of size $n$ and let $R \ge 0$, which may depend on $n$. Consider the set $S := \{x \in \mathbb R^n \mid \|x\|_2 \le R,\,\|x\|_{\Lambda^{-1}} \le 1\}$ where $...
  • 6,094
3 votes
0 answers
66 views

Upper bound of conditional mutual information

Given random variables $X$,$Y$ with a joint distribution $P(X,Y)$ and another random variable $Z$, it is known that there are cases when the conditional mutual information $I(X;Y|Z)$ is greater than ...
4 votes
0 answers
76 views

Does the existence of regular conditional measure follow from that of regular conditional distribution?

For more succinct description, I use the following abbreviations, i.e., RCPD: Regular conditional probability distribution. RCPM: Regular conditional probability measure. First are definitions 10.4....
  • 339
3 votes
1 answer
186 views

Push-forward of uniform measure and uniqueness

On a standard Borel (or Polish) space $X$, any probability measure $\mu$ is the push-forward of the uniform measure on $[0, 1]$ under some $f : [0, 1] \to X$. This $f$ is not unique in general. ...
  • 197
4 votes
1 answer
151 views

Percolation: at what length scale do we see it?

Consider classical bond percolation on $\mathbb{Z}^d$. Each edge is included with probability $p$ and deleted with probability $1-p$. As is well known, there is a $p_c(d) \in (0,1)$ such that $p>...
2 votes
0 answers
87 views

Optimization problem on randomly selecting subintervals from a given interval with combinatorial constraints

We select uniformly at random $k$ pairwise disjoint intervals from a given interval $[0,s]$ with length respectively equal to $\ell_1, \ell_2, \ldots, \ell_k\ $, i.e., we select uniformly at random $k$...
1 vote
0 answers
58 views

Mixed moments of traces

I've seen a host of results concerning computations for $$\mathbb{E} \left[ \operatorname{tr} A^{i_1}\cdots \operatorname{tr} A^{i_j} \,\overline{\operatorname{tr} A^{k_1} \cdots \operatorname{tr} A^{...
  • 171
1 vote
0 answers
56 views

Reference request: rates of weak convergence of Polish space-valued random variables

Let $(E,\mathscr{E})$ be a Polish space $E$ together with its Borel $\sigma$-algebra $\mathscr{E}$. Let $(\Omega, \mathscr{F},P)$ be a probability space and let $(X^{(n)})_{n \in \mathbb{N}}$ be a ...
  • 111
4 votes
1 answer
183 views

Minimum of random walks

Let $M$ independent and identical random walks that follow the chi-squared distribution, i.e. in each step, a $X^2_1$ random variable is added. I am interested in the minimum random walk at each step. ...
3 votes
1 answer
114 views

Asymptotic results for smallest gap of Gaussian random matrix

For a symmetric Gaussian random matrix $G=\{G\}_{1\le i,j \le n}$ with iid $E[G_{ij}]=0$ and $E[G_{ij}^2]=1/n$ (it is normalized), ordering its eigenvalues $\lambda_1\le \lambda_2\le\cdots \lambda_n$. ...
  • 136
2 votes
0 answers
68 views

Generalization of the min-entropy that looks at the top $n$ probabilities

The min-entropy of a random variable $X$ can often be much easier to compute than the Shannon entropy. This is because the min-entropy is simply a function of the most probable value, and sometimes, ...
4 votes
0 answers
115 views

Disintegration of measures: a confusion about an existence proof from a lecture note

I'm reading a proof of Theorem 2.25 below from this note. First, we recall a definition and a theorem, i.e., Theorem 2.25 (Disintegration). Let $\left(Z, d_Z\right)$ and $\left(X, d_X\right)$ be ...
  • 339
1 vote
1 answer
163 views

How to prove that upper bound of the hitting time holds with high probability?

Let $G$ be a symmetric Gaussian random matrix with iid $E[G_{ij}]=0$ and $E[G_{ij}^2]=\frac{1}{n}$, and ordering its eigenvalues $\lambda_1\le \lambda_2\le \dots \le \lambda_n$ corresponding ...
  • 136
15 votes
1 answer
636 views

Probability that a random element of a group is trivial

Let $G$ be an infinite group with a finite generating set $S$. For $n \geq 1$, let $p_n$ be the probability that a random word in $S \cup S^{-1}$ of length at most $n$ represents the identity. Is it ...
  • 153
0 votes
1 answer
62 views

Is the departure process of an infinite server queue independent of the arrival process?

Assume we have a $M/M/\infty$ queue with arrival rate $\lambda$ and a service rate $\mu$. From Burke's theorem, the departure process of the queue is a Poisson process with rate $\lambda$. However, ...
  • 13
0 votes
0 answers
21 views

Asymptotic distribution/Convergence of vectors of empirical processes

Let $(\Omega,\mathcal F,P)$ be a probability space, and consider two random variables $X,Y:\Omega\rightarrow\mathbb R$. Let $X_1, X_2,\dots, X_n$ and $Y_1, Y_2, \dots, Y_m$ each be iid copies of $X$ ...