Given $m$ points in $\mathbb{R}^N$, the Johnson-Lindenstrauss lemma guarantees the existence of a linear operator $\mathbb{R}^N\rightarrow\mathbb{R}^n$ that nearly preserves pairwi …

The following statement about finite differences of the positions of the ordered multiset of factors of $n$ in the sequence of primes seems to be true based on my empirical tests. …

Suppose I have a collection of polynomials with multiple variables (more polynomials than variables, say), and I'm given noisy versions the values of these polynomials at a certain …

Let $X_n$ be a random variable distributed on $A_n:=\{1, \ldots, n\}$ and $g_n\colon A_n \to A_n$ such that $\Pr\big(X_n \neq g_n(X_n)\big) \to 0$. Putting $Y_n=g(X_n)$ then by Fan …

Here by «algorithm» I mean a (halting) Turing machine with finite alphabet and memory. Is it possible to obtain by purely existential (i.e. non-constructive) means the existence …

I have $n$ variables $b_1,\ldots,b_n$, each one $b_k\in {0,1}.$ Associated to each binary vector ${\bf b}=[b_1,\ldots,b_n]$ there are strictly positive function values $f({\bf b})$ …

Let $n \in \mathbb N$, and $s: \mathbb N \rightarrow \mathbb N,\ p: (\mathbb N \rightarrow \mathbb N) \rightarrow \mathbb N$ be defined as follows: $$ s(x) = x + 1; \\ p(f) = c(1), …

There is a well-known theorem, firstly obtained by Denes Petz, in quantum information theory, which is described as follows: $\mathbf{Theorem.}$ Let $\rho$ and $\sigma$ be two sta …

There are several different definitions of relative entropy, and some of them are not equivalent. Following is the definition we will use in this question. Let $M$ be a closed man …

In Terry Tao's notes on Concentration of measure, Exercise 7 indicates that the Chernoff bound can be generalized to sub-exponential random variables: http://terrytao.wordpress.co …

I met with a problem when I am reading a paper "On the Redundancy of Slepian-Wolf Coding" by He, DK; Lastras-Montano, LA; Yang, EH; Jagmohan, A; Chen, J, IEEE TRANSACTIONS ON INFOR …

Hi, $P_1$, $P_2$, $P_3$ are probability distributions defined on the same support. Knowing that $H(P_1) < H(P_2) < H(P_3)$, can we compare $D_{KL}(P_2,P_1)$ and $D_{KL}(P_3 …

Short version Gibbs's inequality is a simple inequality for real numbers, usually understood information-theoretically. In the jargon, it states that for two probability measures …

Consider $w(t)$ as Guassian random process, with $w(t)$ being $\mathcal{N}(\mu,\sigma)$ and i.i.d for all t. I consider applying a (stochastic)derivative operation to the random p …

For two pmf $p=\lbrace p_i\rbrace$ and $q=\lbrace q_i\rbrace$ on the same finite alphabet, we know that relateive entropy $D(p\|q)=\sum p_i\log\frac{p_i}{q_i}$ and 1-norm $\|p-q\|_ …