Theory and applications of probability and stochastic processes: e.g. central limit theorems, large deviations, stochastic differential equations, models from statistical mechanics, queuing theory.

learn more… | top users | synonyms (1)

24
votes
0answers
2k views

When should we expect Tracy-Widom?

The Tracy-Widom law describes, among other things, the fluctuations of maximal eigenvalues of many random large matrix models. Because of its universal character, it obtained his position on the ...
21
votes
0answers
1k views

Correspondence between eigenvalue distributions of random unitary and random orthogonal matrices

In the course of a physics problem (arXiv:1206.6687), I stumbled on a curious correspondence between the eigenvalue distributions of the matrix product $U\bar{U}$, with $U$ a random unitary matrix and ...
19
votes
0answers
711 views

conjectures regarding a new Renyi information quantity

In a recent paper http://arxiv.org/abs/1403.6102, we defined a quantity that we called the "Renyi conditional mutual information" and investigated several of its properties. We have some open ...
19
votes
0answers
443 views

Density of first-order definable sets in a directed union of finite groups

This is a generalization of the following question by John Wiltshire-Gordon. Consider an inductive family of finite groups: $$ G_0 \hookrightarrow G_1 \hookrightarrow \ldots \hookrightarrow G_i ...
18
votes
0answers
396 views

Two conjectures about zero inner products and dissociated sets

The following problems come from something I worked on (with my coauthors) related to proving a new time lower bound for streaming problems. Having worked on these problems for some time with little ...
18
votes
0answers
447 views

Human Knot game

In the popular game "Human Knot", a group of people stands in a circle and each person grabs another person's hands at random (one with the left hand and one with the right hand). The goal is to ...
18
votes
0answers
927 views

The Fourier Transform of taking Eigenvalues

The purpose of this question is to ask about the Fourier transform of the map which associate to an $n$ by $n$ matrix its $n$ eigenvalues, or some function of the $n$ eigenvalues. The main motivation ...
17
votes
0answers
413 views

partition of infinite word onto permitted words

Consider words over binary alphabet $\{0,1\}$. Let $M$ be a set of finite words such that $M$ contains at least $c\cdot 2^n$ words of length $n$ for all large enough $n$ (for a constant $c$, ...
17
votes
0answers
502 views

What is the best probabilistic estimate from below for a random polynomial on an arc?

I'm currently involved in a small (but quite time consuming) project where we are trying to get some decent bound for the number $N(P)$ of real zeroes of a random polynomial $P(x)=\sum_{k=0}^n\xi_k ...
17
votes
0answers
377 views

Are there lightweight foundations for arbitrarily extendable objects?

My experience with foundations is rather scant, but I've run into some types of objects that seem to resist the sort of set-theoretic encoding schemes via Kurowski tuples that are rather common for ...
16
votes
0answers
508 views

Random Distance Matrices

My question is motivated by the following recent paper: http://arxiv.org/abs/1110.6333 Assume you have a metric space $(X,d)$ equipped with a Borel probability measure $\mu$. We can further assume ...
15
votes
0answers
459 views

The lonely molecule

Suppose $n$ air molecules (infinitesimal points) are bouncing around in a unit $d$-dimensional cube, with perfectly elastic wall collisions. Let $k=n^{\frac{1}{d}}$. For example, in 3D, $d=3$, with ...
15
votes
0answers
773 views

Optimal Monotone Families for the Discrete Isoperimetric Inequality

Background: the Discrete Isoperimetric Inequality Start with a set X={1,2,...,n} of n elements and the family $2^X$ of all subsets of X. For a real number p between zero and one, we consider a ...
14
votes
0answers
1k views

When does a correlated Brownian motion leave a square?

Let $B=(X,Y)$ be a correlated two-dimensional Brownian motion, that is, the components are standard Brownian motions and the covariance between $X_t$ and $Y_t$ is $t\rho$ for some constant $\rho \in ...
14
votes
0answers
642 views

On random Dirichlet distributions

Fix a dimension $d\ge2$. Let $Q_d$ denote the positive quadrant of $\mathbb{R}^d$, that is, $Q_d$ is the set of points $\mathbf{x}=(x_i)_i$ in $\mathbb{R}^d$ such that $x_i>0$ for every $i$. ...
13
votes
0answers
334 views

Why, and how badly, does the proof of “no percolation at the critical point in half-spaces” fail for full spaces?

The proof by Barsky et. al. that there is no percolation in half-spaces proceeds by a dynamic renormalization argument. The proof couples critical percolation in the half-space $\mathbb{H}^d$ with a ...
12
votes
0answers
597 views

Does this metric have an official name? Lévy metric? Ky Fan metric?

Let $X$ and $Y$ be random variables taking values in a separable metric space $(S,d)$. The metric I have in mind is $$\rho(X,Y) = \mathbb{E}[\min\{d(X,Y),1\}]$$ if $X$ and $Y$ take values in the a ...
12
votes
0answers
340 views

Which limit to take as a key applied math decision

The Borel-Kolmogorov paradox refers to situations where non-uniqueness in the notion of conditioning on a set of measure zero leads to apparent contradictions. As a formal matter, one requires ...
12
votes
0answers
739 views

surprisingly difficult filtration problem

I am interested in a proof of the following statement which seems intuitive, but is somehow really tricky: Let $X$ be a stochastic process and let $(\mathcal{F}(t) : t \geq 0)$ be the filtration ...
12
votes
0answers
273 views

support of the coupling between two probability measures

Given two Borel probability measures $\mu$ and $\nu$ on $\mathbb{R}$, let $\Pi(\mu, \nu)$ denote all couplings between them, i.e., all Borel probability measures on $\mathbb{R}^2$ such that the ...
11
votes
0answers
284 views

Probability of many overlapping zero inner products on a circle

[Question edited and changed a little on June 14 2015] Consider an $n$-dimensional vector $v$ with $v_i \in \{-1,1\}$. Now consider an $n$-dimensional vector $w$ with $w_i \in \{-1,0,1\}$. The ...
11
votes
0answers
383 views

Transitivity of balanced mass transport in Z

Given two atomic measures $\mu$ and $\nu$ on $\mathbb{Z}$, write $\mu \sim \nu$ iff there exist countable decompositions $\mu = \mu_1 + \mu_2 + \cdots$ and $\nu = \nu_1 + \nu_2 + \cdots$ along with ...
11
votes
0answers
361 views

First passage percolation on a random geometric graph in the large connectivity limit

Let $V_\rho\subset\mathbb{R}^2$ be a point set in the plane obtained from a Poisson process of density $\rho$. The random geometric graph $G_\rho$ is obtained from $V_\rho$ by connecting points that ...
11
votes
0answers
301 views

What kind of random matrices have rapidly decaying singular values?

I've been told that in machine learning it's common to compute the singular value decomposition of matrices in order to throw out all information in the matrix except that corresponding to, say, the ...
11
votes
0answers
153 views

Savings property: A transformation which turns nonnegative martingales into uniformly integrable ones

Background I work in a subfield of computability theory called algorithmic randomness. We have been using martingales as long as probability theory (going back to work of von Mises). However, since ...
11
votes
0answers
438 views

High-dimensional geometry: Top-down Vs. Bottom-up

There are several ways to leverage one's intuition from low-dimensional geometry to understand high-dimensional phenomena. For example, one can get a clearer picture of the behaviour of ...
11
votes
0answers
763 views

Constructive aspects of Caratheodory's theorem in convex analysis

Let me paraphrase Caratheodory's theorem in a probabilistic setup: Let $X$ be a real-valued random variable. For $k = 1, \ldots, m$, let $f_k: \mathbb{R} \to \mathbb{R}$ be a continuous function such ...
10
votes
0answers
154 views

Self-avoiding random walks that always turn

I am wondering if the statistics of self-avoiding random lattice-walks on $\mathbb{Z}^2$ that turn left or right at each step (i.e., they cannot continue the direction of the preceding step) have been ...
10
votes
0answers
378 views

Steady state expectation of dynamic system of urns & balls

We have a large number of urns $N+1$. (Large means that the relative difference between $N$ and $N+1$ is well within the error bounds that I care about. The reason for the $+1$ will be apparent ...
10
votes
0answers
409 views

Where can I find analogues of combinatorial central limit theorems for other groups

The statement of Hoeffding's combinatorial central limit theorem is as follows: given for each $n$, an $n \times n$ matrix $A = (a_{ij})$, one can consider the random diagonal sum: $$\displaystyle ...
10
votes
0answers
345 views

Question from an economist: solving a model of traders' behavior with expectations about the future values of the variable they are currently optimizing

Motivation I am an economist writing a paper for an academic finance journal. My paper is about the behavior of currency traders, who choose the price at which they will sell currency today, based on ...
10
votes
0answers
1k views

Constants in the Rosenthal inequality

Let $X_1,\ldots,X_n$ be independent with $\mathbf{E}[X_i] = 0$ and $\mathbf{E}[|X_i|^t] < \infty$ for some $t \ge 2$. Write $X = \sum_{i=1}^n X_i$. Then we have the family of "Rosenthal-type ...
10
votes
0answers
166 views

literature on “stratified simulation”

I've thought of an approach to variance reduction that surely can't be new, but I haven't been able to find it published anywhere; I'd appreciate some leads. Consider some sort of random variable $X$ ...
9
votes
0answers
195 views

Convergence in $L^2$ of iterated expectations

Take a probability space $(\Omega,\mathcal{F},\mathbf{P})$ and random variable $X \in L^2(\Omega,\mathcal{F},\mathbf{P})$. Define the iterated expectations of X as follows: $X_0 = X$, and, ...
9
votes
0answers
341 views

Distribution of maximum of random walk conditioned to stay positive

I have an $n$ step random walk which starts at zero $X_0 = 0 = S_0$ where the steps $X_i$ are independent uniform random variates in $[-1,1]$, but the walk is conditioned on the hypothesis that it ...
9
votes
0answers
269 views

Renewal process: domination by product measure

Consider a stationary process $(X(i), i\in\mathbb{Z})\in \{0,1 \}^\mathbb{Z}$ with the following structure; runs of 0s alternate with runs of 1s, with the length of all runs independent, and with each ...
9
votes
0answers
356 views

Maximizing the volume in a family of subsets of a cube

Starting from a question in probability, one is eventually lead to the following optimization problem. Let $I:=[0,\\, 1],$ and let $A$ be a Lebesgue measurable subset of the $n$-dimensional cube, ...
8
votes
0answers
161 views

Randomly placing nonoverlapping unit cuboids

Suppose one places unit cuboids of dimension $d$ with min-corners uniformly distributed to lie in $[0,n]^d$, but with cuboid (strict) overlap forbidden. At some point, the region is "saturated," ...
8
votes
0answers
309 views

Finitely additive measures on $\mathbb Z_2^\omega$ with invariance and independence constraints

Let $G = \mathbb Z_2^\omega$, with pointwise addition. Assume the Axiom of Choice. I am interested in finitely additive probability measures $\mu$ defined on all of $\mathcal PG$ that can be ...
8
votes
0answers
262 views

Hasse-Weil Bound and Chebyshev Inequality

I was reading about the Hasse-Weil bound for the number of points in on a curve over the finite field $\mathbb{F}_q$. $$ \big| |C(\mathbb{F}_q)| - (q+1) \big| \leq 2g \sqrt{q} $$ However, this ...
8
votes
0answers
504 views

Full conditional probabilities and versions of AC?

A probability is a finitely additive measure on a boolean algebra with total measure $1$. A function $P:\scr B \times (\scr B - \{ 0 \})$ is a full conditional probability on $\scr B$ (for a boolean ...
8
votes
0answers
150 views

Generalised Polya's urn with i.i.d. replacement

Let $\mu$ be a fixed measure (possibly with moment conditions) on $\mathbb N$ and $X_1,X_2,\dots$ be i.i.d. samples from $\mu$. Start with one white and one black ball in the urn. At the $n$-th step, ...
8
votes
0answers
109 views

Functions between Markov chains that preserve local harmonicity

Given two Markov chains with respective state-spaces $S$ and $T$, say that a function $\phi$ from $S$ to $T$ is holomorphic iff for all states $t \in T$, every real-valued function $f$ on $T$ that is ...
8
votes
0answers
375 views

Eigenvalues of permutations of a real matrix: how complex can they be?

This is sort of complementary to this thread. I’ll repeat the definitions here: For a matrix $M\in GL(n,\mathbb R)$, consider the $n!$ matrices obtained by permutations of the rows (say) of $M$ and ...
8
votes
0answers
300 views

Uncertainty principle in Entropy terms

Math Questions: Consider Hilbert space $L_2(\mathbb{R})$ with a standard norm $ ||\psi|| = ( \int_{\mathbb{R}}{ |\psi(t)|^2 dt } )^{1/2}, $ and Fourier transform $ (F\psi)(\xi) = ...
8
votes
0answers
239 views

First Table of Random Numbers

What was the first table of random numbers of any sort? The best I can do is Tippett and Pearson's Random Sampling Numbers of 1927. Can anybody identify an earlier table? Thanks for any ...
8
votes
0answers
319 views

Bounding the probability that a random variable is maximal

Suppose we have $N$ independent random variables $X_1$, $\ldots$, $X_N$ with finite means $\mu_1 \leq \ldots \leq \mu_N$ and variances $\sigma_1^2$, $\ldots$, $\sigma_N^2$. I am looking for ...
8
votes
0answers
847 views

Combinatorial proof for the number of lattice paths that return to the axis only at times that are a multiple of 4

Consider lattice paths consisting of $2n$ steps, each of which is either $(1,1)$ or $(1,-1)$. The number of such lattice paths that return to the horizontal axis only at times that are a multiple of ...
8
votes
0answers
2k views

Group Theory, Game Theory, a bit of Philosophy and a post in Tao's blog

I've decided to write this post after reading the incredibly beautiful and highly recomended post by Terence Tao ...
8
votes
0answers
392 views

Abelian sandpile models

This question is about a popular probabilistic model on graphs studied in physics, mostly, for the standard lattice in ${\mathbb R}^n$ but also on other graphs (this model is of the same spirit as ...