# 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,500
questions

**4**

votes

**0**answers

130 views

### Tight bounds for finite de Finetti's theorem

de Finetti's theorem roughly states that infinite sequence of exchangeable random variables are conditionally independent. I am looking for tight bounds for de Finetti's theorem in the following ...

**0**

votes

**2**answers

83 views

### Lower bounds on discrete time finite Markov chains hitting probabilities

I am interested in some general theorems related to lower bounds on discrete time finite Markov chains hitting probabilities (preferably ergodic chains , but not necessarily ), with references . ...

**5**

votes

**0**answers

87 views

### Discrepancy of the finite approximation of the Lebesgue measure

Let $\mu$ be a probabilistic measure on the unit square $Q$ which is the average of $N$ delta-measures in some points in this square; let $\lambda$ denote the Lebesgue measure on $Q$. What is the rate ...

**4**

votes

**1**answer

108 views

### Expectation of maximum of multivariate Gaussian

Given a multivariate Gaussian $\mathbf{X} \sim \mathcal{N}(\mathbf{\mu},\Sigma)$, I believe it is a difficult question to find a closed form for $$ \mathbb{E}[ \max\{X_1,\ldots,X_d\}].$$
However, the ...

**5**

votes

**1**answer

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

**3**

votes

**1**answer

145 views

### Spectral radius of Markov averaging operator on graphs

The definition of Markov operator which I am familiar with:
For a graph $G=(V,E)$, Markov's operator upon a function
$\varphi:V\rightarrow\mathbb{C}$ , $\varphi\in L^2(G,\nu)$ ($\nu(v):=\deg(v)$) ...

**0**

votes

**1**answer

111 views

### Supremum of log(E[X]]-E[log(X)]

I've been tackling some questions on probability theory and got stuck on this one.
Determine $$\sup_{1≤X≤b} \ \log(E[X])-E[\log(X)]$$ where $X$ is a random variable defined in $[1,b]$. In other words,...

**11**

votes

**1**answer

340 views

### Growing a chain of unit-area triangles: Fills the plane?

Define a process to start with a unit-area equilateral triangle,
and at each step glue on another unit-area triangle.
$50$ ...

**1**

vote

**0**answers

63 views

### Showing that additive Gaussian noise never increases sparsity

Let $\mathbf{1}\in\mathbb{R}^d$ be the $d$-dimensional all-ones vector and let $n\sim\mathcal{N}(0, \sigma^2 I_{d\times d})$, show that
$$ \frac{\| \mathbf{1} + n \|_1}{\|\mathbf{1} + n \|_2} \ge c \...

**1**

vote

**0**answers

33 views

### Convergence of regression coefficients to probability density

By simulation we create a vector $Y = (y_1,y_2,...,y_n)$, where each $y_i \in R$ is independently drawn from a given non-degenerate distribution.
Next we create by simulation a vector $\xi = (\xi_1,\...

**3**

votes

**1**answer

81 views

### Expected value of a random variable conditioned on a positively correlated event

I have a random variable $x \in [a, b]$ with PDF $f(x)$ and an event $E$ which satisfies the following property for any $x'<b$.
$$\Pr[E\mid x > x'] \geq \Pr[E]$$
My question is whether or not ...

**1**

vote

**1**answer

94 views

### Can we order random variables in a measurable way in a general setup?

Let
$(\Omega,\mathcal A,\operatorname P)$ be a probability space
$(E,\mathcal E)$ be a measurable space
$n\in\mathbb N$
$X_1,\ldots,X_n$ be $(E,\mathcal E)$-valued random variables on $(\Omega,\...

**1**

vote

**1**answer

156 views

### Is there a 1/poly(n) or 1/polylogn upper-bound for this tail bound?

Is there a good tail bound for $\operatorname{P}\!\Bigg[\bigg\vert\dfrac{\sum_{j=1}^n(\sum_{i=1}^n a_{i,j})^2}{n^2} -1\bigg\vert > \epsilon\Bigg]\,,$ where all $a_{i,j}$'s are iid, with $\...

**11**

votes

**1**answer

363 views

### Coincidences between average Catalan tableaux

There are Catalan number $C_n$ of standard Young tableaux of shape $(n,n)$, which we view as $2\times n$ matrices. Denote by $P_n$ the average of these matrices:
$$
P_n \, := \, \frac{1}{C_n} \, \...

**1**

vote

**0**answers

97 views

### Gaussian Integrals over Spheres

I'm after a reference for an integral. In particular, I am looking a way to approximate or calculate the following:
$$ \int \limits_{\| \theta \|_2 = 1} e^{(-(\theta - \mu)^T \Sigma (\theta - \mu))} ...

**6**

votes

**1**answer

98 views

### Restricted independent set of the cycle graph $C_{3n}$

Let $V$ be the vertices of the cycle graph $C_{3n}$. Suppose there is a partition of $V$ into sets of $3$, i.e. $V=\cup_{k=1}^{n}{V_k}$ where $|V_k|=3$ for $k$ in $1..n$.
QUESTION: Is it possible ...

**-2**

votes

**1**answer

57 views

### If $X$ is discrete and $Z,W$ are discrete or continuous, is it always the case that $P(X=x\mid Z) \geq P(X=x\mid Z,W)$? [closed]

Suppose $X$ is discrete and $Z,W$ are discrete or continuous, I am wondering if it is always the case (or at least non-trivially) that
$$
P(X=x\mid Z) \geq P(X=x\mid Z,W)
$$
for all $x\in X$.
It ...

**1**

vote

**1**answer

47 views

### Subsequence density for iid sequence

Given iid sequence of $X_{n}\in N(0,\sigma_{n})$, from the second Borel-Cantelli we find subsequence $\{n_{k}\}_{k\geq 1}$
$$ \sum P[X_{n}\leq c_{n}]=\infty\Rightarrow \{X_{n_{k}}\leq c_{n_{k}}\}~\...

**1**

vote

**2**answers

80 views

### Finite-sample deviation bound of empirical distribution from true distribution

Let $P=(p_1,\ldots,p_k) \in \Delta_k$ be distribution supported on set of size $k$ and let $\hat{P}_n$ be an empirical version of $P$ based on an iid sample of size $n$.
Question
What's a good non-...

**4**

votes

**1**answer

56 views

### Uniform inequality of the form $\text{Proba}(\sup_{v \in [-M,M]^k}|p^Tv-\hat{p}_n^Tv| \le \epsilon_n) \ge 1 - \delta$

Let $M > 0$, $k$ be a positive integer, and $\mathcal V:=[-M,M]^k$. Finally, let $p \in \Delta_k$, (where $\Delta_k$ is the $(k-1)$-dimensional probability simplex) and let $\hat{p}_n$ be an ...

**3**

votes

**0**answers

48 views

### Random Two-Player Asymmetric Game

About half a year ago I asked a question on MSE about a random two player game. At the time, the question received some attention and some progress was made, but was not resolved completely. I have ...

**2**

votes

**1**answer

70 views

### The expectation of partition times needed separate two elements in a set

I met a problem which can be formulated as set partition.
Given a set $S=\{s_1,s_2,...,s_n\}$ having $n$ elements, I want to separate two elements, say $s_1,s_2$, in $S$ by repeatedly using set ...

**7**

votes

**1**answer

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

**4**

votes

**1**answer

145 views

### Information for discovering an item-colour assignment in a combinatorial game

We are given a set $S=\{i_1, i_2, \ldots, i_n\}$ of items and a set $C=\{c_1, c_2, \ldots, c_m\}$ of colours. Each item in $S$ is tinted with one colour $c\in C$. Let $\mathcal{A}$ be the set of all ...

**3**

votes

**1**answer

89 views

### Total offspring of Poisson multitype branching process

A normal branching process $Z_n$ initialized with $Z_0=1$ and offspring generated from $Pois(p),p<1,$ has a total progeny / total off spring distribution
$$X=\sum_{n=0}^\infty Z_n$$
$X\in \mathbb{...

**1**

vote

**2**answers

100 views

### How to use probability to find a matching in a family of graphs?

In a conference, I heard that we can use some probabilistic methods to find a matching in some kind of graphs. I would like to see some examples of such technics. Can someone provide some references ...

**0**

votes

**0**answers

74 views

### Differentiability (Hessian) of $\int \log F$ when $\int \log f$ is differentiable?

For a specific probability density function $f$ with support on ${\mathbb R}$, which is not differentiable everywhere, I have proven that the Hessian matrix of
$$g(\theta) = \int \log f(x;\theta)d H(...

**4**

votes

**0**answers

71 views

### List of Replica Symmetry results for different models?

Does anyone know of a good source that might have a list of problems or models along with what kind of replica symmetry they are conjectured to have?
I am aware of some of the more famous results, e....

**2**

votes

**0**answers

51 views

### Sample $k$ of $n$ numbers (with replacement), what is the probability for a certain from the $n$ numbers to be the median of the $k$ numbers [closed]

Suppose we have ordered numbers $a_1 < a_2 < \dots < a_n$. Now we sample $k$ of them with equal probability and with replacement and compute the median of these and call it $m$. (Let us ...

**4**

votes

**2**answers

250 views

### Convergence of random measure

Suppose that $S$ is a separable metric space or Polish. Let $μ_{n},n∈N $ be a random probability measures and let μ be a deterministic probability measure on $S$. That is to say, that the $ μ_{n}$ are ...

**1**

vote

**0**answers

26 views

### Concentration inequality for Lipschitz functions with orthogonal gradients

Let $f_j:\mathbb{R}^n\to\mathbb{R}$ be a set of 1-Lipschitz functions for $1\leq j\leq M$. From Gaussian isoperimetry or a log-Sobolev inequality, it can be shown that
$$
\mathbf{Pr}(|f_j(X)-\mathbf{...

**2**

votes

**1**answer

87 views

### Heavy tail central limit theorem

I am looking for a proof based on characteristic functions for the generalized central limit theorem when the second moment does not exist, in which case one ends up with a power law rather than a ...

**5**

votes

**1**answer

259 views

### Sum of random variables are equal in distribution

Suppose that $X,Y$ are scalar random variables supported on some standard Lebesgue probability space $(\Omega, \mathrm{P})$, such that $X \overset{\mathrm{d}}{=} Y$ in the sense that their pushforward ...

**4**

votes

**1**answer

212 views

### A balls into bins problem with combinatorial constraints

We are given $m$ balls and $n$ bins, with $m \ge n$. Each bin can contain at most $c$ balls (we assume that $c$ is an even integer). In a sequential fashion, at each time step, one ball is placed into ...

**2**

votes

**1**answer

225 views

### Show that the absolute value of this function is twice differentiable except on a set of Lebesgue measure $0$

Let
$f\in C^3(\mathbb R)$ with $f>0$ and $$\int f(x)\:{\rm d}x=1\tag1$$
$g:=\ln f$ and assume that $g'=\frac{f'}f$ is Lipschitz continuous (note that this implies that $f'(x)\xrightarrow{|x|\to\...

**1**

vote

**0**answers

70 views

### Large Deviation of Triple Poisson Product

Let $X_i$ with $i=1,\ldots,n$ be independent Poisson variables, $X_i$ with parameter $\lambda_i.$
Let $\circ$ be a group operation on a group of size $n.$
I would like to obtain a large deviation ...

**2**

votes

**1**answer

102 views

### Rank of a random sparse matrix with nonnegative reals

I believe this should be some standard result in random matrices theory, but my initial search failed to find a definitive answer.
The question is given a random sparse matrix $M\in\mathbb{R}^{n\...

**1**

vote

**0**answers

91 views

### Entropy of endpoints of a random walk in a dense graph

Let $p\in[0,1]$ be a constant and let $G$ be a graph with $n$ vertices and $\approx p\binom{n}{2}$ edges. If you'd like, consider $p=1/2$.
Let $X$ be a random vertex of $G$ chosen proportional to ...

**2**

votes

**1**answer

147 views

### Estimating probability that a large sum of i.i.d variables is positive

Let $X$ and $Y$ be i.i.d. random variables with exponential distribution with mean $1$, and let $Z=(X-1)(Y-X)$. Let $Z_1,...,Z_n$ are i.i.d. copies of $Z$, and let $f(n)=P[\sum_{i=1}^n Z_i > 0]$. ...

**1**

vote

**1**answer

112 views

### Random optimization problem

Let $V$ be a set of $n$-dimensional vectors such that, for each ${\bf v}\in V$ and for each index $i\in [n-1]$, we have $0\le v_{i+1}\le v_i$. Let $P(\cdot)$ be a discrete probability distribution ...

**0**

votes

**0**answers

31 views

### A modification of Kolmogorov's continuity criterion for $C_{tem}$

I am wondering about how to prove a modification of Kolmogrov's continuity criterion in order to also being able to quantify the growth behaviour of the process. In particular, I am interested in the ...

**1**

vote

**1**answer

318 views

### Taylor's theorem for a composition with $\min:\mathbb R^2\to\mathbb R$ and differentiability Lebesgue almost everywhere

Let
$f\in C^3(\mathbb R)$ with $f>0$ and $$\int f(x)\:{\rm d}x=1$$
$g:=\ln f$ (and assume $g'$ is Lipschitz continuous)
$n\in\mathbb N$, $$s(x,y):=\sum_{i=1}^n\left(g(y_i)-g(x_i)\right)$$ and $$h(...

**4**

votes

**1**answer

67 views

### Linear combination of coordinates of random unit vector

Let $v\in \mathbb{R}^n$ be uniformly distributed on the unit sphere. Let $\lambda_1,...,\lambda_n$ be given real numbers. What is the distribution of
$$X=\sum_{i=1}^n\lambda_iv_i^2\;?$$
Does it happen ...

**2**

votes

**1**answer

111 views

### Density of random matrix only depends on its spectrum

Suppose a random positive definite matrix $A\in\mathbb{R}^{n\times n}$ has density function (with respect to the lebesgue measure on $\mathbb{R}^{n(n+1)/2}$) $f(A)=g(\lambda_1(A),...,\lambda_n(A))$ ...

**1**

vote

**0**answers

72 views

### Joint distribution of two weighted sums of IID random variables

Let $X_1, X_2, \dots$ be independently uniformly distributed random variables in $\{-1, +1\}$ and let $a_1, b_1,a_2,b_2, \ldots \in \mathbb{R}$ be fixed, bounded and of non-zero average. Let $Y_n=...

**2**

votes

**1**answer

54 views

### Is independence preserved if a random entry in an independent sequence is replaced by a constant?

Let $\xi=(\xi_1,\ldots,\xi_n)$ be a sequence of independent random variables.
Let us pick an index $\nu\in \{1,\ldots,n\}$, and replace the entry $\xi_\nu$ by a constant $c$. The rest of the $\xi_i$ ...

**1**

vote

**1**answer

185 views

### If $g$ is differentiable, how can we show that $z\mapsto1\wedge e^{g(z)}$ is differentiable except on a countable set

If $g:\mathbb R\to\mathbb R$ is differentiable, how can we show that $$h(z):=\min\left(1,e^{g(z)}\right)\;\;\;\text{for }z\in\mathbb R$$ is also differentiable, except at a countable number of points, ...

**0**

votes

**0**answers

46 views

### Conditional Expectation of Composite Function

Preliminaries
Let $(\Omega, \mathcal{G}, \mathbb{P})$ be a complete probability space.
Let $D$ be a complete, separable, metrizable topological space with Borel $\sigma$-algebra $\mathcal{B}(D)$ (...

**2**

votes

**0**answers

42 views

### Given a set of marginals, what is the largest support of a distribution satisfying these?

Given a random variable $X$ with support over $\{0,1\}^I$, we can define the marginal distribution on the bits indexed by $A \subseteq I$ by $Pr(X_A = x_A) = \sum_{x \in \{0,1\}^{I - A}} Pr(X = x \cup ...

**0**

votes

**1**answer

77 views

### Correlation between square of normal random variables

Suppose I have $X,Y$ bivariate normal with correlation coefficient $\rho \in (0,1)$ . Then , what is the correlation between $X^2 $ and $Y^2$ ?
I am aware of the fact that the square of the normal ...