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)...


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 ...


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-...


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 ...


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] ...


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 ...


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 ...


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 ...


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 ...


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