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.
9,025 questions
9
votes
4
answers
4k
views
Anti-concentration of Gaussian quadratic form
Let $X_1,\dots,X_n$ denote i.i.d. standard Gaussian random variables. My question is: Do there exist absolute constants $C,c>0$ such that for every $\epsilon>0$ and positive real numbers $a_1,\...
- 667
9
votes
3
answers
749
views
Random RSK and Plancherel Measure
Let $(X_1,X_2,\ldots)$ be a sequence of i.i.d. random variables. It is known that if these random variables are distributed uniformly on the unit interval, then applying the RSK algorithm to this ...
- 4,952
9
votes
2
answers
4k
views
What is (approximately) the expected value of $X\log{ X}$ where $X$ is binomial (or Poisson)?
Let $X$ follow a binomial distribution with parameters $n$ and $p$. Are there any known bounds for the expected value of $X\log{X}$, for large $n$ and small (but fixed) $p$? A Poisson approximation ...
- 383
9
votes
4
answers
952
views
What does it mean when we say we have computed a number to a certain accuracy using a probabilistic algorithm?
My intention is to ask a general question about probabilistic (Monte Carlo) algorithms. But to keep things simple, I will focus on a few specific examples.
Let me start the discussion with ...
- 3,245
9
votes
3
answers
7k
views
Are there known expressions for total variation distance between $N(0,\sigma_1^2)$ and $N(0,\sigma^2)$
Are known expressions for total variation distance between $N(0,\sigma^2)$ and $N(0,\sigma^2+\epsilon)$ for small $\epsilon$? The only thing I seem to find is things are expression about the mean but ...
- 383
9
votes
2
answers
1k
views
Did Joseph Doob prove that random sequences don't exist?
In the book "The Mathematical Experience" it says:
"An infinite [binary] sequence $x_1, x_2, \ldots$ is called random in the sense of von Mises if every infinite sequence $x_{n_1}, x_{n_2}, \ldots$...
- 4,351
9
votes
4
answers
19k
views
Sum of Log Normal random variables [closed]
I would be grateful to anyone who could provide me with some reference concerning the behavior of the sum of Log Normal random variables (need not independent) with respect to a Log Normal random ...
- 1,334
9
votes
5
answers
395
views
Probability theory without deductive closure
Human knowledge is not deductively closed. Uncertainty can arise from that just as much as from lack of brute facts. (When a Harvard graduate was reported to have thought that the earth is farther ...
9
votes
1
answer
8k
views
Convergence rate of the central limit theorem near the center of the distribution
I'm looking for fast convergence rates for the central limit theorem - when we are not near the tails of the distribution.
Specifically, from the general convergence rates stated in the Berry–Esseen ...
- 968
9
votes
5
answers
1k
views
$E(X_1 | X_1 + X_2)$, where $X_i$ are (integrable) independent infinitely divisible rv's "of the same type"
The following is inspired by this recent question on math.stackexchange.
Two standard exercises in conditional expectation are to find ${\rm E}(X_1|X_1+X_2)$ where:
1) $X_i$, $i=1,2$, are independent $...
- 1,468
9
votes
6
answers
3k
views
Primes are pseudorandom?
I've been reading the wonderful slides by Terry Tao and thought about this question.
Primes appear to be quite random, and the formal statement should be that there are some characteristics of primes ...
- 15.1k
9
votes
1
answer
626
views
Strange definition of ergodicity
I've already asked this question on math.stack a few days ago and haven't received an answer, so I'm asking here.
In an engineering course, a stationary process was defined to be ergodic if for all $...
- 935
9
votes
3
answers
1k
views
A question on Cramer's theorem
Almost everybody is familiar with Cramer's theorem: a sum $X+Y$ of of independent random variables is normal if and only if both $X$ and $Y$ are normal. Are there any other classes of distributions ...
- 125
9
votes
1
answer
2k
views
Pólya's Random Walk Constants at infinity
Let be the probability that a random walk on a d-D lattice returns to the origin. In 1921, Pólya proved that $p(1)=p(2)=1$
but $p(d)<1$ for $d>2$.
http://mathworld.wolfram.com/...
9
votes
1
answer
1k
views
The length of the longest consecutive string of heads or tails that occur asymptotically almost surely when a unbiased coin is flipped repeatedly
Consider an unbiased coin being flipped $n$ times, and suppose we label the outcomes as Heads = 0, and Tails = 1. Then the result of the flipping is a finite binary sequence of length $n$. Let us ...
- 91
9
votes
1
answer
395
views
An inequality on the simplex involving $x^x$
Is anything known about the behavior of the function $$f(x)=\prod_{i=1}^n x_i^{x_i}$$ on the standard simplex, i.e. the set $\{x\in\mathbb{R}^n:\sum_{i=1}^n x_i=1, x_i\geq0\}$? I ask because I have ...
- 93
9
votes
2
answers
1k
views
Adaptive version of the Azuma–Hoeffding inequality
The Azuma inequality states that if we have a martingale $X_1,\ldots,X_N$ that satisfies a bounded difference condition:
$$|X_k - X_{k-1}| \leq c_k$$
Then:
$$\Pr\left[X_N - X_0 \geq \sqrt{2\sum_kc_k^2 ...
- 794
9
votes
3
answers
868
views
Rosenthal like inequality for weak $\mathbb L^p$-norms
Let $p$ be a real number greater than $1$. It is well known (see Hall and Heyde's Martingale limit theory and its applications, Theorem 2.10) that there exists a constant $C_p$ such that if $(X_i)_{i=...
- 3,993
9
votes
2
answers
479
views
Hyperreal finitely-additive measure on [0,1) assigning $b-a$ to $[a,b)$ or $(a,b]$ and infinitesimals to singletons
Is there a hyperreal-valued finitely additive measure on all the subsets of [0,1), or at least the Borel ones, that
assigns $b-a$ to $[a,b)$ and to $(a,b]$ for all $a\lt b,$ and
assigns an ...
- 2,555
9
votes
1
answer
860
views
Random walk on a simple finite network
Consider a graph $\Delta_N = \lgroup (x,y)\in\mathbb{Z}^2| x+y\leq N-1, x\geq 0,\ y\geq 0 \rgroup$ (set of edges is defined in a natural way): see here ).
Take a random walker that wonders around ...
- 965
9
votes
3
answers
5k
views
Laplace transform and fractional moments
Is there any "easy" way to calculate fractional moments from Laplace transform.
To be more specyfic let us consider the following example. Let $X$ be a positive random variable and
$L(\theta)...
- 1,491
9
votes
1
answer
484
views
What does convergence in distribution "in the Gromov–Hausdorff" sense mean?
I am trying to understand this survey article by Le Gall on Brownian geometry, especially the statement of Theorem 1.
The basic statement of the theorem is
$$(m_n,d_n) \to (m_{\infty}, d_{\infty})$$
"...
- 7,857
9
votes
2
answers
989
views
Average size of extreme points of convex hull of $N$ points
Fix $n$ a (small) integer.
Let $N$ be a (big) integer. Consider $N$ random points in the $n$-dimensional unit cube $[0, 1]^n$. The $N$ points are independently uniformly distributed.
Define $V(N)$ ...
- 3,432
9
votes
1
answer
578
views
Does every smooth manifold carry a gaussian random field?
Let $M$ be an arbitrary finite-dimensional smooth manifold. For simplicity, let's assume that $M$ has no boundary. Does there always exist a gaussian random field with constant variance on $M$? If not,...
- 201
9
votes
1
answer
4k
views
What are some characterizations of the strong and total variation convergence topologies on measures?
I asked this question on StackExchange a few days ago but didn't get any response, so I thought I would try here.
The Wikipedia article on convergence of measures defines three kinds of convergence: ...
- 203
9
votes
3
answers
354
views
Surfaces that are 'everywhere accessible' to a randomly positioned Newtonian particle with an arbitrary velocity vector
Consider an idealized classical particle confined to a two-dimensional surface that is frictionless. The particle's initial position on the surface is randomly selected, a nonzero velocity vector is ...
- 811
9
votes
4
answers
850
views
easy(?) probability/diff eq. question
I've been wondering about this ever since I was a little kid and I used to ride in the back of the car and my mom would speed like hell towards a green light, only to slam on the brakes when she ...
- 6,069
9
votes
3
answers
450
views
All stationary martingales are constant?
Suppose $(X_{n})_{n\geq{1}}$ is a stationary process that is a martingale with respect to some filtration. Suppose also that $\mathbb{E}X_{0}^{2}<\infty$ so that $\mathbb{E}X_{n}^{2}<\infty$ for ...
- 662
9
votes
1
answer
652
views
Scaling in Mehta's integral
The following expression is known as Mehta's integral and deeply connected to random matrix theory:
$$\frac{1}{(2\pi)^{n/2}}\int_{-\infty}^{\infty} \cdots \int_{-\infty}^{\infty} \prod_{i=1}^n e^{-...
- 124
9
votes
2
answers
726
views
Return probabilities for random walks on infinite Schreier graphs
Question: Is there a sequence $(\delta_n)_n$ of real numbers with $\delta_n \to 0$ as $n \to \infty$, such that the following holds:
Let $F$ be a free group on two generators, let $F \curvearrowright ...
- 25.5k
9
votes
1
answer
155
views
How to sample exactly k indices given the inclusion probabilities of all indices?
Let $k<d$ two positive integers, and $\{p_i\}_{i=1}^d$ a series of probabilities, with $p_i \in (0,1)$ and $\sum_{i=1}^d p_i = k$.
We wish to sample exactly $k$ distinct indices $\mathcal{I}\...
- 968
9
votes
1
answer
735
views
Where has this structure been observed?
$\newcommand{\M}{\mathcal{M}}$Let $M$ be a monoid. Consider the following structure:
$R_X,R_Y:\mathbb{Z}^2 \to M$ satisfying the following "compatiblity-relation":
$$R_X (x, y) \cdot R_Y (x +...
- 6,741
9
votes
1
answer
539
views
Random walk on infinite graph
Let $G$ be an infinite countable non-oriented connected graph with bounded degrees. Let $X(n)$ be the lazy random walk on $G$ and let $u,v$ be two vertices. Does the ratio
$P(X(n)=v)/P(X(n)=u)$
tend ...
- 723
9
votes
4
answers
371
views
Diameter of random segment intersection graph?
I have an even number of points $n$ randomly distributed (uniformly) in a disk.
Then the points are randomly connected to form $n/2$ segments, a perfect
matching.
Finally, I form the intersection ...
- 151k
9
votes
2
answers
706
views
Measures whose projections are absolutely continuous
Since my question was not answered on MSE, I would like to ask it here.
Let $\mu$ be a finite Borel measure on the plane. Does there exist a characterization of the property that almost all (wrt ...
- 452
9
votes
2
answers
646
views
Rain droplets falling on a table
Suppose you have a circular table of radius $R$. This table has been left outside, and it begins to rain at a constant rate of one droplet per second. The drops, which can be considered points as they ...
- 191
9
votes
3
answers
486
views
Representing a real number as the value of a countably infinite game
Is it true that for any real number $p$ between 0 and 1, there exist finite or infinite sequences $x_m$ and $y_n$ of positive real numbers, and a finite or infinite matrix of numbers $\varphi_{mn}$ ...
- 187
9
votes
1
answer
958
views
Quantitative bounds for multivariate central limit theorem
For the univariate central limit theorem, the Berry-Esseen theorem gives a quantitative bound on the rate of convergence of distributions to the Normal distribution under Kolmogorov distance:
https://...
- 93
9
votes
3
answers
569
views
Statistics for Second order properties of Random graphs
Hi!
Let G(N) be the number of graphs with vertices {1, 2, ..., N} and GN(F) be the number of those of them which satisfy graph property F. There is a beautiful result by Glebskii and Fagin that limit ...
- 1,175
9
votes
2
answers
659
views
Symmetric groups and Poisson processes
Consider the number of fixed points in a permutation chosen uniformly at random from the symmetric group on $n$ elements - this gives a probability distribution. For $k < n$, the $k$-th moments of ...
- 354
9
votes
2
answers
658
views
Probability that randomly chosen balls have a nonempty common intersection
Fix some $0 < r < 1$. A collection of points $x_1, \dots, x_n$ are chosen independently and uniformly at random from the closed unit ball in $\mathbb R^d$.
What is the probability that the ...
- 6,321
9
votes
2
answers
497
views
Is there a determinantal point process proof of the Keating-Snaith formula for the cumulants of the log characteristic polynomial of a random matrix?
For $U$ a unitary $N \times N$ matrix, randomly distributed according to Haar measure, we have the complex-valued random variable $\log (\det (1-U))$. The real part and imaginary parts of $\log (\det (...
- 149k
9
votes
2
answers
1k
views
An elementary question in bond percolation
Consider a locally finite, connected graph and "bond (edge) percolation" on this graph. Each edge is open with probability $p.$ There is a parameter $\alpha$, $0<\alpha<1.$
The ...
9
votes
1
answer
557
views
A non-recursive, explicit formula for the Fabius function
The Fabius function $F\colon\mathbb R\to[-1,1]$ may be defined as the unique solution of the functional integral equation
$F(x)=\int_0^{2x}F(t)\,dt$ for all real $x$ such that $F(1)=1$.
The recent ...
- 128k
9
votes
4
answers
3k
views
How can the Kalman filter be adapted to handle binary observations?
Imagine a coin with a time-varying probability of coming up heads. (For example, perhaps the probability follows a random walk that is constrained to live in $[0, 1]$. And say we have some ...
- 251
9
votes
1
answer
2k
views
Fourth moments of Gaussian processes
I am working on a topic outside my main research area, so I am afraid I am reproving obvious results, so I would like to ask for a reference. Google didn't help, mostly because I am looking for ...
- 20.2k
9
votes
2
answers
537
views
Clusters of uniformly distributed random points
This can be viewed as a toy version of this wonderful question. (I'm removing the TSP component, and I'll zoom in on the statistical part.)
Let $X_1,\ldots, X_n$ be iid, with uniform distribution in $...
- 24.2k
9
votes
3
answers
1k
views
Concentration of sum of pairwise squared Euclidean distances of random vectors
Let $X_1, \ldots, X_n $ be independent random vectors in $B(0, D) \subset R^d$ ($\ell_2$ ball of radius $D$ centered at the origin). I am trying to find the concentration of the following quantity ...
- 91
9
votes
2
answers
1k
views
Random pseudoprimes vs. primes
(Edit. What I called "pseudoprimes" are known as "Cramér random primes" in the literature,
of which I was unaware.)
Say that a set $S$ of natural numbers is a set of pseudoprimes if they
are (a) ...
- 151k
9
votes
2
answers
3k
views
Is this a situation where triple mutual information is always non-negative?
Suppose I have three identically-distributed homogeneous continuous-time discrete state space Markov chains $X_1(t), X_2(t), X_3(t)$, $t\geq 0$. They evolve independently but share a common random ...
- 599