All Questions
9,497 questions
41
votes
2
answers
2k
views
Topple height of randomly stacked bricks
What is the expected height of a stack of unit-length bricks, each one
stacked on the previous with a uniformly random shift within $\pm \delta$?
The stack topples if the center of gravity of the top $...
- 151k
40
votes
5
answers
5k
views
"Entropy" proof of Brunn-Minkowski Inequality?
I read in an information theory textbook the Brunn-Minkowski inequality follows from the Entropy Power inequality.
The first one says that if $A,B$ are convex polygons in $\mathbb{R}^d$, then
$$ m(...
- 22.8k
40
votes
5
answers
6k
views
Probabilities in a riddle involving axiom of choice
The question is about a modification of the following riddle (you can think about it before reading the answer if you like riddles, but that's not the point of my question):
The Riddle:
We assume ...
- 1,341
40
votes
4
answers
4k
views
Polynomials on the Unit Circle
I asked this question in math.stackexchange but I didn't have much luck. It might be more appropiate for this forum. Let $z_1,z_2,…,z_n$ be i.i.d random points on the unit circle ($|z_i|=1$) with ...
- 3,626
40
votes
1
answer
6k
views
The human body's random number generator
I remember learning in microbiology that the human body generates antibodies using a random process so that an enormous variety of antibodies can be produced with a simple genetic code.
Now that I'm ...
- 3,359
40
votes
1
answer
5k
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 ...
- 2,135
39
votes
2
answers
2k
views
Random sequence of integers in $\{1, 2, \dots, n \}$ which is "everywhere probably increasing" - how long can it be?
Let $D=(d_1,d_2,\dots,d_k)$ be a sequence of correlated random variables. $D$ is "everywhere $r$-probably increasing" if the event $d_j > d_i$ has probability $\geq r$ for all $j > i$.
Fix $r \...
- 1,927
39
votes
2
answers
4k
views
Can random variables that almost surely solve equations be repaired to surely solve these equations?
Let $(X_\alpha)_{\alpha \in A}$ be a family of boolean random variables $X_\alpha: \Omega \to \{0,1\}$ on a probability space $\Omega = (\Omega, {\mathcal F}, {\mathbf P})$. Let ${\mathcal S}$ be a ...
- 114k
39
votes
3
answers
4k
views
Manifold of probability measures: connections between two types of metrics
The space of probability measures could be viewed as an infinite-dimensional manifold, equipped with two possible types of metrics — (1) Wasserstein and (2) Fisher-Rao. Metric (1) is connected with ...
- 1,127
39
votes
9
answers
3k
views
The shortest path in first passage percolation
Update (January 17): The problem has now been solved by Daniel Ahlberg and Christopher Hoffman. (Thanks to Matt Kahle for informing us.)
Consider a square planar grid. (The vertices are pair of ...
- 24.7k
39
votes
1
answer
1k
views
Modeling question: how often does "the world's oldest person" die?
This story yesterday (no need to follow the link to understand the question!)
http://www.cnn.com/2011/US/02/01/texas.oldest.person.dies/index.html?hpt=T2
reminds me that I've often wondered about ...
- 17.6k
37
votes
3
answers
3k
views
On Mathematical Analysis of MathSciNet & MathOverflow
This question has two original motivations: mathematical and social.
The mathematical motivation is mainly based on what I have seen about Zipf's law here and there. The Zipf's law simply states ...
37
votes
3
answers
3k
views
An entropy inequality
Let $X,Y$ be probability measures on $\{1,2,\dots,n\}$, and set $K=\sum_i\sqrt{X(i)Y(i)}$ so that $Z:=\frac{1}{K}\sqrt{XY}$ is also a probability measure on $\{1,2,\dots,n\}$. How can we prove the ...
- 11.4k
36
votes
3
answers
4k
views
the following inequality is true，but I can't prove it
The inequality is
\begin{equation*}
\sum_{k=1}^{2d}\left(1-\frac{1}{2d+2-k}\right)\frac{d^k}{k!}>e^d\left(1-\frac{1}{d}\right)
\end{equation*}
for all integer $d\geq 1$. I use computer to verify ...
- 363
36
votes
2
answers
13k
views
Mean minimum distance for N random points on a one-dimensional line
Let's say that I have a one-dimensional line of finite length 'L' that I populate with a set of 'N' random points. I was wondering if there was a simple/straightforward method (not involving long ...
- 811
36
votes
4
answers
2k
views
Determinant of the random matrix $X^2+Y^2$
$\DeclareMathOperator\Prob{Prob}$Let $X,Y\in M_n(\mathbb{R})$ be $2$ random matrices. The entries of $X,Y$ are i.i.d. variables. They follow the standard normal law $N(0,1)$.
i) When $n=2,3,4$, one ...
- 3,741
36
votes
0
answers
2k
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 ...
- 188k
35
votes
7
answers
6k
views
Why is conformal invariance only possible for massless theories?
I'm conscious that this isn't necessarily a research level question, but I've asked this question on mathstackexchange, and received no answer. So I'm trying it here.
A usual mantra in field theories ...
- 914
35
votes
4
answers
5k
views
Why are optimization problems often called "programs"?
Why are optimization problems often called programs?
linear programming
geometric programming
convex programming
Integer programming
...
- 461
35
votes
5
answers
11k
views
What mathematical treatment is there on the renormalization group flow in a space of Lagrangians?
What mathematical treatment is there on the renormalization group flow in a space of Lagrangians?
- 921
35
votes
1
answer
2k
views
Random walk inside a random walk inside...
Let $G=(V,E)$ be a graph and consider a random walk on it. Let $G'=(V',E')$ be a subgraph consisting of the vertices and edges that are visited by the random walk.
Question 0: Is there a standard ...
- 85.6k
34
votes
7
answers
3k
views
A hat puzzle question—how to prove the standard solution is optimal?
I am currently writing an essay on hat puzzles, and for the warm-up section I introduce some of the standard finite hat puzzles. One of these proceeds as follows:
You and two friends are each given a ...
- 236k
34
votes
3
answers
2k
views
Intrinsic significance of differential entropy
Many commentators (e.g. Jaynes, Rota) argue that the notion of "differential entropy" is problematic (as commonly defined by $ h(X) = \int ( \log\frac{1}{p(x)} ) p(x) \, dx $, where $X$ is a random ...
- 1,223
33
votes
7
answers
2k
views
List of proofs where existence through probabilistic method has not been constructivised
The probabilistic method as first pioneered by Erdős (although others have used this before) shows the existence of a certain object. What are some of the most important objects for which we can show ...
33
votes
4
answers
9k
views
A Markov process which is not a strong markov process?
Can anyone give an example of a Markov process which is not a strong Markov process? The Markov property and strong Markov property are typically introduced as distinct concepts (for example in ...
- 1,666
33
votes
1
answer
2k
views
$\mathbb{E}[X^4]=1$, $X,Y$ iid, what's the best upper bound of $\mathbb{E}[(X-Y)^4]$?
Let $X,Y$ be i.i.d. random variables, $\mathbb{E}[X^4]=1$, what's the best upper bound for $\mathbb{E}[(X-Y)^4]$ ?
A trivial upper bound is $16$, since $(X-Y)^4 \leq 8 (X^4+Y^4)$ then take ...
- 563
33
votes
4
answers
2k
views
How many random walk steps until the path self-intersects?
Take a random walk in the plane from the origin,
each step of unit length in a uniformly random direction.
Q. How many steps on average until the path self-intersects?
My simulations suggest ~$8....
- 151k
33
votes
1
answer
1k
views
Why does McMahon formula look like the inclusion-exclusion principle?
The McMahon formula for the number of tilings of an $a \times b \times c$ hexagon by lozenges:
$$ \Big[H(a)H(b)H(c)\Big] \Big[H(a+b)H(b+c)H(c+a)\Big]^{-1} \Big[H(a+b+c)\Big]$$
looks oddly like the ...
- 22.8k
32
votes
5
answers
6k
views
What is a good method to find random points on the n-sphere when n is large?
As part of a more complex algorithm, I need a fast method to find random points of the n-sphere, $S^n$, starting with a RNG (random number generator). A simple way to do this (in low dimensions at ...
- 15.3k
32
votes
3
answers
12k
views
What is the Katz-Sarnak philosophy?
It has been recently mentioned by a speaker (his talk is completely not relevant to random matrix theory/RMT though) that modern statistics, especially random matrices theory, will help solving some ...
- 8,071
32
votes
4
answers
4k
views
Is a random subset of the real numbers non-measurable? Is the set of measurable sets measurable?
One might say, "a random subset of $\mathbb{R}$ is not Lebesgue measurable" without really thinking about it. But if we unpack the standard definitions of all those terms (and work in ZFC), it's not ...
- 2,200
32
votes
4
answers
7k
views
Bayesian statistics for pure mathematicians
Could someone please recommend reading on Bayesian statistics presented from a pure mathematical point of view? That is, works that start assuming a good knowledge of measure theoretic probability. ...
32
votes
1
answer
1k
views
Does projection of 3D points reduce distances by exactly 1/3?
Let $P$ be a set of $n$ random points uniformly distributed inside
a unit-radius sphere centered on the origin.
Orthogonally project $P$ to a random plane through the origin;
call the projected points ...
- 151k
32
votes
1
answer
4k
views
Do invariant measures maximize the integral?
Update: The negative answer to the following question has been provided by Matthew Daws, who won, but also rejected, the bounty of 100 euro that I set over the question.
Let $\mathcal M(\mathbb Z)$ ...
- 6,034
32
votes
2
answers
11k
views
Intuition of law of iterated logarithm?
Let $X_i$ be iid random variables with $EX_i = 0$ and $Var X_i=1$ and $S_n=X_1+\cdots+X_n$. Then the law of the iterated logarithm says almost everywhere we have
$$\limsup_{n\to\infty}\frac{S_n}{\...
- 1,533
32
votes
5
answers
2k
views
You pass X people and Y people pass you: how relatively fast are you?
This question occurs to me every time I go jogging. I suspect every runner probabilist in the world must have thought of it (though I'm no probabilist), but I could not specifically find it online. I ...
- 2,791
31
votes
4
answers
3k
views
Expected length of longest stick in a stick snapping process
Starting with a single stick of unit length, a point $p \in (0, 1)$ is picked uniformly at random along the stick and the stick is snapped, producing two sticks of length $p$ and $1-p$.
At each next ...
- 6,155
31
votes
4
answers
2k
views
Probability of zero in a random matrix
Let $M(n,k)$ be the set of $n\times n$ matrices of nonnegative integers such that every row and every column sums to $k$. Let $P(n,k)$ be the fraction of such matrices which have no zero entries, ...
- 37.7k
31
votes
3
answers
4k
views
Expectation of a random sum
Let $X_1, X_2, X_3,\dots$ be an i.i.d. sequence of random variables with finite mean. Write $S_n=X_1+X_2+\dots+X_n$.
Let $N$ be a non-negative integer-valued random variable with finite mean. $N$ may ...
- 3,937
31
votes
5
answers
2k
views
On average, how many uniformly random real numbers $u$ are needed for their sum to exceed $1$, if $u_1$ is in $(0,1)$ and $u_k$ is in $(0,eu_{k-1})$?
A well-known question is: on average, how many uniformly random real numbers in $(0,1)$ are needed for their sum to exceed $1$? The answer is $e$.
Let's tweak this question by making each random ...
- 3,507
31
votes
1
answer
7k
views
"psi-epistemic theories" in 3 or more dimensions
In their recent paper The Quantum State Can Be Interpreted Statistically, Lewis et al. end with a very nice mathematical question, one whose answer (either way) would have interesting implications for ...
- 9,823
30
votes
4
answers
2k
views
If $X$ and $Y$ independent and identically distributed, then $E(|X-Y|)\leq E(|X+Y|)$. Are other proofs of this known?
I know a proof of the theorem that if $X$ and $Y$ independent and identically distributed, then $E(|X-Y|)\leq E(|X+Y|)$. The proof uses an integral representation of the absolute value,
$$\int_0^\...
- 409
30
votes
8
answers
3k
views
A variation of the law of large numbers for random points in a square
I uniformly mark $n^2$ points in $[0,1]^2$. Then I want to draw $cn$ vertical lines and $cn$ horizontal lines such that in each small rectangle there is at most one marked point. Surely, for a given ...
- 5,053
30
votes
4
answers
3k
views
Distribution of roots of complex polynomials
I generated random quadratic and cubic polynomials with coefficients in $\mathbb{C}$
uniformly distributed in the unit disk $|z| \le 1$. The distribution of the roots of 10000
of these polynomials are ...
- 151k
30
votes
3
answers
2k
views
Random knot on six vertices
This question is inspired by Joseph O'Rourke's beautiful question on random knots. Choose an random ordered 6-tuple of points on the unit sphere in $\mathbf{R}^3$, and form a knot by connecting ...
- 13.1k
30
votes
1
answer
2k
views
Have any numbers been proven to be normal that weren't constructed to be?
It's easy to construct an example of a number that's normal in a given base, but for most given numbers it's notoriously hard to prove that they're normal.
Has any number ever been proven to be normal ...
- 1,311
30
votes
2
answers
1k
views
Shortest path through $\sqrt{n}$ points out of $n$
Say I sample $n$ points uniformly at random in the unit square, and then I look for the shortest path through $\sqrt{n}$ of those points (rounding up, say). What happens to the length of this path as ...
- 335
30
votes
1
answer
1k
views
Functional-analytic proof of the existence of non-symmetric random variables with vanishing odd moments
It is known that a random variable $X$ which is symmetric about $0$ (i.e $X$ and $-X$ have the same distribution) must have all its odd moments (when they exist!) equal to zero. The converse is a ...
- 6,853
30
votes
1
answer
942
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$, $0<c&...
- 109k
29
votes
5
answers
9k
views
Examples where Kolmogorov's zero-one law gives probability 0 or 1 but hard to determine which?
Inspired by this question, I was curious about a comment in this article:
In many situations, it can be easy to
apply Kolmogorov's zero-one law to
show that some event has probability 0
or 1, ...
- 2,615