29

The similarity between the entropy power inequality and the Brunn-Minkowski inequality is not directly related to convexity - after all, Brunn-Minkowski can be generalised to bounded open sets that are not necessarily convex. (However, many of the proofs of both inequalities use ideas from convexity theory, of course.)
Taking the microstate (i.e. Boltzmann)...

answered May 25 '14 at 16:03

Terry Tao

77.1k2121 gold badges296296 silver badges380380 bronze badges

26

• Concerning question 2, you might want to take a look at Simulation of cubical particle packing under mechanical vibration (2016). The precise effect mentioned in the 2017 paper is not considered in that study, but a variety of ordering mechanisms are examined.
• Concerning question 1, the complexity of this mechanical problem (in the sense of many ...

answered Dec 16 '17 at 16:42

Carlo Beenakker

111k1010 gold badges269269 silver badges386386 bronze badges

24

Firstly, the proof given there doesn't really show that $p_n = O(n(\log n)^2)$
(at least not without further effort). Instead what it shows is that there are
$n$ for which $p_n = O(n(\log n)^2)$, and with a small effort that this holds for arbitrarily large $n$. As noted in the comments, the argument also gives that there are $n$ with $p_n = O(n (\log n) ...

18

OK, having spent about 20 hours on the search of a nice proof (which extinguished my passion for beauty for the next several days at least), I'm resorting to the brute force. I will love to see someone else to avenge this pitiful defeat of mine...
As I mentioned in the comment, the key to the solution is the inequality
$$
(1+a)\log(1+b)+(1+b)\log(1+a)\ge 2(...

18

$\newcommand{\R}{\mathbb{R}}$Actually, for compact subsets $A, B\subset \R^n$, the inequality
\begin{equation*}
m(A+B)^{1/n} \ge m(A)^{1/n} + m(B)^{1/n}
\end{equation*}
is ultimately nothing but the convexity of $\log(1+e^x)$ in disguise (whose convexity in turn follows immediately from the AM-GM inequality).
This idea, and the entire inductive proof may ...

18

I doubt that a mathematically rigorous explanation of the phenomenon discovered in that paper exists using today's technology. While mathematical statistical mechanics is a well-developed field of study, there is still much to be done before the applications of statistical mechanics by physicists can be made rigorous.
Any explanation should include a ...

16

Here is a pure existence proof of computability, where we show that a function is computable, not by exhibiting an explicit algorithm, but by providing a list of infinitely many algorithms, and proving that one of them computes the function; we just don't know which one.
(This answer is adapted from an answer I gave to Hans Stricker's question Non-...

answered Apr 5 '13 at 16:44

Joel David Hamkins

182k2828 gold badges545545 silver badges948948 bronze badges

13

If you are still not satisfied with any of the current answers, then I think the trouble is that you have not thought through clearly in your own mind what it means for it to be impossible to know some particular mathematical fact.
The first condition that you want to be satisfied is clear enough. You want it to be provably true that
There exists some ...

13

Maximum likelihood Estimation:
Let $X_1,\dots,X_n$ be independently and identically distributed observations from a distribution modeled by the parametric family $\mathcal{F} = \{P_{\theta}:\theta\in\Theta\}$. Let us suppose that all the distributions in $\mathcal{F}$ have a common finite support set $\mathcal{X}$. The maximum likelihood estimation (MLE) ...

13

The physical reason is that the cubically packed state has lower gravitational potential energy than the jammed random state. The overall process is analogous to annealing, although the reduction in energy in the latter case is to do with atomic bonding, not gravity.
For the process to work, it is necessary for the jostling to be enough to ease the elements ...

13

The earliest reference I have found for this result is Entropy and maximal spacings for random partitions (E. Slud, 1978).
Theorem 2.2 states that the entropy $W_n=-\sum_{i=1}^n p_i \ln p_i$ of the random partition is asymptotically normally distributed for $n\rightarrow \infty$ as ${\cal N}(\ln n +\gamma-1,\alpha_n)$, with $\alpha_n={\cal O}(1/n)$.
(Note ...

answered Feb 13 '19 at 12:39

Carlo Beenakker

111k1010 gold badges269269 silver badges386386 bronze badges

12

I'm not sure I would say I'm an expert in information geometry, I worked for several years as a postdoc in a lab that focuses on the subject. As a disclaimer, this is entirely my own opinion and others may disagree.
Since you asked this question, the research situation in the field has improved. Firstly, two separate books ([1$ $], [2$ $]) have been ...

12

The Kullback-Leibler divergence $D_{\rm KL}(Q||P)$ of two distributions $Q,P$ has been generalized to multiple distributions in various ways:
[1] information radius: $R(P_1,\ldots P_k)=\frac{1}{k}\sum_{i=1}^k D_{\rm KL}(P_i||k^{-1}\sum_i P_i)$
[2] average divergence: $K(P_1,\ldots P_k)=\frac{1}{k(k-1)}\sum_{i,j=1}^k D_{\rm KL}(P_i||P_j)$
[3,4] ...

answered Jul 14 '16 at 12:19

Carlo Beenakker

111k1010 gold badges269269 silver badges386386 bronze badges

12

Thanks for your interest. The term “conformal prediction” was suggested by Glenn Shafer, and at first I did not like it exactly for the reason that you mention: it has nothing (or very little) to do with conformal mappings in complex analysis. But then I discovered other meanings, even in maths; e.g., Wikipedia has five on its disambiguation page for “...

11

The Robertson-Seymour graph minor theorem shows that membership in any given minor-closed family of graphs can be checked in polynomial time. It even shows this can be done in $\mathcal{O}(n^3)$ time, but gives no bound on the size of the hidden constant.

11

Yes.
We take a fixed diophantine equation in variables $y,x_1, x_2, \ldots, x_k$.
Task: for an input $n \in \mathbb{Z}$, output either
Five values of $y$ for which solutions exist to the equation.
A solution to the equation for which $y=n$.
"No", in which case there must be no solution with $y=n$.
It is clear that for any diophantine equation, there is a ...

11

Pinsker's inequality states that
\begin{equation}
\text{KL}(f|g)\ge B_P:=\|f-g\|^2/2,
\end{equation}
where $\|f-g\|:=\int|f-g|$ is the total variation norm of the difference between the distributions with densities $f$ and $g$.
Another lower bound on $\text{KL}(f|g)$ can be given in terms of the Hellinger distance $d_H(f,g):=\frac1{\sqrt2}\|\sqrt f-\sqrt ...

11

The answer to your first question is no: $D(Q||P)$ may be however large while $D(P||Q)$ is however small. E.g., let $P$ have masses $s$ and $1-s$ at points $0$ and $1$, respectively, and let $Q$ have masses $t$ and $1-t$ at points $0$ and $1$, respectively, where $0<s,t<1$. Then
\begin{equation}
D(P||Q)=s\ln\frac st+(1-s)\ln\frac{1-s}{1-t},
\end{...

10

Pinsker's inequality has many proofs. My favorites include Pollard's short but "magical" proof,
https://www.cs.bgu.ac.il/~asml162/wiki.files/pollard-pinsker.pdf
and surely the Proof from the Book is via Hoeffding's inequality+Fenchel-Lagrange duality, as in Theorem 2.16 Massart's book:
http://www.cmap.polytechnique.fr/~merlet/articles/probas_massart_stf03....

10

It seems natural to work with an algebraically closed field of characteristic $p$, or, less restrictively, a splitting field of characteristic $p$ for $G$. For example, any field containing the primitive $m$-th roots of unity, where $|G| = p^{a}m$ and $p$ dos not divide $m$, so I assume now that $k$ is algebraically closed of characteristic $p.$ We have ...

answered Jul 18 '12 at 20:13

Geoff Robinson

35.3k33 gold badges9797 silver badges136136 bronze badges

10

The trick is to use appropriate units or scaling for the different edges of the rectangular parallelopiped when computing its volume. More specifically, apply the uniform probability argument (i.e., the isoperimetric inequality) to the probabilities
$$\tilde{p}_i = \frac{1}{n}\text{ and }
\tilde{q_i} = \frac{q_i}{p_i}\left(\sum \frac{q_i}{p_i}\right)^{-1}.
$...

10

Take any open question Q. ("Is the Riemann hypothesis true"? "Is P=NP?" etc)
There is an algorithm that will answer Q correctly.
It is trivial to prove (in classical logic) that one of the following programs works:
Program 1: Print "yes".
Program 2: Print "no".

10

This is a theorem of K. Berg, that the Haar measure is the measure of maximal entropy for automorphisms of compact groups. See, for example, these lecture notes.
An information-theoretic approach has been developed in the context of scattering theory, mainly for the unitary group, but I imagine the results are readily transposed to the orthogonal group. The ...

answered Apr 18 '14 at 19:49

Carlo Beenakker

111k1010 gold badges269269 silver badges386386 bronze badges

10

One related result is the Chernoff characterization of the best achievable exponent in Bayesian hypothesis testing. Given $X_1,\ldots,X_n$ i.i.d., ($X_k \in {\cal X}$, which is a finite set, for $k=1,\ldots,n$) from the distribution $\mathbb{Q}$ and two hypotheses $$H_k:\mathbb{Q}=\mathbb{P}_k$$ with $k=1,2$ and prior probabilities $\pi_k,$ the overall ...

10

Claim. If $\|P-Q\|\leq\varepsilon\leq\frac{1}{2}$, then $|H(P)-H(Q)| \leq H(\varepsilon) + \varepsilon\log N$.
Proof.
Let $\varepsilon':=\|P-Q\|$.
Let $(X,Y)$ be an optimal coupling of $P$ and $Q$, so that
\begin{align}
\mathbb{P}(X\neq Y) = \|P-Q\| \;.
\end{align}
Using a standard construction, we can assume that $X$ and $Y$ have the particular form
\...

9

If you understand the case of equal weights, the general case following by a simple trick. I'll do your example of maximizing $q_1^2 q_2$ for $q_1+q_2=1$.
Set $(r_1, r_2, r_3) = (q_1/2, q_1/2, q_2)$. Then our goal is to maximize $r_1 r_2 r_3$ subject to the side constraints $r_1+r_2+r_3=1$ and $r_1=r_2$. By the equal weights case, the maximum of $r_1 r_2 ...

answered Feb 25 '13 at 13:57

David E Speyer

124k1010 gold badges316316 silver badges599599 bronze badges

9

As I understand the problem, the expected value is
$$\frac{\sum_{i=0}^k i\binom{n}{i}}{\sum_{i=0}^k \binom{n}{i}}$$ which, for $k=n$, reduces by nice identities to $\frac{n}{2}$.
I don't know of nice formulas for partial sums of (weighted) binomial coefficients. Below are the simplified expressions for small values of $k$.
$k=1$: $\frac{n}{n+1} \sim 1$,
$...

8

Contrary to what some of the commenters said, there's no great difficulty in generalizing Kolmogorov complexity to infinite strings. For example, given a language L⊆{0,1}*, we could let K(L) be the length of the shortest program that decides L, or K(L)=∞ if L is undecidable. (Or we could also talk about programs that recognize L, in which ...

8

The basic roadblock for a finite group over a finite prime field (whether or not the characteristic divides the group order) is clear-cut: you rarely get all of the absolutely irreducible representations of the group over the prime field, which is equally a problem when working over $\mathbb{Q}$. You always get various irreducible reprsentations living in ...

answered Jul 18 '12 at 20:46

Jim Humphreys

48.9k44 gold badges100100 silver badges207207 bronze badges

Only top voted, non community-wiki answers of a minimum length are eligible

#### Related Tags

it.information-theory × 464pr.probability × 178

st.statistics × 82

coding-theory × 68

entropy × 66

co.combinatorics × 54

reference-request × 33

probability-distributions × 33

inequalities × 23

graph-theory × 21

linear-algebra × 18

measure-theory × 17

information-geometry × 17

computer-science × 16

algorithms × 14

nt.number-theory × 13

mg.metric-geometry × 13

mp.mathematical-physics × 12

stochastic-processes × 12

computational-complexity × 11

quantum-mechanics × 11

real-analysis × 10

lo.logic × 9

ca.classical-analysis-and-odes × 9

dg.differential-geometry × 8