All Questions
9,498 questions
18
votes
3
answers
8k
views
Number of invertible {0,1} real matrices?
This question is inspired from here, where it was asked what possible determinants an $n \times n$ matrix with entries in {0,1} can have over $\mathbb{R}$.
My question is: how many such matrices ...
- 32.1k
18
votes
2
answers
643
views
What is the expected value of an N-dim vector of uniform randoms that sum to 1 which have been sorted into descending order?
What is the expected value of an N-dimensional vector of uniformly distributed random numbers which sum to 1 and have been sorted in descending order?
Here is the algorithm for drawing a sample from ...
- 183
18
votes
4
answers
1k
views
Pennies on a carpet problem
I recently read the following "open problem" titled "Pennies on a carpet" in "An Introduction To Probability and Random Processes" by Baclawski and Rota (page viii of book, page 10 of following pdf),...
- 4,952
18
votes
1
answer
872
views
What's the probability that k + n^2 is squarefree, for fixed k?
While playing around with this question (when is the sum of two squares squarefree?), from some experimental computations (and bolstered by the fact that the density of squarefree positive integers is ...
- 14k
18
votes
4
answers
1k
views
Generalization of a mind-boggling box-opening puzzle
Motivation. Suppose we are given $6$ boxes, arranged in the following manner:
$$\left[\begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \end{array}\right]$$
Two of these boxes contain a ...
- 48.8k
18
votes
3
answers
2k
views
How do we express measurable spaces using type theory?
A measurable space $(X,\mathcal X)$ consists of a set $X$ equipped with a $\sigma$-algebra of subsets $\mathcal X$. I would like to write computer programs involving measurable spaces, but to the best ...
- 8,512
18
votes
3
answers
3k
views
Deciding membership in a convex hull
Given points $u, v_1, \dots,v_n \in \mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1, \dots, v_n$.
This can be done efficiently by linear programming (time polynomial in $n,m$) in ...
- 667
18
votes
2
answers
2k
views
Big Picture: What is the connection of Malliavin calculus with differential geometry?
I know that Paul Malliavin was heavily influenced by ideas from differential geometry while developing his calculus on Wiener space. But what are the concrete analogies between both areas of ...
- 313
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
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
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
4
answers
3k
views
Markov chain on groups
Let $G$ be a permutation group on the finite set $\Omega$. Consider the Markov chain where you start with an element $\alpha \in \Omega$ chosen from some arbitrary starting probability distribution. ...
- 85.6k
18
votes
1
answer
3k
views
Let a function f have all moments zero. What conditions force f to be identically zero?
Throughout, let $f$ be a Lebesgue measurable function (or continuous if you wish, but this is probably no easier). (Questions with distributions etc. are possible also but I want to keep things simple ...
- 1,990
18
votes
4
answers
4k
views
Concentration inequalities for the maximum of the rescaled/normalized sum of iid random variables
I am interested in concentration inequalities for the maximum of the rescaled/normalized sum of iid random variables.
Let $X_1,..., X_n$ be i.i.d random variables, $S_n$ their centered sum and $M_n$ ...
- 591
18
votes
3
answers
1k
views
Not-lonely runners
The lonely runner conjecture
has several formulations.
They all involve a number $n$ runners running on a circular track,
each with a different speeds, and the conjecture is that each runner is ...
- 151k
18
votes
3
answers
1k
views
Is there a natural measurable structure on the $\sigma$-algebra of a measurable space?
Let $(X, \Sigma)$ denote a measurable space. Is there a non-trivial $\sigma$-algebra $\Sigma^1$ of subsets of $\Sigma$ so that $(\Sigma, \Sigma^1)$ is also a measurable space?
Here is one natural ...
- 8,512
18
votes
3
answers
918
views
Can Gauss sums derandomize any heuristic arguments?
I've always been fascinated by the fact that the classical Gauss sum has absolute value $\sqrt p$, which is exactly what we would expect if we were to interpret the Gauss sum as a random walk. In ...
- 82.7k
18
votes
1
answer
2k
views
Probability of a point on a unit sphere lying within a cube
Suppose we have a ($n-1$ dimensional) unit sphere centered at the origin: $$ \sum_{i=1}^{n}{x_i}^2 = 1$$
Given some some $d \in [0,1]$, what is the probability that a randomly selected point on the ...
- 1,254
18
votes
1
answer
451
views
Is defining measures as functionals ever insufficiently general in practice?
Crossposting from Math Stack Exchange, as it has yet to receive any answers there; the original question is here.
The way I learned measures was as set functions on a $\sigma$-algebra with certain ...
- 183
18
votes
2
answers
966
views
Is there an axiomatic characterization of the entropy of a continuous random variable?
Let $X$ be a random variable taking values in $\{1,\ldots,n\}$, and let $p_i$ denote the probability of the event $\{X = i\}$. Shannon defined the entropy of $X$ to be the quantity
$$H(X) = -\sum_i ...
- 29.2k
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
2
answers
1k
views
In an Erdős–Rényi random graph, what is the threshold for the property "every edge is contained in at least one triangle"?
Let $G(n,p)$ denote the Erdős–Rényi random graph, where $n$ is the number of nodes and $p$ is the probability for each edge. I'm interested in precisely what range of $p$ the random graph has at least ...
- 7,857
18
votes
1
answer
2k
views
Looking for an appealing counterexample in probability
There is a commonly-encountered-but-wrong rule of thumb that says something like
If a probability distribution is positively skewed, its mean is greater than its median.
(You sometimes also see it ...
- 1,180
18
votes
2
answers
4k
views
When is the function of a median closer to the median of the function than the mean of the function is to the function of the mean?
Background
notation: RV= random variable, $\mu=$ mean $m=$ median
Jensen's Inequality considers the relationship between the mean of a function of an RV and the function of the mean of an RV.
If $f(...
- 225
18
votes
2
answers
1k
views
Random Walk on $\mathbb{R}$ with Uniformly Distributed Steps and "Reflective" Boundary at Origin
A particle lies on the real number line at the origin. For each step taken, the particle moves from its current position a distance (and direction) chosen equi-probably from range $[-1,r]$. However, ...
- 313
18
votes
1
answer
656
views
Does erosion mix faster than a riffle shuffle?
It is a famous result of Aldous and Diaconis1 that
seven shuffles are necessary and suffice to approximately
randomize 52 cards.2
Here the shuffles are the standard riffle shuffle, where the ...
- 151k
18
votes
1
answer
1k
views
Applications of the Giry monad in probability and statistics
In another thread, I asked about the $M$ endofunctor on the category $\operatorname{Meas}$ of measurable spaces, which sends a space $X$ to its space of measures $M(X)$.
Will Sawin described the ...
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
18
votes
1
answer
3k
views
Distribution of maximum of random walk conditioned to stay positive
I have an $n$ step random walk which starts at zero $X_0 = 0 = S_0$ where the steps $X_i$ are independent uniform random variates in $[-1,1]$, but the walk is conditioned on the hypothesis that it ...
- 747
18
votes
1
answer
890
views
Two conjectures about zero inner products and dissociated sets
The following problems come from something I worked on (with my coauthors) related to proving a new time lower bound for streaming problems. Having worked on these problems for some time with little ...
- 3,377
18
votes
1
answer
2k
views
Gini Coefficient and Renyi Entropy
Gini coefficient (aka Gini Index) is a quantity used in economics to describe income inequality. It is 0 for uniformly distributed income, and approaches 1 when all income is in hands of one ...
- 1,612
18
votes
1
answer
996
views
Existance of certain almost invariant functions related to amenability and piece-wise transformations
We would like very much to know the answer to the following question:
Let $\|\cdot\|$ be any norm on $\mathbb{Z}^d$ and let $W(\mathbb{Z}^d)$ be the group of all bijections of $\mathbb{Z}^d$ such ...
18
votes
2
answers
1k
views
An Entropy Inequality (generalized)
Let $X,Y$ be probability measures on $\{1,2,\dots,n\}$. For $0\le \alpha \le 1$, set $K=\sum_i X(i)^\alpha Y(i)^{1-\alpha}$ so that $Z:=\frac{1}{K}X^\alpha Y^{1-\alpha}$ is also a probability measure ...
- 351
18
votes
1
answer
2k
views
How big is the sum of smallest multinomial coefficients?
Given positive integers $n$ and $d$, let $S$ indicate the list of all $d$-tuples of non-negative integers $(c_1,\ldots,c_d)$ such that $c_1+\cdots+c_d=n$. Let $v_i$ be the value of the multinomial ...
- 2,442
18
votes
0
answers
571
views
Fundamental Theorem of Algebra via multiple integrals
Consider the product of complex linear monic polynomials times polynomials of degree less than $n$, that is $\big( (z-\lambda), p(z)\big)\mapsto (z-\lambda)p(z)$. If we represent a polynomial by its ...
- 60.5k
18
votes
0
answers
310
views
Profiles of very high dimensional functions
This question comes from trying to understand the recent success of deep neural nets. Neural networks just (crudely speaking) create a very complicated function of very many variables, and then ...
- 96.4k
18
votes
0
answers
584
views
Human Knot game [duplicate]
In the popular game "Human Knot", a group of people stands in a circle and each person grabs another person's hands at random (one with the left hand and one with the right hand). The goal is to ...
- 2,449
18
votes
0
answers
667
views
The lonely molecule
Suppose $n$ air molecules (infinitesimal points) are bouncing around in
a unit $d$-dimensional cube, with perfectly elastic wall collisions.
Let $k=n^{\frac{1}{d}}$.
For example, in 3D, $d=3$, with $n=...
- 151k
17
votes
13
answers
6k
views
Probability in number theory
I am hearing that there are some great applications of probability theory (or more general measure theory) to number theory. Could anyone recommend some good book(s) on that (or other types of ...
17
votes
2
answers
5k
views
Positive-Definite Functions and Fourier Transforms
Bochner's theorem states that a positive definite function is the Fourier transform of a finite Borel measure. As well, an easy converse of this is that a Fourier transform must be positive definite.
...
- 4,952
17
votes
4
answers
6k
views
Correlated Brownian motion and Poisson process
Is there an (easy) way to construct, on the same filtered probability space,a Brownian motion $W$ and a Poisson process $N$, such that $W$ and $N$ are not independent ?
I first asked this question ...
- 368
17
votes
4
answers
823
views
Sweep-segment bot: Will this random walk sweep the plane?
This model is inspired by the random behavior of the
Roomba sweeping robot.
Let a unit segment $ab$ in the plane be placed
initially with $a=(0,0)$ and $b=(1,0)$.
The segment is first rotated a ...
- 151k
17
votes
3
answers
6k
views
The cone of positive semidefinite matrices is self-dual? (reference needed)
I'm seeking a reference for the following fact.
The cone of positive semidefinite matrices is self-dual (a.k.a. self-polar).
This result is relatively easy to prove, has been known for a long time,...
- 1,513
17
votes
4
answers
2k
views
Good introduction to statistics from a algebraic point of view?
There are already lots of questions on this subject like
Is there an introduction to probability theory from a structuralist/categorical perspective?
Is there a combinatorial/topological treatment ...
- 283
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
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
3
answers
2k
views
The minimum of a sum of absolute values of inner products in $\mathbb{R}^d$
Consider a collection of unit vectors $v_1, \ldots, v_n$ in $\mathbb{R}^d$ (we think of $n$ being much larger than $d$). I would like to minimize the sum:
$$\sum_{i\neq j}|\langle v_i,v_j\rangle|.$$
...
- 2,288
17
votes
1
answer
9k
views
Intuitive understanding of the Stieltjes transform
I have been using random matrix theory in signal processing and have some trouble understanding what the Stieltjes transform does.
The gist of my work is that I have an $N\times N$ true covariance ...
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
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