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
7 votes
0 answers
161 views

Approximating any convex shape in $\mathbb{R}^d$ with a polytope having $\mathrm{poly}(d)$ facets

We denote by $V(A)$ the $d$-volume of any convex set $A$. Furthermore, given any two convex sets $A,B\in\mathbb{R}^d$, we denote by $V_{A,B}$ the $d$-volume of the symmetric difference $V\left(A \...
Penelope Benenati's user avatar
7 votes
1 answer
779 views

Trace of inverse of random positive-definite matrix in high dimension?

Consider a random matrix $A \in \mathbb{R}^{n\times n}$ with i.i.d. entries, with symmetric law and finite variance. I am curious about the behavior of $$\mathrm{Tr}( (A^T A + \lambda \mathrm{Id})^{-1}...
Goulifet's user avatar
  • 2,174
7 votes
0 answers
181 views

Growth of spheres in FINITE nilpotent groups - Gaussian approximation (central limit theorem)?

Standard setup. Consider a group and choose generators. Word-metric (or in the other words - distance on the Cayley graph of the group+generators) - converts a group into a metric space, which is ...
Alexander Chervov's user avatar
7 votes
2 answers
1k views

A curious martingale

Does there exist an almost surely continuous martingale $X$ with $X_t \to +\infty$ almost surely? Remark: Note that such a martingale exists in discrete time, or equivalently in continuous time if the ...
Nate River's user avatar
  • 4,822
7 votes
2 answers
637 views

Is there an algebraically normal function from $\mathbb{Z}^{n}$ to $\{ 0 , 1\}$?

Definition: Let $h$ be a polynomial in $n$ variables, then : $\gamma(h,r,R):=\{ v \in \mathbb{Z}^{n} : \vert h(v) \vert \leq r, \Vert v \Vert < R \}$ Let $\omega : \mathbb{Z}^{n} \to \{ 0 , 1\}$...
Sebastien Palcoux's user avatar
7 votes
1 answer
2k 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 ...
syh2010's user avatar
  • 71
7 votes
2 answers
388 views

Fractional Brownian motion of Riemann-Liouville type is not a semimartingale

Given a filtered probability space $(\Omega,\mathcal{F},\mathbb{F},\mathbb{P})$ satisfying the usual conditions, $B$ a standard one-dimensional Brownian motion and $H\in(0,1/2)$. Consider the process $...
El_mago's user avatar
  • 99
7 votes
1 answer
234 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 ...
Kass's user avatar
  • 243
7 votes
0 answers
428 views

Does the law of a Feller Process on a non-locally-compact Polish space depend continuously on the initial condition (in Skorohod path-space)?

I am sure this is written down somewhere but cannot find it. Consider a Polish space $E$ and a strong Markov process $(X_t)_{t\ge 0}$ with values in $E$ and cadlag paths. More precisely, we have a ...
Wolfgang Loehr's user avatar
7 votes
1 answer
353 views

Singular Fisher information matrix and existence of unbiased estimators

I'm doing some research into the Cramer-Rao bound for time of arrival localization and have come across a rather strange result: the FIM is singular, but there exists an unbiased estimator. My ...
JNL's user avatar
  • 75
7 votes
4 answers
3k views

Upper bound of the expectation of sum of the absolute value pairs

We have two arrays $A,B$ of length $n$. All values are i.i.d drawn from same distribution on $[0,1]$. If we sort $A,B$ in non-decreasing order and let $A_{(i)},B_{(i)}$ denote the i-th value in the ...
user avatar
7 votes
1 answer
964 views

Bounding the probability that two binomials are equal

Note: This question was migrated from this earlier post, where it initially appeared. Following suggestions, I moved this into its own question. Let $B_{n,p}$ denote the usual binomial random ...
Pat Devlin's user avatar
  • 2,660
7 votes
2 answers
637 views

What's the standard name for sets of a given size with maximal probability (or a given probability and minimal size)?

The definition I'm going to give isn't quite the concept I really want, but it's a good approximation. I don't want to make the definition too technical and specific because if there's a standard name ...
Darsh Ranjan's user avatar
  • 5,912
7 votes
1 answer
380 views

Combinatorial/probabilistic statements having $F_{\text{un}}$/$F_q$ geometric interpetation

$\newcommand{\Fun}{F_\text{un}}$There was lots of "Fun with $\Fun$" (field with one element) in recent years. One of the points is that it provides bridge between geometrical and ...
Alexander Chervov's user avatar
7 votes
1 answer
611 views

Do there exist three pairwise independent random variables, such that their sum is zero?

Do there exist such three non-constant pairwise independent random variables $X, Y, Z$ such that $X + Y + Z = 0$? I managed only to prove the following two facts: If such $X, Y, Z$ exist, they are ...
Chain Markov's user avatar
  • 2,618
7 votes
4 answers
7k views

Is there MDPs (Markov Decision Process) which have a non deterministic optimal policy?

I'm working on Markov Decision Process and I have not found yet an example of MDP that has a stochastic (non deterministic) optimal policy. Is there MDPs that have a stochastic optimal policy or is it ...
Lamine's user avatar
  • 288
7 votes
1 answer
217 views

Bound on queries to a tree with unusual probabilities

Consider a tree $\mathcal{T}(r) = (V,E)$ rooted at $r \in V$. Let $\kappa_r: V \longrightarrow [0,1]$ such that $\sum_{v \in V} \kappa_r(v)^2 = 1$. Furthermore, for any given vertex $v \neq r$, $\...
Michael Jarret's user avatar
7 votes
3 answers
328 views

Quantifying the noninvertibility of a function

Given a function $f$ from a finite set $X$ to itself, it seems natural to consider $\kappa_f := (\sum_{x \in X} |f^{-1}(x)|^2)/|X|$ as a measure of the non-invertibility of $f$: it equals 1 if $f$ is ...
James Propp's user avatar
  • 19.4k
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 ...
AB-Spc's user avatar
  • 71
7 votes
2 answers
1k views

Edge probability for connected Erdős–Rényi model

Consider the Erdős–Rényi model $G_{n,p}$ with corresponding probability measure $\mathbb{P}_{n,p}$. For any two vertices $x,y$, $\mathbb{P}_{n,p}[E_{x,y}]=p$, where $E_{x,y}$ is the event that there ...
jondal's user avatar
  • 71
7 votes
4 answers
454 views

What does $\mathbb E_V \max_{x \in V,\,\|x\|=1} x^T Ax$ evaluate to when $V$ is random $k$-dim suspace of $\mathbb R^n$ and $A$ is fixed psd matrix?

Let $G_{k,n}$ be the grassmannian of $k$-dimensional vector spaces of $\mathbb R^n$. By the Courant–Fisher characterization, the $k$th largest eigenvalue of an $n \times n$ psd matrix $A$ is given by $...
dohmatob's user avatar
  • 6,716
7 votes
1 answer
326 views

First Collision Time for k Random Walkers on a Torus

I consider $k$ random walkers on $\mathbb{Z}^{d}/n \mathbb{Z}^{d}$, the $d$-dimensional torus of side length $n$. More precisely, I will define a Markov chain $Z_{t} = (X_{t}[1], \ldots, X_{t}[k])$ ...
AMQS's user avatar
  • 71
7 votes
0 answers
496 views

Squaring random Schwartz distributions

Let $\mu$ denote the centered Gaussian measure on $S'(\mathbb{R}^d)$ with covariance $$ \mathbb{E} [\phi(f)\phi(g)]=\int_{\mathbb{R}^d} \frac{\overline{\widehat{f}(\xi)} \widehat{g}(\xi)}{|\xi|^{d-2[\...
Abdelmalek Abdesselam's user avatar
7 votes
0 answers
239 views

Distribution of trivial subset sums

Suppose I have a set $S$ of $n$ integers picked independently, uniformly at random from $[-L, L].$ Let $z(S)$ be the number of subsets of $S$ which sum to zero. The question is: what is the ...
Igor Rivin's user avatar
  • 95.5k
7 votes
1 answer
354 views

Injectivity of matrix "fingerprint"

Consider $S$, the set of all $n\times m$ real matrices with specified row sums $(r_1,...,r_n)$, column sums $(c_1,...,c_m)$, and strictly positive entries. For any matrix $A$, define $$ D_A(i,j)=\...
Bill Bradley's user avatar
  • 3,809
7 votes
1 answer
477 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 ...
Hedonist's user avatar
  • 1,269
7 votes
0 answers
462 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 ...
Abdelmalek Abdesselam's user avatar
7 votes
1 answer
753 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 ...
lchen's user avatar
  • 459
7 votes
1 answer
302 views

The time to drift a binary string from one state to another via deterministic selection of two possible random bit mutation procedures

I have some length $L$ binary string consisting of an ordered array of bits: $(b_1, b_2, ..., b_{L})$, where all bit values $b_i$ are originally set to zero. I'd like a particular set of $n$ bits to ...
Barium's user avatar
  • 123
7 votes
2 answers
555 views

Gaussian and the convex hull of moment curves

Let $c_1,\dots, c_d$ be the first $d$ moments of the standard normal distribution. Does the point $(c_1,\dots, c_d)$ lie in the convex hull of the set $\{(t,t^2,\dots,t^d)\colon t\in[-b,b]\}$, for a ...
Minkov's user avatar
  • 1,117
7 votes
2 answers
320 views

Random suborbits of a rotation

Let $u_n = x + n\alpha \pmod 1$ with $\alpha$ irrational. We know that $(u_n)_{n \geq 0}$ is dense in $\mathbb{R}/\mathbb{Z}$ (equivalently $(u_n)_{n \geq 0}$ visits every open interval infinitely ...
Stéphane Laurent's user avatar
7 votes
5 answers
672 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|...
teagut's user avatar
  • 93
7 votes
2 answers
3k views

The largest Wasserstein distance to uniform distribution among all probability distributions with uniform marginals

I am looking for the largest Wasserstein distance to the uniform distribution among all probability distributions with uniform marginals. More specifically, let $\Xi=\{1,2,\ldots,N\}^2$, and let $\nu$...
O. Richard's user avatar
7 votes
2 answers
882 views

Brownian motion in $n$ dimensions

Consider a particle starting at the origin in $\mathbb{R}^n$ and undergoing Brownian motion. Is there an expression known for the probability of the particle hitting the sphere $S^{n - 1}_r = \{x \in \...
user82390's user avatar
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 ...
Jiahao Chen's user avatar
  • 1,870
6 votes
0 answers
306 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 ...
Jeanne Scott's user avatar
  • 1,847
6 votes
2 answers
4k 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 ...
Gregory Putzel's user avatar
6 votes
3 answers
415 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) = ...
dohmatob's user avatar
  • 6,716
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 ...
Hugh Medal's user avatar
6 votes
2 answers
196 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?
Jean Duchon's user avatar
  • 3,055
6 votes
1 answer
347 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$ ...
Jiayi Liu's user avatar
  • 909
6 votes
0 answers
243 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$: $$...
Yaroslav Bulatov's user avatar
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 ...
SBF's user avatar
  • 1,605
6 votes
1 answer
372 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 ...
JSG's user avatar
  • 237
6 votes
2 answers
480 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 ...
AgnostMystic's user avatar
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$. ...
Georg Pichler's user avatar
6 votes
1 answer
232 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 ...
Matthew Harrison-Trainor's user avatar
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 ...
Scott Armstrong's user avatar
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 ...
Mehmet Ozan Kabak's user avatar
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 ...
Henry.L's user avatar
  • 7,951

1
7 8
9
10 11
18