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