All Questions
950 questions
43
votes
8
answers
3k
views
How to quantify noncommutativity?
If I have two operators or finite-dimensional matrices $A$ and $B$, how can I quantify the amount to which they commute or don't commute? (I would consider it a big plus if it is computable easily for ...
- 1,890
41
votes
4
answers
2k
views
What is the probability two random maps on n symbols commute?
It is well known that two randomly chosen permutations of $n$ symbols commute with probability $p_n/n!$ where $p_n$ is the number of partitions of $n$. This is a special case of the fact that in a ...
- 38.6k
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
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
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
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
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
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
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
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
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
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
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
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
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
29
votes
6
answers
8k
views
How to find a closest integer point to the intersection of two lines?
Here's a question that originates from StackOverflow.
Given are two lines on a plane, specified by equations ($a x + b y = c$) with integer coefficients. The lines aren't parallel and they don't ...
- 391
29
votes
6
answers
2k
views
Combinatorial Morse functions and random permutations
This question has its origin in combinatorial topology. In the 90s R. Forman proposed a discrete counterpart of Morse theory. In his case, a Morse function on a triangulated space is a function ...
- 34.7k
28
votes
6
answers
2k
views
Random Alternating Permutations
An alternating permutation of {1, ..., n} is one were π(1) > π(2) < π(3) > π(4) < ... For example: (24153) is an alternating permutation of length 5.
If $E_n$ is the number of alternating ...
- 22.8k
28
votes
2
answers
771
views
Probability of generation of ${\mathbb Z}^2$
What is the probability that three pairs $(a,b) $ , $(c,d) $ and $(e,f) $ of integers generate $\mathbb Z^2$? As usual the probability is the limit as $n\to \infty$ of the same probability for the $n\...
user6976
28
votes
5
answers
2k
views
Moments of area of random triangle inscribed in a circle
The $2m$th moment of the (random) area of the triangle whose vertices are three independent, uniformly distributed random points on the unit circle appears to be $((3m)!/(m!)^3)/16^m$. Can anyone ...
- 19.7k
27
votes
4
answers
3k
views
Rate of convergence of $\frac{1}{\sqrt{n\ln n}}(\sum_{k=1}^n 1/\sqrt{X_k}-2n)$, $X_i$ i.i.d. uniform on $[0,1]$?
Let $(X_n)$ be a sequence of i.i.d. random variables uniformly distributed in $[0,1]$; and, for $n\geq 1$, set
$$
S_n = \sum_{k=1}^n \frac{1}{\sqrt{X_k}}\,.
$$
It follows from the generalized central ...
- 1,372
27
votes
7
answers
9k
views
Why are two "random" vectors in $\mathbb R^n$ approximately orthogonal for large $n$?
I saw that two random independent vectors are approximately orthogonal in high dimensional space.
How can I prove this?
And is there an intuitive explanation?
Thank you.
- 387
27
votes
3
answers
4k
views
Why is free probability a generalization of probability theory?
Note: This question was already asked on Math.SE nearly a week and a half ago but did not receive any responses. To the best of my knowledge, free probability is an active topic of research, so I hope ...
- 2,680
27
votes
7
answers
30k
views
When do 3D random walks return to their origin?
The probability of a random walk returning to its origin is 1 in two dimensions (2D) but only 34% in three dimensions: This is Pólya's theorem. I have learned that in 2D the condition of returning to ...
- 151k
27
votes
5
answers
7k
views
Probability of a Random Walk crossing a straight line
Let $(S_n)_{n=1}^{\infty}$ be a standard random walk with $S_n = \sum_{i=1}^n X_i$ and $\mathbb{P}(X_i = \pm 1) = \frac{1}{2}$. Let $\alpha \in \mathbb{R}$ be some constant. I would like to know the ...
- 733
26
votes
3
answers
3k
views
An $L^0$ Khintchine inequality
Suppose that $\epsilon_1,\epsilon_2,\ldots$ are IID random variables with the Bernoulli distribution $\mathbb{P}(\epsilon_n=\pm1)=1/2$, and $a_1,a_2,\ldots$ is a real sequence with $\sum_na_n^2=1$. ...
- 17.1k
26
votes
4
answers
2k
views
$\binom{x}{2}+\binom{x}{4}+\cdots+\binom{x}{2u}$ is a convex function on $[0,+\infty)$?
Let $f(x)=\binom{x}{2}+\binom{x}{4}+\cdots+\binom{x}{2u}$, where $u\in\mathbb{Z}^+$ and $\binom{x}{l}=\frac{x(x-1)\dots(x-l+1)}{l!}$ for all $l\in\mathbb{Z}^+$.
Then can we prove $f(x)$ is a convex ...
- 271
25
votes
3
answers
2k
views
Some models for random graphs that I am curious about
G(n,p)
We are familiar with the standard notion of random graphs where you fixed the number n of vertices and choose every edge to belong to the graph with probability 1/2 (or p) independently. This ...
- 24.7k
25
votes
3
answers
2k
views
Persistent homology of Gaussian fields in Euclidean space
If you generate points in $\mathbb R^n$ via a process that respects a Gaussian normal distribution, then compute the persistent homology / barcodes, to my eye something fairly regular seems to be ...
- 44.3k
24
votes
3
answers
4k
views
What upper bounds are known for the diameter of the minimum spanning tree of $n$ uniformly random points in $[0,1]^2$?
Let $P$ be a pointset consisting of $n$ uniformly random elements of $[0,1]^2$. It is known that the diameter (greatest number of edges in any shortest path between two points) of the Delaunay ...
- 4,922
24
votes
2
answers
1k
views
Drawing natural numbers without replacement.
Suppose we start with an initial probability distribution on $\mathbb{N}$ that gives positive probability to each $n$. Let's call this random variable $X_1$ so we have $P(X_1=n)=p_{1,n}>0$ for all $...
- 551
23
votes
2
answers
7k
views
What is a Gaussian measure?
Let $X$ be a topological affine space. A Gaussian measure on $X$ is characterized by the property that its finite-dimensional projections are multivariate Gaussian distributions.
Is there a direct ...
- 8,502
23
votes
2
answers
1k
views
How large can $\mathbf{P}[X_1 + X_2 + X_3 < 2 X_4]$ get?
Let $\mu$ be a probability measure on $[0,\infty)$ and $X_1, \dots, X_4 \sim \mu$ independent. Then what can be said about the probability that $X_1 + X_2 + X_3 < 2 X_4$?
More precisely, what is ...
- 6,406
23
votes
1
answer
1k
views
Does a theory of stochastic differential algebras exist?
My question is motivated primarily by finance, where a non-technical student will learn how to approach SDEs using the symbolic manipulation of Itô calculus and the few basic rules of Brownian motion, ...
- 231
23
votes
7
answers
5k
views
What makes Gaussian distributions special?
I'm looking for as many different arguments or derivations as possible that support the informal claim that Gaussian/Normal distributions are "the most fundamental" among all distributions.
...
22
votes
4
answers
5k
views
Eigenvalues of permutations of a real matrix: can they all be real?
For a matrix $M\in GL(n,\mathbb R)$, consider the $n!$ matrices obtained by permutations of the rows (say) of $M$ and define the total spectrum $TS(M)$ as the union of all their spectra (counting ...
- 13.4k
21
votes
7
answers
2k
views
Identities and inequalities in analysis and probability
Usually, at the heart of a good limit theorem in probability theory is at least one good inequality – because, in applications, a topological neighborhood is usually defined by inequalities. Of course,...
21
votes
3
answers
6k
views
Why pi-systems and Dynkin/lambda systems? On the relative merits of approaches in measure theory.
What is the point of $\pi$-systems and
$\mathcal{D}$ / Dynkin /
$\lambda$-systems?
I am an analyst in the process of consolidating my measure theory knowledge before moving on to harder/newer ...
- 1,771
21
votes
3
answers
1k
views
Probability that random weights on $K_n$ satisfy triangle inequality
Given $K_n$, if a random real weight between $[0, 1]$ is chosen for every edge, what is the probability that the graph satisfies the triangle inequality? How about the discrete version, where the ...
- 343
21
votes
2
answers
3k
views
How to optimally bet on a biased coin?
A number $p$ is drawn uniformly at random from $[0, 1]$. You are then given a biased coin that turns up heads with probability $p$, but the number $p$ is not known to you.
You start with a total ...
- 6,155
21
votes
3
answers
5k
views
James-Stein phenomenon: What does it mean that a James-Stein estimator beats least squares estimator?
Background James-Stein estimator and Stein's phenomenon, as described in Wikipedia are rather counterintuitive and amazing.
It is claimed that if one wants to estimate the mean $\Theta$ of
Gaussian ...
- 24.9k
21
votes
2
answers
548
views
Do these polynomials have alternating coefficients?
In answering another MathOverflow question, I stumbled across the sequence of polynomials $Q_n(p)$ defined by the recurrence
$$Q_n(p) = 1-\sum_{k=2}^{n-1} \binom{n-2}{k-2}(1-p)^{k(n-k)}Q_k(p).$$
Thus:
...
- 44.4k
21
votes
4
answers
6k
views
A random walk with uniformly distributed steps
The following problem has bothered me for a long time.
Let us imagine a point on the real axis. At the beginning, it is located at point $O$. Then it will "walk" on the real axis randomly in the ...
- 1,551
20
votes
3
answers
1k
views
what is the probability that a scissor became the champion?
Here is a question from one of my students:
suppose 8 players are in an elimination match. The players are marked with marked with either R (for rock), P (for paper) or S (for scissors). If two ...
- 201
20
votes
3
answers
1k
views
The Angel and Devil problem with a random angel
In the classic version of Conway's Angel and the Devil problem, an angel starts off at the origin of a 2-D lattice and is able to move up to distance $r$ to another lattice point. The devil is able ...
- 6,969
20
votes
3
answers
1k
views
How can I randomly draw an ensemble of unit vectors that sum to zero?
Inspired by this question, I would like to determine the probability that a random knot of 6 unit sticks is a trefoil. This naturally leads to the following question:
Is there a way to sample ...
- 7,633
20
votes
5
answers
1k
views
Probability that biggest area stays greater than 1/2 in a unit square cut by random lines
The square $[0,1]^2$ is cut into some number of regions by $n$ random lines. We can chose these random lines by randomly picking a point on one of the four sides, picking another point randomly from ...
20
votes
4
answers
870
views
Enumeration and random selection
In Peter J. Cameron's book "Permutation Groups" I found the following quote
It is a slogan of modern enumeration theory that the ability to count a set is closely related to the ability to pick a ...
- 85.6k
19
votes
3
answers
3k
views
Measure induced on [0, 1] by infinite tosses of biased coin
It is well-known that one can get the Lebesgue measure on [0, 1] by tossing a fair coin infinitely (countably) many times and mapping each sequence to a real number written out in binary.
I was ...
- 675
19
votes
4
answers
1k
views
Applications of linear programming duality in combinatorics
So, I know that one can apply the strong LP duality theorem to specific instances of maximum flow problems to recover some nontrivial theorems in combinatorics, such as Hall's theorem, Koenig's ...
- 997