# 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.

5,175 questions

**0**

votes

**0**answers

25 views

### (Upper) bounding the MGF of a semi-decoupled non-homogeneous Rademacher chaos of order 4

Let $(\xi_i)_{1\leq i\leq n}$, $(\xi'_i)_{1\leq i\leq n}$ be two independent vectors of independent Rademacher random variables, and
$(a_{ij})_{1\leq i,j\leq n}$, $(b_{ijk})_{1\leq i,j,k\leq n}$, $(c_{...

**2**

votes

**1**answer

132 views

### non-backtracking random walk in regular (finite) graphs

I know that many things are known when dealing with random walks on a finite (or even infinite) graph: mixing time, returns to origin, etc. All is based in the use of the Markovian property of such a ...

**1**

vote

**1**answer

120 views

### Expected value of sin(X) for Gamma r.v. X in closed form (approximation is fine)

I have a random variable $X \sim \operatorname{Gamma}(\alpha, \beta)$.
How can I compute or approximate $\mathbb{E} \sin(X)$ very quickly? Iterative quadrature would be too slow, I need some closed ...

**4**

votes

**1**answer

143 views

### Component properties in Euclidean graphs with distance threshold

In the context of Euclidean graphs with vertices randomly embedded in either a 2D plane (for instance square with length $L$) or in 3D (similarly, cube of side $L$), where an edge between two given ...

**0**

votes

**0**answers

87 views

### Is there a probabilistic proof/interpretation of Mergelyan Theorem

I came across Mergelyan's Theorem:- Let K be a compact subset of the complex plane C such that C∖K is connected. Then, every continuous function $f : K \to C$, such that the restriction f to int(K) ...

**2**

votes

**0**answers

139 views

### Sum of Gaussian matched by Brownian Motion?

Given independent Gaussian $d$ dimensional vectors $G_i$,
If $\mathbb{E}(\sum_{i \le n} G_i) \cdot (\sum_{i \le n} G_i)^T=n \cdot I_{d \times d} + o(n^{1-\epsilon})$.
there exists Brownian motion $...

**1**

vote

**0**answers

38 views

### Probability estimate with a Lipschitz, weak* semicontinuous function on the $\ell^\infty$ unit ball

Suppose that $X_i$ for $i=0,1,\dots$ is an i.i.d. sequence of uniformly distributed random variables taking on values in $[-1,1]$. Fix a real number $L>0$ and suppose that $f_n:[-1,1]^n\rightarrow [...

**6**

votes

**4**answers

299 views

### Improvement of Chernoff bound in Binomial case

We know from Chernoff bound
$P\bigg(X \leq (\frac{1}{2}-\epsilon)N\bigg)\leq e^{-2\epsilon^2 N}$ where
$X$ follows Binomial($N, \frac{1}{2}$).
If I take $N=1000, \epsilon=0.01$, the upper bound is ...

**13**

votes

**3**answers

752 views

### Probability of commutation in a compact group

It is well known that if $G$ is a finite group, then the probability that two elements commutte is either $1$ (if $G$ is abelian) or less than or equal to $\frac58$.
If instead $K$ is a compact group,...

**0**

votes

**1**answer

33 views

### Right tail decay of F distribution [closed]

Suppose $X\sim F(a,b)$. Is there any sharp upper bound of the following probability with large $x$?
$$\mathbb{P}(X\geq x)$$
what is the order of the above probability as $x\to+\infty$?

**-1**

votes

**1**answer

71 views

### Expected value of $W_{t_i} W^2_{t_{i+1}}$

I stuck in determining the expected value of the following product
$E[W_{t_i}W_{t_{i+1}}^2]$ where $W_{t_i}$ and $W_{t_{i+1}}$ are Brownian with normal distribution, i.e. $W_{t_i}\sim N(0,t_i)$. I ...

**3**

votes

**3**answers

188 views

### What is the probability distribution of the $k$th largest coordinate chosen over a simplex?

Suppose we're selecting points uniformly at random from the $N$-simplex
$S_N = \{x \in \mathbb R^{N+1}: $ all $ x_i \ge 0$ and $x_1 + \ldots x_N = 1\}$.
One way to do this in practice is choose $N-...

**1**

vote

**2**answers

123 views

### lower bound the probability of at least L collisions

Lets say we get a list $M$ containing $|M|=\sqrt{L\cdot N}$ randomly and independtly drawn elements from a set of size $N$. And lets denote the $i$-th element of the list $M$ by $M[i]$.
If we now ask ...

**5**

votes

**1**answer

96 views

### What is the expected value of the submeasure of a random set?

Let $N \in \mathbb N$ and suppose that $\phi$ is a submeasure on $[1,N] = \{1,2,\dots,N\}$, by which I mean that $\phi$ is a function $\mathcal P ([1,N]) \rightarrow \mathbb R$ such that
i. $A \...

**2**

votes

**1**answer

72 views

### Controlling Mean Difference Between Product and Joint Distributions Using Optimal Transportation

Suppose we have nonindependent random variables $X \sim P$ and $Y \sim Q$, where $P$ and $Q$ denote their marginal distributions. We are interested in upper bounding
$$
|\mathbf{E}_{X, Y\sim P \...

**4**

votes

**0**answers

221 views

### What is the category of algebras for the finitely supported measures monad?

In this post, I was introduced to the monad of finitely supported measures.
$HX$ is the set of finitely supported measures on $X$, with monad structure defined as for the Giry monad.
I have three ...

**3**

votes

**0**answers

105 views

### Galton Watson tree with various kinds of offspring

As far as I understood, for the Galton-Watson tree process, the offspring are of one type. I am thinking of the case where we have offspring of different types. I have illustrated this in the example ...

**12**

votes

**3**answers

498 views

### A Modern Proof of Erdos and Renyi's 1959 Random Graph Paper?

In their paper, Erdos and Renyi consider a random graph with a fixed number of edges, as opposed to the more modern approach of adding each edge independently with probability $p$. From what I ...

**3**

votes

**1**answer

116 views

### Log concavity of the maximum of dependent Gaussians

Let $Z_1,\dots,Z_n$ be dependent Gaussian random variables. Is it true that $X=\max\{Z_1,\dots,Z_n\}$ has a log-concave distribution function? This is true for the independent case, but is it true in ...

**2**

votes

**0**answers

42 views

### Convergence to the probability generating function of a Poisson process

I'm working currently with a Poisson process trying to proove Renyi's Theorem, so far I want to show that
$\prod_{i=1}^{k_n}[z + (1-z)e^{-\mu(A_{n_i})}] \to e^{-(1-z)\mu(A)}$ as $\mu(A_{n_i}) \to 0$, ...

**5**

votes

**1**answer

495 views

### What is the six positive real number for a dice producing a highest chance?

Say there is a dice with six faces, each face has a positive real number different from others. There is a chessman on the origin of the number axis. In each trial, the dice rolls infinite times. ...

**2**

votes

**1**answer

92 views

### Convergence of a stochastic sequence?

I am reading this paper related to an algorithm for nonsmooth optimization problems. After many simplifications, I was able to formalize the method as follows: let $\Bbb B $ denote the unit ball in $\...

**0**

votes

**1**answer

116 views

### Is the normal product distribution sub-gaussian?

Consider the normal product distribution, which is the distribution of the product of two or more independent normal variables. Particulary, focus in the case where the multiplied normal variables are ...

**1**

vote

**0**answers

51 views

### A Random Graph Process

I'd like to understand the following random graph process. I'm not sure if it's difficult or straightforward, so apologies if this is below the level of mathoverflow, but I've gotten no response on ...

**3**

votes

**1**answer

143 views

### Why does the assumption $|U_t| \le \frac1{p_{\min}}$ work in this paper?

I am reading a 2009 paper right now "Importance Weighted Active Learning" and on page 5, there is a theorem that uses the inequality $|U_t| \leq \frac{1}{p_{\min}}$. I am not sure how the paper found ...

**1**

vote

**0**answers

74 views

### Schilder's theorem for brownian bridges

I am really not a probabilist and I apologize if my question is too naive or not appropriate, please feel free to migrate to SE.
A bit of context: usually, Schilder's theorem tells us that the ...

**3**

votes

**1**answer

117 views

### Tail probability of random projection

Suppose $v\in R^n$ is a constant unit vector. $P_l$ is a random projection matrix to an $l$ dimensional subspace of $R^n$ which is uniformly sampled from $G(l,R^n)$ which is the collection of all $l$-...

**3**

votes

**1**answer

138 views

### Universal decay rate of the Fisher information along the heat flow

I'm looking for a reference for the following fact: In the torus $\mathbb T^d$ let me denote by $u_t=u(t,x)$ the (unique, distributional) solution of the heat equation
$$
\partial_t u=\Delta u
$$
...

**5**

votes

**0**answers

140 views

### Characterization of KL divergence for continuous variables?

This is an analog of an older question:
What characterizations of relative information are known?
With the modification that I’m interested in the case when the distribution is over something that’s ...

**1**

vote

**0**answers

55 views

### Negative association in a “k out of n” process

Suppose we have $n$ distinct balls labeled $1,2,\dots,n$ in a black box. Now we want to fetch $k$ balls from the box, one by one. Let event $E_i$ be that the label of the $i$-th ball we fetch is no ...

**6**

votes

**0**answers

131 views

### What is known about the distribution of lengths of the cycle you get by adding an edge to a uniform spanning tree?

Let $G$ be a finite, connected graph. Let $T$ be a uniform spanning tree, and let $e$ be a uniformly random edge not in $T$. When we add $e$ to $T$, we get a subgraph with a unique cycle, $C$. I am ...

**3**

votes

**0**answers

63 views

### Convergence of SDEs

Suppose that $\{a_n(x)\}_{n \in \mathbb{N}}$ is a sequence of real-valued Lipschitz functions with domain $\mathbb{R}^d$, which converges $m$-a.e. to a Lipschitz function $a$. Suppose that $b$ is a ...

**0**

votes

**1**answer

63 views

### Bivariate Poisson-Binomial distribution

Suppose you have $100$ coins whose probabilities of obtaining the outcome "head" are $p_1,\ldots,\,p_{100}$. These probabilities are not necessarily equal each other. Consider the following random ...

**4**

votes

**0**answers

112 views

### Spectral gap for the Brownian motion with drift on a compact manifold

Let $M$ be a compact Riemannian manifold without boundary, $X$ a smooth vector field on $M$. Consider the Brownian motion $t\mapsto B_t$ on $M$ with drift $X$, so that its generator is $L=\Delta +X$. ...

**2**

votes

**1**answer

45 views

### Convergence of $\sup_{l \leq \rho \leq u} | \frac{1}{\sqrt{n}} \sum_{i=[\rho n]}^n \sum_{k=1}^i i^{-1} x_i y_k |$ in probability to zero

I am dealing with a sequence $\{(x_i,y_i)\}$ of zero-mean random variables. For simplicity we can assume that the sequence is i.i.d. Define $Y_i := i^{-1} \sum_{k=1}^i y_k$. I would like show that
\...

**6**

votes

**3**answers

349 views

### Connections between martingales and Fourier analysis

I have had this strange feeling recently that somehow, the theory of martingales we study in probability, and the theory of Fourier analysis are very alike. But I am not able to formalize my thoughts.
...

**1**

vote

**0**answers

89 views

### Closed-form formula for Wasserstein distance between uniform discrete distribution and discrete distribution with same support

Let $x_1,\ldots,x_n$ be $n \ge 1$ distinct points in $\mathbb R^d$ and consider two discrete distributions on these points $\mu = (1/n)\sum_{i=1}^n\delta_{x_i}$, and $\nu = \sum_{i=1}^n\nu_i\delta_{...

**7**

votes

**1**answer

302 views

### The probability that two elements of a finite nonabelian simple group commute

It is mentioned in here (last paragraph of the first page) that Dixon proved the following result: the probability that two elements of a finite nonabelian simple group commute is at most $\frac{1}{12}...

**2**

votes

**0**answers

83 views

### Covering a sphere with ellipsoid-products in high dimension

For $\Sigma\geq 0$ a $k\times k$ matrix and large $n$, fix $E:= \{(x_i)_{i=1}^n: \sum_i x_i^\dagger \Sigma x_i \leq n\}$. Fix $(z_m)_m$ as $M$ points iid uniform on $\mathbb{S}^{nk-1}\subset \mathbb{...

**2**

votes

**1**answer

83 views

### Tail condition (Varadhan's lemma)

I would like your help with the following tail condition, which arises in the theory of large deviations.
Let $P(\mathbb{R}^{d})$ the space of probability measures on $\mathbb{R}^{d}$, $ G:P(\mathbb{...

**1**

vote

**0**answers

27 views

### Vertical and horizontal percolation on heterogeneous honeycomb lattice

I have a regular honeycomb lattice where a bond in the unit cell aligns with $(1,0)$; call this the horizontal direction. Each horizontal bond in the lattice is open with probability $p$ and each "...

**4**

votes

**1**answer

201 views

### Map from the Multiset Monad to the Giry Monad: From Data to Probabilities

The Mulitiset monad, aka the free commutative monoid monad or "Bag" monad, takes a set to the set of all Multisets for that set. A Multiset is like a set, but can have duplicates. It is used in ...

**10**

votes

**3**answers

561 views

### Entropy and total variation distance

Let $X$, $Y$ be discrete random variables taking values within the same set of $N$ elements. Let the total variation distance $|P-Q|$ (which is half the $L_1$ distance between the distributions of $P$ ...

**1**

vote

**0**answers

49 views

### Existence of Time-Reversed Markov Kernels

Suppose I have a probability measure $\pi$ and a Markov kernel $q$ which leaves $\pi$ invariant, in the sense that
\begin{align}
\int_x \pi(dx) q(x \to dy) = \pi(dy)
\end{align}
Then, a (the) time-...

**0**

votes

**1**answer

115 views

### Does log-concave approximable distribution satisfy transportation-cost inequality?

Definition: Recall that a distribution $\mu$ on $\mathbb R^d$ is said to be log-convave with constant $c > 0$, if density $d\nu \propto e^{-V}dvol$ satisfying the curvature condition
$$
\...

**3**

votes

**2**answers

64 views

### Left tail of convex combinations of $\chi_1^2$

Suppose $a_1,...,a_n\geq0, \sum_{i=1}^na_i=1$ and $Z_1,...,Z_n$ are i.i.d. standard normal, what is a sharp upper bound of the following probability as $\delta\to0$ and what is the order?
$$\mathbb{P}(...

**1**

vote

**3**answers

115 views

### Distribution of x1/(x1+x2) with x1 and x2 being 2 uniformly distributed random variables [closed]

Let $X_1$ and $X_2$ be two uniformly distributed random variables on [0,1].
What is the statistical distribution of the ratio
$\frac{X_1}{X_1+X_2}$ ?
Same question with 3 variables $X_1$, $X_2$ and $...

**4**

votes

**2**answers

279 views

### The probability density function of the number of coins to first fill one box of $N$

Given $N$ boxes with the same capacity $C$, I toss coins into the boxes uniformly, one by one. When any one of the boxes is full, the sum of the coins in all boxes is denoted $S$. How to compute the ...

**2**

votes

**1**answer

191 views

### A modest generalization of the law of large numbers

Suppose I collect $2n$ independent samples of a probability density function $f$, which are separated into pairs $\{X_i^1, X_i^2\}$ for $1\leq i\leq n$. Suppose I now consider the set of all $2^n$ ...

**2**

votes

**1**answer

95 views

### time delay ergodic theorem

given dynamic system $(X, \mathcal{B}, F, \mu), \mu \circ F^{-1}=\mu, F $ is mixing, $ A \in \mathcal{B}, s.t. \mu(A) >0 $.
consider dynamic system $(X\times X, \mathcal{B}\otimes \mathcal{B}, ...