All Questions
2,766 questions with no upvoted or accepted answers
222
votes
0
answers
18k
views
Why do polynomials with coefficients $0,1$ like to have only factors with $0,1$ coefficients?
Conjecture. Let $P(x),Q(x) \in \mathbb{R}[x]$ be two monic polynomials with non-negative coefficients. If $R(x)=P(x)Q(x)$ is $0,1$ polynomial (coefficients only from $\{0,1\}$), then $P(x)$ and $Q(x)$ ...
- 2,272
51
votes
0
answers
2k
views
Alternating colors on a line: infinitely often or converge?
Suppose we have intervals of alternating color on $\mathbb{R}$ (say, red / blue / red / blue / …). All intervals have independent length, with all red intervals distributed as $\mathbb{P}_{R}$, all ...
- 1,010
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
24
votes
0
answers
1k
views
conjectures regarding a new Renyi information quantity
In a recent paper http://arxiv.org/abs/1403.6102, we defined a quantity that we called the "Renyi conditional mutual information" and investigated several of its properties. We have some open ...
- 483
21
votes
0
answers
2k
views
The Fourier Transform of taking Eigenvalues
The purpose of this question is to ask about the Fourier transform of the map which associate to an $n$ by $n$ matrix its $n$ eigenvalues, or some function of the $n$ eigenvalues. The main motivation ...
- 24.7k
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
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
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
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
16
votes
0
answers
309
views
Randomized Pascal's triangle: What is the average of all the numbers?
This question was posted on MSE. It received some interesting responses, but no definite answer.
Let's build a variation of Pascal's triangle. We write $1$'s going down the sides, as usual. Then for ...
- 3,507
16
votes
1
answer
743
views
Inequalities for marginals of distribution on hyperplane
Let $H = \{ (a,b,c) \in \mathbb{Z}_{\geq 0}^3 : a+b+c=n \}$. If we have a probability distribution on $H$, we can take its marginals onto the $a$, $b$ and $c$ variables and obtain three probability ...
- 156k
16
votes
0
answers
851
views
Self-avoiding random walks that always turn
I am wondering if the statistics of self-avoiding random lattice-walks
on $\mathbb{Z}^2$
that turn left or right at each step (i.e., they cannot continue the
direction of the preceding step) have been ...
- 151k
16
votes
0
answers
2k
views
When does a correlated Brownian motion leave a square?
Let $B=(X,Y)$ be a correlated two-dimensional Brownian motion, that is, the components are standard Brownian motions and the covariance between $X_t$ and $Y_t$ is $t\rho$ for some
constant $\rho \in [-...
- 16.4k
16
votes
0
answers
1k
views
Optimal monotone families for the discrete isoperimetric inequality
Background: the discrete isoperimetric inequality
Start with a set $X=\{1,2,...,n\}$ of $n$ elements and the family $2^X$ of all subsets of $X$.
For a real number $p$ between zero and one, we consider ...
- 24.7k
15
votes
0
answers
398
views
Will a unit disk be completely covered by randomly placed disks of area $\pi,\frac{\pi}{2},\frac{\pi}{3},\dots$ with probability $1$?
On a "bottom" disk of area $\pi$, we place "top" disks of area $\pi,\frac{\pi}{2},\frac{\pi}{3},\dots$ such that the centre of each top disk is an independent uniformly random ...
- 3,507
15
votes
0
answers
477
views
Quantitative Skorokhod embedding
The Skorokhod embedding theorem says that any random variable $X$ with $\mathbb E X=0$ and $\mathbb E[X^2]<\infty $ can be written as $X=B_{\tau }$ where $B$ is a Brownian motion and $\tau $ is a ...
- 723
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
14
votes
0
answers
718
views
Lower bounds on analytic functions connected to Fox H
The question is related to the one I asked before and never got an answer to. Fourier transform of $f_a(x)= a^{-2}\exp(-|x|^a)$, $a \in (0,2)$, is decreasing in $a$ . I need to demonstrate that the ...
- 178
14
votes
0
answers
358
views
What is the asymptotic dynamics of the winning position in this game?
$n$ players indexed $1,2,...,n$ play a game of mock duel. The rules are simple: starting from player $1$, each player takes turns to act in the order $1,2,...,n,1,2,...$. In his turn, a player ...
- 2,619
14
votes
0
answers
1k
views
The threshold for a perfect matching in a random subgraph of a regular bipartite graph?
The following question seems very natural.
It is a well known consequence of Hall's Theorem that every regular bipartite graph has a perfect matching. Another classical result states that the ...
- 1,633
14
votes
0
answers
585
views
Apparent disparity between the results of two papers (nearest neighbours)
This is a follow up question this one on MSE, which can basically be summarised as Robert Abilock originally posed in American Monthly in 1967:
The Rifle-Problem:
$n$ riflemen are distributed at ...
- 1,903
14
votes
0
answers
629
views
Probability of many overlapping zero inner products on a circle
[Question edited and changed a little on June 14 2015]
Consider an $n$-dimensional vector $v$ with $v_i \in \{-1,1\}$. Now consider an $n$-dimensional vector $w$ with $w_i \in \{-1,0,1\}$. The ...
- 3,377
14
votes
0
answers
4k
views
Minimum tiling of a rectangle by squares
Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes).
Is there an efficient way to calculate this?
- 1,015
14
votes
0
answers
587
views
Why, and how badly, does the proof of "no percolation at the critical point in half-spaces" fail for full spaces?
The proof by Barsky et. al. that there is no percolation in half-spaces proceeds by a dynamic renormalization argument. The proof couples critical percolation in the half-space $\mathbb{H}^d$ with a ...
- 4,922
13
votes
0
answers
710
views
Minimizing total variation under constraint
For $p\in[0,1]$, we write $\mathrm{Ber}(p)$
to denote the Bernoulli measure on $\{0,1\}$;
that is, $\mathrm{Ber}(p)(0)=1-p$,
$\mathrm{Ber}(p)(1)=p$.
For $n\in\mathbb{N}$ and $p=(p_1,\ldots,p_n)\in[0,1]...
- 6,541
13
votes
0
answers
880
views
Arguments against Freiling's argument against Continuum Hypothesis
Freiling's axiom of symmetry ($\sf AS$) is known as a justification for falsity of Continuum Hypothesis. Freiling in his 1986 paper, Axioms of symmetry: throwing darts at the real number line, ...
13
votes
0
answers
412
views
Transitivity of balanced mass transport in Z
Given two atomic measures $\mu$ and $\nu$ on $\mathbb{Z}$, write $\mu \sim \nu$ iff there exist countable decompositions $\mu = \mu_1 + \mu_2 + \cdots$ and $\nu = \nu_1 + \nu_2 + \cdots$ along with ...
- 19.7k
13
votes
0
answers
509
views
First passage percolation on a random geometric graph in the large connectivity limit
Let $V_\rho\subset\mathbb{R}^2$ be a point set in the plane obtained from a Poisson process of density $\rho$. The random geometric graph $G_\rho$ is obtained from $V_\rho$ by connecting points that ...
- 3,927
13
votes
0
answers
1k
views
Constructive aspects of Caratheodory's theorem in convex analysis
Let me paraphrase Caratheodory's theorem in a probabilistic setup:
Let $X$ be a real-valued random variable. For $k = 1, \ldots, m$, let $f_k: \mathbb{R} \to \mathbb{R}$ be a continuous function such ...
- 1,839
12
votes
0
answers
704
views
From biased coins (and nothing else) to biased coins
Background
We're given a coin that shows heads with an unknown probability, $\lambda$. The goal is to use that coin (and possibly also a fair coin) to build a "new" coin that shows heads ...
- 697
12
votes
0
answers
196
views
UMD constant of finite dimensional spaces
For a Banach space $B$, its one-sided Unconditional Martingale Difference (UMD) constant $C^-_p$ (for $p \in (1,\infty)$) is the smallest value such that for all $B$-valued martingale difference ...
- 408
12
votes
1
answer
627
views
A function with unexpectedly simple Legendre transformation
Let $I(x) = \frac{1}{2\pi} \int_{-2}^2 \sqrt{4-y^2}\ln|x-y|dy$. Then $I(x)$ is a concave function and
\begin{equation}
I(x)=
\begin{cases}
\frac{1}{4}x^2-\frac{1}{2}, &\text{if } |x|\leq2 \\
\...
- 1,608
12
votes
0
answers
489
views
Is this extension of Hoeffding's inequality known?
Question Overview:
Is it already known that, when using Hoeffding's inequality to lower bound the mean of i.i.d. random variables, you can replace the upper bound on the random variables with the ...
- 399
12
votes
0
answers
825
views
Eigenvalues of permutations of a real matrix: how complex can they be?
This is sort of complementary to this thread. I’ll repeat the definitions here:
For a matrix $M\in GL(n,\mathbb R)$, consider the $n!$ matrices obtained by permutations of the rows (say) of $M$ and ...
- 13.4k
12
votes
0
answers
1k
views
American put option pricing by "binomial trees"
I'm teaching a financial mathematics course and have found a fascinating (to me) numerical phenomenon and wonder if anyone has studied it, or knows anything similar.
I'll try and give a description ...
- 23.2k
11
votes
0
answers
263
views
Which results in probabilistic group theory generalize from finite groups to compact Hausdorff groups (and which don't)?
Let $G$ be a finite group. It has been shown that:
If the probability that two randomly selected elements of $G$ generate an abelian group is greater than $5/8$, $G$ is abelian.
If the probability ...
- 495
11
votes
0
answers
307
views
Entropy, magnitude, diversity of finite metric spaces in number theory
I was reading the article by Tom Leinster, (Maximizing
diversity in biology and beyond, arXiv link), and find it very interesting.
Since I was searching for entropies of finite metric spaces I found
...
user6671
11
votes
0
answers
225
views
Functional Weak Convergence of Maximum Likelihood Estimator
Let $\hat{\theta}_n$ be the Maximum Likelihood Estimator of parameter $\theta$, where $n$ is the sample size. It is well-known that under sufficient regularity conditions, we have the asymptotic ...
- 87
11
votes
0
answers
381
views
Concerning Luzin-(N)-property
Definition: a function $f:\mathbb{R}\to \mathbb{R}$ has Luzin-(N)-Property if $f$ maps any null set to a null set.
By https://www.encyclopediaofmath.org/index.php/Luzin-N-property, it is known that ...
- 4,201
11
votes
0
answers
223
views
Savings property: A transformation which turns nonnegative martingales into uniformly integrable ones
Background
I work in a subfield of computability theory called algorithmic randomness. We have been using martingales as long as probability theory (going back to work of von Mises). However, since ...
- 6,287
11
votes
0
answers
638
views
Uncertainty principle in Entropy terms
Math Questions:
Consider Hilbert space $L_2(\mathbb{R})$ with a standard norm
$
||\psi|| = ( \int_{\mathbb{R}}{ |\psi(t)|^2 dt } )^{1/2},
$
and Fourier transform
$
(F\psi)(\xi) =
\int_{\...
- 580
11
votes
0
answers
536
views
Bounding the probability that a random variable is maximal
Question: Suppose we have $N$ independent random variables $X_1$, $\ldots$, $X_N$ with finite means $\mu_1 \leq \ldots \leq \mu_N$ and variances $\sigma_1^2$, $\ldots$, $\sigma_N^2$.
I am looking ...
- 119
11
votes
0
answers
601
views
High-dimensional geometry: Top-down Vs. Bottom-up
There are several ways to leverage one's intuition from low-dimensional geometry to understand high-dimensional phenomena. For example, one can get a clearer picture of the behaviour of high-...
- 1,666
11
votes
0
answers
426
views
Maximizing the volume in a family of subsets of a cube
Starting from a question in probability, I arrived to the following optimization problem.
Let $I:=[0, 1],$ and let $A$ be a Lebesgue measurable subset of the $n$-dimensional cube, $A\subset I^n.$ ...
- 60.5k
11
votes
1
answer
2k
views
Bounding the entropy of a convolution
Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$, such that $\sum _{x\in \mathbb{Z}_2^n} f(x)^2 = 1$ (so we can think of $\{ f(x)^2\} _{x\in \mathbb{Z}_2^n}$ as a distribution). It is natural ...
user17253
11
votes
2
answers
1k
views
Distribution of infinity-norm over the unit sphere
I need to compute probabilities of the form
$P( \Vert X \Vert_\infty < r ),$
where $X$ is a random variable of dimension $n$, drawn with a uniform distribution on the unit sphere $\mathcal{S}_{n-1}$...
- 617