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.
920 questions
7
votes
1
answer
757
views
Length of nearest neighbor path in travel salesman problem
Given $n$ nodes uniformly distributed in $[0,1]^2$, consider the nearest neighbor algorithm to solve traveling salesman problem, i.e., each time I select the nearest neighbor not visited so far as the ...
- 367
7
votes
0
answers
497
views
Extreme unitary minimal models of conformal field theory
Some of the best understood conformal field theories are the 2D unitary minimal models $\mathcal{M}(m+1,m)$ indexed by the integer $m\ge 2$ and with central charge
$$
c=1-\frac{6}{m(m+1)}\ .
$$
I ...
7
votes
1
answer
499
views
Moments of a random variable and of its conditional expectation
Let $X$ be a bounded random variable with $\mathbb{E}X=0$. Since $X$ is bounded, all its moments exist. Let $\mathcal{G}$ be any $\sigma$-field and let $Y:=\mathbb{E}[X|\mathcal{G}].$ I am interested ...
- 1,269
7
votes
1
answer
3k
views
The question about Kolmogorov tightness criterion
We know about Kolmogorov Criterion for the tightness of a stochastic process $X_n(t)$
1.The sequence $(X_{n}(0))_{n\geq0}$ is tight.
2.There exist constants $\gamma\geq0$,$\alpha>1$, $K>0$ and ...
- 71
7
votes
5
answers
682
views
Bound on sum of complex summands involving binomial coefficients
I am trying to find the asymptotic behavior of the sum:
$$ \sum^n_{i=0} \begin{pmatrix} 2n \\ i \end{pmatrix} x^i y^{2n-i}$$
as $n\rightarrow\infty$. Here $x$, $y$ are complex numbers and I have $|x|...
- 93
7
votes
3
answers
6k
views
Concentration results for inner products of two independent random gaussian vectors
Hi,
I wanted to know if there are standard results on concentration of absolute
value of inner products of two random vectors. Thus if $X, Y \in R^m$ are two
independent random vectors with each ...
- 71
6
votes
1
answer
349
views
Ramsey type theorem
Let $\mathcal{P}(\{0,\dotsc,7\})$ denote the power set of $\{0,\dotsc,7\}$.
Is the following true?
For any function $f: \mathcal{P}(\{0,\dotsc,7\})\rightarrow\{0,1\}$ there exists $0\leq k\leq 3$ ...
- 909
6
votes
2
answers
1k
views
Do binary symmetric channels maximize mutual information?
Consider the following setup: $(X, Y)$ is a doubly symmetric binary source with parameter $0 < p < 1/2$, i.e., $X \sim \text{Bernoulli}(1/2)$, $Z \sim \text{Bernoulli}(p)$ and $Y = X \oplus Z$. ...
6
votes
0
answers
300
views
A natural fragmentation process
Starting from the length-1 list whose only entry is 1, iterate the process of replacing the last (and largest) entry in the list of length $n$ (call that entry $m$) by the two numbers $mU_n$ and $m(1-...
- 19.7k
6
votes
1
answer
375
views
Deviation bound for the maximum of the norm of Wiener process
Let $W(t)$ be an $n$-dimensional Wiener process. Denote by $\chi_n^2$ a chi-squared random variable with $n$ degrees of freedom. I have recently found the following inequality given without proof:
$$
{...
- 61
6
votes
2
answers
5k
views
Can I relate the L1 norm of a function to its Fourier expansion?
I would like to express the integral of the absolute value of a real-valued function $f$ (over a finite interval) in terms of the Fourier coefficients of $f$. Failing that, I would like to know of any ...
- 185
6
votes
1
answer
1k
views
About the generating structure of Borel field
This is a graduate-level measure theory problem. I have thought throught it and asked on math.SE but received no satisfying answer.
On P.32 of [P.Billingsley] Probability and Measure, 3ed, 1993, the ...
- 8,071
6
votes
1
answer
333
views
Lower bound for probability of getting exactly one head with pairwise independence
Say we toss $d$ pairwise independent coins, each with probability $1/d$ of getting a head. What is the highest lower bound one can give for the probability of getting exactly one head?
If they had ...
- 3,377
6
votes
1
answer
392
views
Does $E^{x,t}(f(X_T))$ solve a PDE if $f$ is not continuous?
Many books [see below for references] explore the connections between partial differential equations and expectation values.
Assume $X$ is a diffusion with generator $A$, then they conclude, that ...
- 237
6
votes
1
answer
883
views
Random walk with positive uniformly distributed steps
Let $U_1,U_2,\ldots$ be iid random variables distributed uniformly on $[0,1]$. I am interested in the random walk $X_i = \sum_{j \leq i} U_j$. In particular,
What is the expected number of points ...
- 1,906
6
votes
2
answers
293
views
Expectation of the inner product of a subset of two random orthonormal vectors
Setting: Consider sampling two orthonormal vectors $\mathbf{u},\mathbf{v}$ in $\mathbb{R}^p$ (where $p\ge2$) from a "uniform" distribution over the $p$-dimensional sphere (alternatively, ...
- 673
6
votes
0
answers
1k
views
Relationship between R-transform and free convolution of random matrices?
I've been using the R-transform to calculate the free convolution of the eigenvalue spectra of two random matrices and I am trying to understand how it works, and in particular how it relates to ...
- 1,890
6
votes
1
answer
1k
views
Is there a McDiarmid-type inequality for sequences with a finite range of dependence?
Let $X, X_1, X_2, \ldots, X_N$ be a sequence of identically distributed random variables with $0 \leq X \leq 1$.
We do not assume the sequence is iid, but rather allow the random variables to be ...
- 2,155
6
votes
4
answers
614
views
Number of intervals needed to cross, Brownian motion
Let $B_t$ be a standard Brownian motion. Let $E_{j, n}$ denote the event$$\left\{B_t = 0 \text{ for some }{{j-1}\over{2^n}} \le t \le {j\over{2^n}}\right\},$$and let$$K_n = \sum_{j = 2^n + 1}^{2^{2n}} ...
user80013
6
votes
3
answers
938
views
Uniformly distributed sequence in $\mathbb{R}$
We say that a sequence $(x_n)_{n=1}^\infty \subseteq \mathbb{R}$ is "uniformly distributed in $[a,b]$", with $a < b$, if $(x_n)_{n=1}^\infty \cap [a,b] \neq \varnothing$ and
$$\lim_{N \to \infty} \...
- 61
6
votes
1
answer
798
views
Prohorov's theorem for random elements of Hilbert space: weak convergence
Let $(\Omega,\mathcal{F},P)$ be a probability space and let $(E,\mathcal{E})$ be a separable Hilbert space ($E$) with Borel $\sigma$-algebra $\mathcal{E}$. For concreteness let us set $E=L^{2}[a,b]$ ...
- 61
6
votes
0
answers
295
views
Dimension-free sample complexity for estimating Gaussian covariance
(also asked on math.se, with no answers)
Suppose I have $m$ samples drawn from a Gaussian in $\mathbb{R}^n$, and need sample covariance $\Sigma_m$ to be $\epsilon$-close to true covariance $\Sigma$:
$$...
- 2,252
6
votes
2
answers
413
views
Random walk in a convex body or convex polytope
Let $\Delta$ be a convex body (i.e. a compact convex subset) or a convex polytope in
$\mathbb{R}^n$. Let $x$ be a point inside $\Delta$ and consider a (uniform) random walk starting at $x$ inside $\...
- 893
6
votes
2
answers
2k
views
Is the Binomial Expectation of Convex Function Convex in p?
Suppose $X$ has a binomial distribution with success probability $p$ and $n$ trials and let $h(\cdot)$ be a positive convex real-valued function.
Is the function $g(p)=\mathbb{E}[h(X)\ |\ p]$ convex ...
- 103
6
votes
3
answers
447
views
Isoperimetric inequality for $\epsilon$-expansion of a set only along a certain subspace
Let $\gamma_n$ be the standard gaussian distribution on $\mathbb R^n$. Let $V$ be a $k$-dimensional subspace of $\mathbb R^n$. Finally let $A$ be any (nonempty) Borel subset of $A$ with $\gamma_n(A) = ...
- 6,853
6
votes
1
answer
2k
views
Topological conditions of Kolmogorov Extension Theorem
KET is often used to construct stochastic processes in continuous time when the state space is $\Bbb R^d$. As far as I am familiar with its proof, it uses standard monotonic class-like arguments ...
- 1,655
6
votes
1
answer
1k
views
How to check if a symmetric random variables is the difference of two iid symmetric random variables
I have the continuous symmetric random variable $X$ in $\mathbb{R}$. If I know its distribution function $F(x)$ what are the conditions on $F(x)$ so that $X=Y_1 - Y_2$ where $Y_i$ are also iid ...
6
votes
2
answers
497
views
Average distance of the mean of $n$ random complex numbers in a unit disc
Let $z_1,z_2,\dots,z_n$ be $n$ complex numbers distributed uniformly and randomly over the unit disc $x^2+y^2 \leq 1$. Let $z$ be the complex number defined by the mean of the of these numbers,that ...
- 826
6
votes
2
answers
756
views
Kolmogorov vs Ionescu-Tulcea extension theorem (again)
Disclaimer. This post is not a duplicate, I have carefully (best I could) read all posts on the subject both here and on math.se and my particular questions have not been asked there.
I've recently ...
- 620
6
votes
1
answer
269
views
Algebraization of Bayesian networks?
The algebraization of classical propositional logic is Boolean algebra.
Bayesian networks are a generalization of classical propositional logic with probability truth-values.
What is the ...
- 558
6
votes
4
answers
3k
views
Calculating the probability of an event defined by a condition on a Gaussian random process
Although the question itself can be expressed succinctly, I couldn't come up with a nice self-explanatory title - suggestions are welcome.
Motivation/Background
I was investigating whether it would ...
6
votes
3
answers
999
views
Does there exist an almost surely differentiable martingale?
Does there exist a continuous time martingale $X_t$ not a.s. constant in $t$ that is almost surely everywhere differentiable?
- 6,223
6
votes
1
answer
196
views
Simultaneous simulation of all probability measures on a compact metric space
A well known fact in probability is that a uniform random variable on $[0,1]$ can be used to simulate any other probability distribution on $\mathbb{R}$.
A standard way of doing this is to define, ...
- 4,304
6
votes
2
answers
202
views
Bound on the joint distribution of three real random variables with given two dimensional marginals
Let $X,Y,Z$ be real r.v. with $(X,Y)$, $(Y,Z)$ and $(Z,X)$ centered unit normal. How large can $\mathbb E (XYZ)$ be?
- 3,085
6
votes
1
answer
837
views
Average minimum number of random k-sparse vectors in GF(2) to span the whole space?
What is the average minimum required number of independent $k$-sparse (having at most $k$ non-zero elements) random vectors belonging to $\mathbb{F}_2^n$ to span the whole space of $\mathbb{F}_2^n$? ...
- 307
6
votes
1
answer
642
views
Bochner-Minlos for moment-generating functions?
It is well-known that the Bochner-Minlos theorem characterises measures on duals of nuclear spaces by their characteristic functions. Is there a similar version for moment-generating functions?
I have ...
- 651
6
votes
0
answers
321
views
extensions of the Nekrasov-Okounkov formula
This post is related to the issues addressed in
A q,t-extension of Plancherel Measure thru Yang-Mills Theory ?
however the generalization/interpolation which John Mangual asks for looks different ...
- 2,137
6
votes
1
answer
3k
views
Minimum Hamming Distance Distribution in a Random Subset of Binary Vectors+
Select $K$ random binary vectors $Y_i$ of length $m$ uniformly at random.
Let the following collection of random variables be defined: $X_{i,j}=w(Y_i \oplus Y_j)$ where $w(\cdot)$ denotes the Hamming ...
- 10.4k
6
votes
1
answer
264
views
Which orthant probabilities are the largest? (For a multivariate normal distribution)
I have a $k$-dimensional multivariate normal distribution $X∼N(0,\Sigma)$ with covariance matrix $\Sigma$. $\Sigma$ has two distinct eigenvalues, say $\lambda_1 > \lambda_2$, with orthogonal ...
6
votes
3
answers
13k
views
Probability of one binomial variable being greater than another.
I need to calculate (or bound) the probability that one binomial variable is greater than other. Specifically, if $x \leftarrow B(n,p)$ and $y \leftarrow B(n,q)$, what is the probability that $y \...
- 73
6
votes
1
answer
847
views
Publishing an elementary proof of a less-general and less-useful version of a classic result?
Background
Let $X_t$ be a stochastic process on the state space {Working, Broken}. Let $U$ be the cumulative sojourn Working during an interval $[0,\tau]$ (the process's uptime). It is well-known [1]...
- 290
6
votes
1
answer
170
views
Probabilities of small balls with convergent center points under Gaussian measure
I'm in the following situation:
Consider a centred Gaussian measure $\mu_0$ on a separable Hilbert space $X$ with covariance operator $Q \in \mathcal{L}(X)$ (positive definite, self-adjoint, trace ...
- 61
5
votes
1
answer
275
views
Is there a good notion of "random bounded linear map" on a separable Hilbert space?
Let $H$ be a separable Hilbert space and let $\{e_i\}$ be an orthonormal basis. My first question is:
Is there a probability measure on $B(H)$ such that for $T$ chosen uniformly randomly the ...
- 29.2k
5
votes
0
answers
797
views
How many balls should we throw into $m$ bins so that at least $k$ bins get at least $r$ balls, with probability $1-\delta$?
Let $m,k,r\in\mathbb N$ and $\delta\in(0,1)$, such that $k\le m$.
Suppose that we throw balls uniformly and independently into $m$ bins.
I am looking for an upper bound $N_{m,k,r,\delta}$ on the ...
- 51
5
votes
4
answers
395
views
Concentration of closed random walks
Consider a random walk $S_n=\sum_{i=1}^n X_i$ where $P(X_i=+1)=P(X_i=-1)=1/2$ with $n$ large. By Chernoff's bound we know that, for example, $\sum_{i=1}^{n/2} X_i=O(\sqrt{n})$ with high probability.
...
- 470
5
votes
0
answers
2k
views
What exactly is the relationship between Donsker-Varadhan variational formula and the Laplace principle?
Given a nice real valued functional $C$ on some probability space $(\Omega, \mathcal F, P_0)$ we have the following Donsker-Varadhan variational representation
$$\log E_{P_0}\left[e^C\right]=\sup_{P\...
- 1,904
5
votes
1
answer
224
views
Conditional expectation of random vectors
$\newcommand{\E}{\mathsf{E}}$
$\newcommand{\P}{\mathsf{P}}$
The following additional question was asked in a comment by user Oleg:
Suppose that $(\Omega,\mathcal F,\P)$ is a probability space, $B$ ...
- 128k
5
votes
1
answer
2k
views
Stopping time of two dimensional random walk
Let $U_n=\sum_{i=1}^n X_i,V_n=\sum_{i=1}^n Y_i$, $n\geq 1$, be a two-dimensional random walk with i.i.d. increments $(X_n, Y_n)$, where $X_n, Y_n$ are discrete random variables with joint pmf $P_{X,Y}$...
- 93
5
votes
2
answers
352
views
Does this equation has a closed-form solution for $t$? ($(1-p)\sum_{i=0}^{n}t^i = p\sum_{i=0}^{n}(1-t)^i)$)
We are given $n\in \mathbb N^+$ and $p\in[\frac{1}{2},\frac{n+1}{n+2}]$.
Our goal is to find $t\in[0,1]$ such that
$$(1-p)\sum_{i=0}^{n}t^i = p\sum_{i=0}^{n}(1-t)^i$$
Is there a closed-form solution $...
- 618
5
votes
1
answer
1k
views
Explicit constant for Carbery–Wright inequality
The Carbery–Wright inequality is a seminal result about the anti-concentration of polynomials of Gaussian random variables.
See e.g. Meka, Nguyen, and Vu - Anti-concentration for polynomials of ...
- 111