Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
4answers
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
3answers
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
1answer
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
1answer
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
3answers
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
2answers
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
1answer
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
1answer
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
0answers
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
0answers
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
3answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
3answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
3answers
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
0answers
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
1answer
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
2answers
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
3answers
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
2answers
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
1answer
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
1answer
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}, ...