All Questions
9,497 questions
21
votes
0
answers
578
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 \...
- 2,200
20
votes
9
answers
3k
views
Random vs Unknown
Is there any distinction at all between a random quantity and an unknown quantity or is it impossible to distinguish?
Example: 5 minutes in the future, I plan to roll a die the the number of the die ...
20
votes
2
answers
3k
views
Boys and Girls Revisited
Consider a country with $n$ families, each of which continues having children until they have a boy and then stop. In the end, there are $G$ girls and $B=n$ boys.
Douglas Zare's highly upvoted answer ...
- 23k
20
votes
6
answers
19k
views
Intuition for Haar measure of random matrix
What is an intuitive way to understand Haar measure as defined for random matrices, say, $N\times N$ orthogonal or unitary matrices?
My understanding for what Haar measure means for $U(1)$ is that it ...
- 1,890
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
2
answers
2k
views
Is there a noncommutative Gaussian?
In classical probability theory, the (multivariate) Gaussian is in some sense the "nicest quadratic" random variable, i.e. with second moment a specified positive-definite matrix. I do not ...
- 5,701
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
10
answers
4k
views
Expected value as decision criterion in the context of rare events
I have often seen discussions of what actions to take in the context of rare events in terms of expected value. For example, if a lottery has a 1 in 100 million chance of winning, and delivers a ...
- 3,475
20
votes
5
answers
1k
views
Iterated Circumcircle
Take three noncollinear points (a,b,c), compute the center of their circumcircle x, and replace a random one of a,b,c with x. Repeat. It seems this process may converge to a point, assuming no ...
- 151k
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
3
answers
1k
views
The probability for a sequence to have small partial sums
The question
Let $a_1,a_2,\dots,a_n$ be a sequence whose entries are +1 or -1. Let t be a parameter. My question is to give an estimate for the number of such sequences so that
$|a_1+a_2+\dots ...
- 24.7k
20
votes
1
answer
2k
views
Does every compact metric space have a canonical probability measure?
Edit: Shortly after this post it was rightly pointed out by @AntonPetrunin that the measure $\mu$ may not be unique. @R W then showed how one can construct a metric space where the limiting measure is ...
- 203
20
votes
1
answer
2k
views
How rich is the richest person in a society satisfying the Pareto principle?
The Pareto Principle roughly states that in many societies, the top 20% of people hold over 80% of the wealth. Suppose we had a society that satisfied this principle in every stratum of society - how ...
- 6,155
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
20
votes
2
answers
4k
views
Teaching stochastic calculus to students who know no measure theory (or PDE, or...)
I've got quite a challenge as my teaching assignment for the next Fall (not that I want to get rid of it, quite the contrary, but I still feel like asking for advice won't hurt :-)).
I'm to teach the ...
- 61.9k
20
votes
4
answers
3k
views
Is there a statistical interpretation of Green's theorem, Stokes' theorem, or the divergence theorem?
This is cross-posted from math.stackexchange and stats.stackexchange. Probably there is no great answer to this question, but I thought I'd give it a shot here.
I'm teaching a class on integration ...
- 29.2k
20
votes
2
answers
819
views
A probability question related to extremal combinatorics
$k$ people play the following game: person $i$ independently picks a subset $S_i$ of $\{ 1,2,\ldots,n \}$ according to some distribution $p$ on the $2^n$ subsets; each person uses the same ...
- 976
20
votes
2
answers
6k
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 ...
- 201
20
votes
3
answers
2k
views
Do convex and decreasing functions preserve the semimartingale property?
Some time ago I spent a lot of effort trying to show that the semimartingale property is preserved by certain functions. Specifically, that a convex function of a semimartingale and decreasing ...
- 17.1k
20
votes
1
answer
4k
views
Using Fisher Information to bound KL divergence
Is it possible to use Fisher Information at p to get a useful upper bound on KL(q,p)?
KL(q,p) is known as Kullback-Liebler divergence and is defined for discrete distributions over k outcomes as ...
- 2,442
20
votes
1
answer
2k
views
Roadmap to Ergodic Theory
I have recently been interested in going deeper into ergodic theory, beyond an introductory level of knowledge. Background wise, my training has mostly been in stochastic analysis, and I have a ...
- 6,155
20
votes
1
answer
1k
views
Fourier transform of $f_a(x)= a^{-2}\exp(-|x|^a)$, $a \in (0,2)$, is decreasing in $a$
Can one show that Fourier transform of
$$ f_a(x) = a^{-2} \exp(-|x|^a), \qquad a \in (0,2)$$
is decreasing in $a$?
I have a solution for $a \in (0,1]$ which cannot be used for $a\in (1,2)$.
- 178
20
votes
2
answers
922
views
A functional inequality about log-concave functions
Let $f,g$ be smooth even log-concave functions on $\mathbb{R}^{n}$, i.e.,$f=e^{-F(x)}, g=e^{-G(x)}$ for some even convex functions $F(x),G(x)$. Is it true that:
$$
\int_{\mathbb{R}^{n}} \langle \...
- 3,946
19
votes
10
answers
3k
views
Probabilistic method used to prove existence theorems
I am aiming for a "big list" of theorems using probability techniques to prove existence of some objects. And in each case, there is an interesting question -- can we find an explicit example? Was the ...
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
5
answers
8k
views
What is the probability that two random walkers will meet?
It is a well known result that a random walk on a 2D lattice will return to the origin see Polya's random walk constant. Based on this, it is not a big stretch to conclude that the random walk will ...
- 301
19
votes
2
answers
1k
views
Particles chasing one another around a circle
Two particles start out at random positions on a unit-circumference circle.
Each has a random speed (distance per unit time) moving counterclockwise uniformly distributed
within $[0,1]$. How long ...
- 151k
19
votes
9
answers
3k
views
How can I generate random permutations of [n] with k cycles, where k is much larger than log n?
I've been thinking a lot lately about random permutations. It's well-known that the mean and variance of the number of cycles of a permutation chosen uniformly at random from Sn are both ...
- 14k
19
votes
7
answers
3k
views
A geometric interpretation of independence?
Consider the set of random variables with zero mean and finite second moment. This is a vector space, and $\langle X, Y \rangle = E[XY]$ is a valid inner product on it. Uncorrelated random variables ...
- 415
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
19
votes
3
answers
6k
views
Anti-concentration of Bernoulli sums
Let $a_1,\ldots,a_n$ be real numbers such that $\sum_i a_i^2 =1$ and let $X_1,\ldots,X_n$ be independent, uniformly distributed, Bernoulli $\pm 1$ random variables. Define the random variable
$S:= \...
- 363
19
votes
3
answers
931
views
Is the circle in the square best at avoiding random lines?
This question is inspired by a recent one (and takes a great deal from the answers there). Given a convex subset $\Delta$ of the unit square, let $p(\Delta)$ be the probability that a random line does ...
- 30.1k
19
votes
3
answers
1k
views
Which distributions can you sample if you can sample a Gaussian?
Explicitly: You have a computer that is able to pick a real number at random according to the normal distribution: $\mathcal{N}(0,1) = \frac{1}{\sqrt{2\pi}}e^{-x^2/2}$. Which distributions can this ...
- 922
19
votes
3
answers
2k
views
Current state of the Komlos conjecture on vector balancing
Komlos Conjecture: the exists an absolute constant $K>0$ such that for all $d$ and any collection of vectors $v_1,\ldots, v_n\in \mathbb{R}^d$ with $\left\lVert v_i\right\rVert _2=1$ we can find ...
- 2,288
19
votes
5
answers
18k
views
Time-inhomogeneous Markov chains
I'm trying to find out what is known about time-inhomogeneous ergodic Markov Chains where the transition matrix can vary over time. All textbooks and lecture notes I could find initially introduce ...
- 191
19
votes
2
answers
569
views
Repeated random two-steps in $\mathbb{R}^3$: unbounded?
I created a random isometry $T$ of $\mathbb{R}^3$ by generating
a random orthogonal matrix $M$,
uniformly distributed among all such,
and a random displacement $v$, whose coordinates
are drawn from a ...
- 151k
19
votes
4
answers
4k
views
Are gaussians with different moments far in total variation distance?
If two Gaussians disagree on one moment, it seems like this should imply that they have a large variation distance--equivalently, if two Gaussians are close in variation distance it's hard for their ...
- 777
19
votes
2
answers
2k
views
Higher or lower?
Consider the following game - I draw a number from $[0, 1]$ uniformly, and show it to you. I tell you I am going to draw another $1000$ numbers in sequence, independently and uniformly. Your task is ...
- 6,155
19
votes
2
answers
2k
views
Is the tensor product of polyhedra a polyhedron?
Conventions: A polytope in a finite-dimensional $\mathbb R$-vector space $V$ is defined to be a convex hull of finitely many points in $V$. A polyhedron in a finite-dimensional $\mathbb R$-vector ...
- 33.8k
19
votes
1
answer
701
views
Estimates for Symmetric Functions
Let $z_1,z_2,\ldots,z_n$ be i.i.d. random variables in the unit circle. Consider the polynomial
$$
p(z)=\prod_{i=1}^{n}{(t-z_i)}=t^n+a_{1}t^{n-1}+\cdots+a_{n-2}t^2+a_{n-1}t+a_n
$$
where the $a_i$ are ...
- 3,626
19
votes
1
answer
859
views
Fictitious density of paths of diffusion processes outside the Cameron--Martin space
Let $X_t$ be an $n$-dimensional diffusion process satisfying the following Itō SDE over $[0,1]$:
$$dX_t = f(X_t)\,dt + dW_t,$$
where $W_t$ is an $n$-dimensional Wiener process and $f$ is of class $C^...
19
votes
1
answer
1k
views
Horst Knörrer's Permutation Cancellation Problem
The Problem:
The following question of Horst Knörrer is a sort of toy problem coming from mathematical physics.
Let $x_1, x_2, \dots, x_n$ and $y_1,y_2,\dots, y_n$ be two sets of real numbers.
We ...
- 24.7k
19
votes
2
answers
2k
views
Graph with Poisson Clock at each Vertex
Let $G$ be a connected, undirected graph, with countably infinite set of vertices and countably infinite set of edges. Assume that the degree of each vertex is finite, and moreover, the degrees of all ...
- 403
19
votes
1
answer
1k
views
Zinn's "doubling" conjecture on weighted sums of independent Rademacher random variables
Let $a_1,\dots,a_n$ be real numbers such that $a_1^2+\dots+a_n^2=1$. Let $\eta_1,\dots,\eta_n$ be independent Rademacher random variables (r.v.'s), so that $P(\eta_i=\pm1)=\frac12$ for all $i$. Let $S:...
- 128k
19
votes
1
answer
448
views
Precise estimate for probability an $n$-point set has diameter smaller than $1$
This question was inspired by an earlier question that I answered but would like a more precise bound for.
Consider random points $x_1, \dots, x_n$ in the unit ball in $\mathbb R^d$, uniformly and ...
- 148k
19
votes
0
answers
3k
views
What does a product of many Gaussian matrices converge to?
Let $A$ be a product of $n$ $d\times d$ matrices with IID standard Gaussian entries and consider the value of $g(x)=x f(x)$ where $f(x)$ is the density of squared singular values of $A/\|A\|$.
Is ...
- 2,442
19
votes
0
answers
682
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 ...
- 1,839
19
votes
0
answers
988
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$.
For ...
- 5,721
18
votes
9
answers
25k
views
Why isn't likelihood a probability density function?
I've been trying to get my head around why a likelihood isn't a probability density function. My understanding says that for an event $X$ and a model parameter $m$:
$P(X\mid m)$ is a probability ...
- 283