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
18
votes
3
answers
1k
views
Existence of a "quasi-uniform" probability distribution on $\mathbb{Z}$
Does there exist a probability distribution on $\mathbb{Z}$ such that
for every integer $n\geq 1$, the probability that a random integer $x$
is divisible by $n$ equals $1/n$?
Henry Cohn has an ...
- 50.8k
18
votes
3
answers
3k
views
Entropy and total variation distance
Let $X$, $Y$ be discrete random variables taking values within the same set of $N$ elements. Let the total variation distance $|P-Q|$ (which is half the $L_1$ distance between the distributions of $P$ ...
- 20.2k
18
votes
4
answers
6k
views
most general way to generate pairwise independent random variables?
Is there a sort of structure theorem for pairwise independent random variables or a very general way to create them?
I'm wondering because I find it difficult to come up with a lot of examples of ...
- 1,093
18
votes
4
answers
1k
views
Reference for a strong intermediate value theorem for measures
Let $\mu$ be a finite nonatomic measure on a measurable space $(X,\Sigma)$, and for simplicity assume that $\mu(X) = 1$. There is a well-known "intermediate value theorem" of Sierpiński that states ...
- 5,407
18
votes
1
answer
1k
views
How fast can extreme eigenvalues of the average of random matrices converge to their expectation?
Suppose that $X_1,X_2,\ldots,X_m$ are independent $d\times d$ random matrices and let $\overline{X} := \frac{1}{m}\sum_{i=1}^m X_i$. One of the questions studied under the theory of random matrices is ...
- 181
17
votes
2
answers
1k
views
Is measure preserving function almost surjective?
Let $F:[0,1]\to[0,1]$ be a Lebesgue measure preserving function. Is $F$ almost surjective, i.e., the image of $F$ has interior measure one?
This question is motivated by the following observation. If ...
- 397
17
votes
1
answer
622
views
Longest of random worm-like paths in $\mathbb{Z}^2$
Imagine at each lattice point of $\mathbb{Z}^2$ within $[1,3n]^2$,
with coordinates
$\equiv 2 \bmod 3$,
we place, with equal probability, one of these six patterns:
The result ...
- 151k
17
votes
1
answer
1k
views
Can this probability be obtained by a combinatorial/symmetry argument?
Suppose that $a_1,\dots,a_n,b_1,\dots,b_n$ are iid random variables each with a symmetric non-atomic distribution.
Let $p$ denote the probability that there is some real $t$ such that $t a_i \ge b_i$ ...
- 128k
17
votes
3
answers
736
views
Probability that a word in the free group becomes (much) shorter?
Let $w$ be a word of length $2\ell$ chosen at random on the alphabet $\{x_1,x_1^{-1},x_2,x_2^{-1},\dotsc,x_k,x_k^{-1}\}$. By the reduction $\rho(w)$ I mean what you obtain by deleting substrings of ...
- 20.2k
17
votes
1
answer
10k
views
Conjugate prior of the Dirichlet distribution?
What is the conjugate prior distribution of the Dirichlet distribution?
Edit: Since I asked this question many years ago, I've written a Python library for working with exponential families. Maximum ...
- 598
17
votes
5
answers
4k
views
Brownian motion and spheres
Consider a Brownian motion on $[0;1]$. A (finite) discrete approximation of this Brownian motion consists of $N$ iid Gaussian random variables $\Delta W_i$ of variance $\frac{1}{N}$:
$$ W\left(\frac{k}...
- 2,133
17
votes
1
answer
910
views
Randomly switching street lights, in a square city
This is a combinatorics-probability question, best stated however in "recreational" terms. Imagine a $N\times N$ city, meaning that we have $N$ horizontal streets, and $N$ vertical streets. At each ...
- 1,363
16
votes
1
answer
929
views
A simple stochastic game
An individual, henceforth called the runner starts at the center of an open two dimensional square $\Omega$ of side length $r \geq 2$.
At each turn, a vector $x \in S^1$ is chosen uniformly at random, ...
- 6,213
16
votes
3
answers
2k
views
Solving a modified birthday problem at a glance
Modified Birthday Problem: a bunch of people line up, and the winner is the first person who shares their birthday with someone lined up ahead of them. What position in the line is optimal?
Three (...
- 7,831
16
votes
4
answers
1k
views
Continuity on a measure one set versus measure one set of points of continuity
In short: If $f$ is continuous on a measure one set, is there a function $g=f$ a.e. such that a.e. point is a point of continuity of $g$?
Now more carefully, with some notation: Suppose $(X, d_X)$ ...
- 2,221
16
votes
4
answers
1k
views
Random Diophantine polynomials: Percent solvable?
Suppose one generates a random polynomial
of degree $d$ with integer coefficients
uniformly distributed within $[-c_\max,c_\max]$.
For example, for
$d=8$, $|c_\max|=100$, here is one random polynomial:...
- 151k
16
votes
3
answers
2k
views
A random walk on random lines
I am wondering if this random walk remains finite with positive probability.
Start with three lines $A,B,C$ that are extensions of an equilateral triangle.
Let $p_0$ be one corner. Generate a line $...
- 151k
16
votes
6
answers
2k
views
Optimal pebble-packing shape
Suppose you throw many ($n$) congruent convex bodies (in $\mathbb{R}^3$) of unit volume (or of unit area in $\mathbb{R}^2$) into a large container, and shake it until little else changes.
Q. ...
- 151k
15
votes
3
answers
2k
views
Probability that product is a perfect square
The probability a given integer in $[0,n]$ is a square is $\frac1{\sqrt n}$. What is the probability that if you take two integers uniformly then their product is square?
I know the main term is $\...
- 13.9k
15
votes
3
answers
6k
views
Is there a central limit theorem for bounded non identically distributed random variables?
I have a sequence of centered independent random variables $X_i$ that are all
bounded by one in absolute value. They are not identically distributed, though.
I would like to know if the central limit ...
15
votes
1
answer
660
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 ...
15
votes
2
answers
1k
views
self-avoidance time of random walk
How many steps on average does a simple random walk in the plane take before it visits a vertex it's visited before?
If an exact formula does not exist (as seems likely), then I'm interested in good ...
- 19.7k
15
votes
0
answers
749
views
Prove $\int_{0}^{\infty} \cos(\omega x) \exp(-x^{\alpha}) \, {\rm d} x \ge {\alpha^2 \sqrt{\pi} \over 8} \exp \left( -\frac{\omega^2}{4} \right)$
I would like to prove that
$$\int_{0}^{\infty} \cos(\omega x) \exp(-x^{\alpha}) \, {\rm d} x \ge
{\alpha^2 \sqrt{\pi} \over 8} \exp \left( -\frac{\omega^2}{4} \right)$$
for any $\omega > 0$ and $...
- 178
15
votes
0
answers
477
views
Expanding disks lead to what packing of the plane?
Suppose one sprinkles points uniformly at random on the infinite Euclidean plane,
with some density $\rho$ per unit area.
View the points as disks of radius zero.
Now the radii $r$ of all disks grows ...
- 151k
15
votes
2
answers
5k
views
What areas of algebra could be interesting to probability theorists?
I would like to find some topic of algebra (beyond linear algebra; algebraic number theory is fine) that would be interesting both to a student that wants to specialize in probability theory and to me ...
- 16.9k
15
votes
3
answers
13k
views
Maximum of two normal random variables
The main purpose of the following question is to get some intuition and deeper understanding why the presented method works which would hopefully help me in trying to adapt it to the setting I am ...
- 311
15
votes
3
answers
2k
views
Disintegrations are measurable measures - when are they continuous?
This is a sequel to another question I have asked.
The notion of disintegration is a refinement of conditional probability to spaces which have more structure than abstract probability spaces; ...
- 8,512
15
votes
4
answers
1k
views
Painting $n$ balls from $2n$ balls red, and guessing which ball is red, game
The game
Lucy has $2n$ distinct white colored balls numbered $1$ through $2n$. Lucy picks $n$ different balls in any way Lucy likes, and paint them red. Lucy then giftwrap all the balls so that it is ...
- 215
15
votes
6
answers
8k
views
Any sum of 2 dice with equal probability
The question is the following: Can one create two nonidentical loaded 6-sided dice such that when one throws with both dice and sums their values the probability of any sum (from 2 to 12) is the same. ...
- 261
15
votes
1
answer
1k
views
In how many steps a random walk visits all the elements of a finite group, with a probability 1/2?
This question is a variation of the return to the origin problem.
Let $G$ be the finite group $\mathbb{Z}/n \times \mathbb{Z}/n$ and let the random transformation $T: G \to G$ such that $T(a,b) = (...
15
votes
2
answers
3k
views
What do we actually know about logarithmic energy ?
In potential theory, the $\textit{logarithmic energy}$ of a Radon measure $\mu$ acting on $\mathbb{C}$ is defined by
$$I(\mu)=\iint\log\frac{1}{|x-y|}\mu(dx)\mu(dy).$$ Of course it is not well ...
- 2,135
15
votes
2
answers
734
views
On sums of independent random variables in Banach spaces
Let $(\xi_n)_{n\ge 1}$, $(\eta_n)_{n\ge 1}$ be independent mean-zero random variables with values in a Banach space $X$ such that
$$\sum_n\mathbb P(\xi_n\in A)\le\sum_n\mathbb P(\eta_n\in A)$$for any ...
- 4,535
14
votes
1
answer
1k
views
Normal numbers, Liouville function, and the Riemann Hypothesis
This is a question about whether or not some number $\lambda^*$ is normal in base 2. More specifically, I am wondering if $\lambda^*$ is not normal. Proving it is normal would be next to impossible, ...
- 3,098
14
votes
3
answers
8k
views
Analog of Chebyshev's inequality for higher moments
I have a positive random variable $X$ with $E[X] = 1$ and a small number $k$ more moments bounded by constants:
$$E[(X-1)^i] = O(1) \forall i \in \{2, ..., k\}.$$
I'd like to bound the average of $n$...
- 241
14
votes
1
answer
3k
views
How is the "conformal prediction" conformal?
The question is clarified by Prof.V.Vovk. See his answer below for discussion.
Recently, early works of Gammerman, Vanpnik and Vovk[4] are rediscovered by Wasserman et.al[1] and proposed it as a ...
- 8,071
14
votes
1
answer
8k
views
Expectation of square root of binomial r.v.
Let $X\sim B(n,p)$ denote a binomial random variable. Is there any approximation available for the quantity $E(\sqrt{X})$? Clearly Jensen's inequality holds, but rudimentary tooling around with ...
14
votes
1
answer
956
views
Partitioning the vertices of an n-cube with random hyperplane cuts
An evolutionary biologist asked me a question which boils down, at least in part, to what seems to me an interesting question of combinatorial/probabilistic geometry.
It is an old chestnut of a ...
- 19.2k
14
votes
4
answers
2k
views
Gaussian distributions as fixed points in Some distribution space
I'm taking a course on topology and probabily. Today, the professor remarked something along the lines of:
If you look at the space of probability distributions with $0$ mean and variance $1$, ...
- 935
14
votes
1
answer
813
views
Large-n limit of the distribution of the normalized sum of Cauchy random variables
What is the large-n limit of a distribution of the following sample statistic:$$x\equiv\displaystyle\frac{\sum^{n}X_{i}}{\,\sqrt{\,\sum^{n}X_{i}^{2}\,}\,}$$ when sampling the Cauchy(0,1) distribution? ...
- 419
14
votes
3
answers
4k
views
How to generate random points in $\ell_p$ balls?
How do I feasibly generate a random sample from an $n$-dimensional $\ell_p$ ball? Specifically, I'm interested in $p=1$ and large $n$. I'm looking for descriptions analogous to the statement for $p=2$:...
- 667
14
votes
3
answers
3k
views
Expected value of the minimum with limited independence
Imagine you sample $n$ number with replacement uniformly from the integers $1,\dots, n$. Let $X$ be the minimum of these samples. I am interested in $\mathbb{E}(X)$ but with a twist. All I know is ...
- 3,377
14
votes
6
answers
2k
views
Density of numbers having large prime divisors (formalizing heuristic probability argument)
I want to prove that the set of natural numbers n having a prime divisor greater than $\sqrt{n}$ is positive.
I have a heuristic argument that this density should be $\log 2$, which is approximately ...
- 7,320
14
votes
1
answer
417
views
Lipschitz property of the determinant
$\newcommand{\A}{\mathcal A}\newcommand{\Tr}{\operatorname{tr}}$For $c$ and $C$ such that $0<c<C<\infty$, let $\A_{d;c,C}$ denote the set of all symmetric positive-definite real $d\times d$ ...
- 128k
14
votes
3
answers
2k
views
Concentration bounds for sums of random variables of permutations
I'm trying to find theorems regarding random variables derived from sampling permutations, specifically concentration bounds.
As an example, let $X_i$ be the $\{0,1\}$-random variable that represents ...
- 539
14
votes
1
answer
1k
views
Berry Esseen type result for probability density functions
Let $X_1, X_2, \cdots$ be i.i.d. random variables with $E(X_1) = 0, E(X_1^2) = \sigma^2 >0, E(|X_1|^3) = \rho < \infty$.
Let $Y_n = \frac{1}{n} \sum_{i=1}^n X_i$ and let us note $F_n$ (resp. $\...
14
votes
3
answers
1k
views
Probability of coprime polynomials
Given positive integer $N$, we choose $m_1, m_2, n_1, n_2$ independently and with equal probabilities from $\{0,1,\ldots,N\}$, and let
$f_1 = x^{m_1} + (1+x)^{n_1}$ and $f_2 = x^{m_2} + (1+x)^{n_2}$ ...
- 54.2k
14
votes
1
answer
781
views
Perimeters of random-walk polygons
I have a random walk on $\mathbb{Z}^2$ that takes a step
with equal probability in the three directions that avoid
retracing the previous step.
The walk proceeds until it returns to a lattice point
...
- 151k
14
votes
2
answers
962
views
The power of two random choices with pairwise independence
Throw $n$ balls into $n$ bins, and let $X_n$ be the max load. That is the number of balls in the fullest bin. It is known that if the balls are thrown uniformly and independently at random then $\...
- 3,377
13
votes
1
answer
3k
views
random walk and Brownian motion on Riemannian manifold
As we know, the random walk on $\mathbb{Z}/n$ will converge(in some sense) to the Brownian motion on $\mathbb{R}$ when $n\to\infty$. I would like to know is there some higher dimensional analogy ...
- 1,111
13
votes
1
answer
10k
views
KL divergence and mixture of Gaussians
Do we have an exact formula to compute the KL divergence between 2 mixtures of Gaussians (i.e convex combinations of a finite number of Gaussian distributions)?
If not exactly known, are there good ...
- 2,246