18

A set of points on the unit sphere in ${\Bbb R}^n$ with $\langle x,y\rangle \le \cos \theta$ for all distinct $x$ and $y$ is called a spherical code with minimum angle $\theta$. For $0<\theta < \pi/2$, Kabatiansky and Levenshtein gave an exponential upper bound (of the form $\exp(C(\theta)n)$) for the maximum number of points in such a spherical code. ...


13

It is a theorem of Besicovitch that measures on $\mathbb R^d$ do satisfy the density theorem. Fremlin, Measure Theory, Chap. 47 added Besicovitch, around 1930, extended his density properties of sets to those of finite Hausdorff measure. source next: D. G. Larman, "A new theory of dimension", Proc. London. Math. Soc. 17 (1967) 178-192 ...


13

$\newcommand{\ep}{\varepsilon} $ Let $X$ be any nonnegative random variable (r.v.) with finite mean $\mu>0$ and variance $\sigma^2<\infty$. For any real $u>0$, we have $\ln\frac xu\le\frac xu-1$ for all real $x>0$, whence $x\ln x\le\frac{x^2}u+x\ln\frac ue$ and \begin{equation*} EX\ln X\le\frac{EX^2}u+EX\ln\frac ue=\frac{\sigma^2+\mu^2}u+\mu\...


9

This inequality cannot be true. Let us rewrite it in the more common form $$P(R_n\ge x)\le e^{-x^2/2} \tag{1} $$ for $x\ge0$, where $R_n:=S_n/b_n$, $S_n:=\sum_1^n c_iB_i$, $b_n:=\sqrt{\sum_1^n c_i^2}$. Let $n=2$, $c_1=1$, and $c_2=aI\{B_1=-1\}$, where $I\{\cdot\}$ denotes the indicator function, $a>0$ is large enough so that $\frac{-1+a}{\sqrt{1+a^2}}&...


9

We have $$ C(W) = 2 A \circ A + v v^\top$$ where $v$ is the vector with entries $\|w_i\|^2$, $A$ is the Wishart matrix with entries $w_i^\top w_j$, and $\circ$ is the Hadamard product. From the Schur product theorem (and the fact that adding a positive semi-definite matrix to a self-adjoint matrix only serves to increase the least eigenvalue $\lambda_1$) we ...


8

From the area estimates you get that that for fixed $\varepsilon>0$ this number, say $M_\varepsilon(n)$, grows quite fast. Direct calculations show that the total area of the locus of unit vectors in $\mathbb{R}^{n}$ which are not $\varepsilon$-perependicular to the given vector $u$ is about $$2\cdot e^{-(n-2)\cdot\varepsilon^2/2}\cdot\mathop{\rm area}\...


8

Exponential inequalities for sums of independent random variables (r.v.'s) can be extended to martingales in a standard and completely general manner; see Theorem 8.5 or Theorem 8.1 for real-valued martingales, and Theorem 3.1 or Theorem 3.2 for martingales with values in 2-smooth Banach spaces in this paper. In particular, Theorem 8.7 in the same paper ...


7

For $p>1$, the random variables you discuss do not possess exponential moments; You are in the regime of large deviations with stretched exponential tails. See for example the following recent paper by Gantert, Ramanan and Rembart http://arxiv.org/abs/1401.4577 (and the back references, going to Nagaev and earlier).


7

Basically, the proof goes along the following lines: (1) Take a small $\varepsilon>0$ and show that the expected exit time from the interval $[-\varepsilon\sqrt{vl},\varepsilon\sqrt{vl}]$ is less than $\varphi l$ (this is standard, using the fact that your martingale squared becomes a submartingale with uniformly positive drift, see e.g. Example 7.1 of ...


7

Let $X_i=(X_{i,1},\dots,X_{i,d})$, $S:=(S_1,\dots,S_d)$, $S_j:=\sum_{i=1}^d X_{i,j}/\sqrt n$. Then, by Hoeffding's inequality, for $s\ge0$ $$P(|S_j|\ge s)\le2e^{-s^2/2},$$ whence $$E\|S\|_\infty=\int_0^\infty ds\,P(\|S\|_\infty\ge s) \le\int_0^\infty ds\,\min(1,2d\,e^{-s^2/2}) =O(1+\sqrt{\ln d});$$ here we used the inequality $$\int_t^\infty ds\,e^{-s^2/2}\...


7

Let $n:=N$. Let us show that for all natural $n$ and all $p\in(0,1)$ $$P(A_n>\sqrt p)\le\frac{\sqrt p+p}{1+p},\tag{1}$$ so that $P(A_n>\sqrt p)\to0$ whenever $p\downarrow0$. Consider first the case when $n\ge1/\sqrt p$, so that $1/n\le\sqrt p$. In view of Cantelli's inequality, $$\begin{aligned} P(A_n>\sqrt p)&\le\frac{p(1-p)/n}{p(1-p)/n+(\sqrt ...


6

A possible relevant post What kind of random matrices have rapidly decaying singular values?. In that post I discussed the distribution of maximal eigenvalue of a random matrix based on the result [Johnstone]. However that answer does not fully answer your question since there I emphasized the fact that the maximal eigenvalues of most random matrices in ...


6

The general idea behind such inequalities is to follow the martingale $X$ until you lose control over the differences, then force it to be constant. This defines a new martingale $Y$ with bounded differences, which is therefore concentrated. You then add to your probability of error the probability that the differences of $X$ are too large, so that $Y \neq ...


6

For any $\beta>0$, $$\mathbb{E}B(n,p)^k\leq k!\beta^{-k}\mathbb{E}e^{\beta B(n,p)}= k!\beta^{-k}(1-p+pe^{\beta})^n.$$ Now you can plug various $\beta$, e.g. $\beta=\frac{k}{np}$ which yields $$\mathbb{E}B(n,p)^k\leq (np)^k k!k^{-k}\left((1-p)+pe^{\frac{k}{pn}}\right)^n.$$ I assume that you got your estimate by elaborating on this expression, although in ...


6

By the Tsirel’son--Ibragimov--Sudakov argument, reviewed on the first page in Bobkov, pushing the measure forward from the cube to the canonical Gaussian on $\mathbb R^n$ and using the Gaussian isoperimetric inequality, we have \begin{equation} 1 - \mu_{\infty}(A_r)\le B(r):= B_p(r):= 1-\Phi\big(r\sqrt{2\pi}+\Phi^{-1}(p)\big), \end{equation} where $r\...


6

On the one hand, the proof is very cheap. Let $Z_j=e^{2\pi iX_j}$. $X=\sum_j X_j$, $Z=e^{2\pi i X}$. Note that $\operatorname{Var}_{\mathbb R/\mathbb Z}X\approx 1-|EZ|$ and similarly for $X_j$ and $Z_j$. Now just use the identity $EZ=\prod_j EZ_j$ to conclude. On the other hand, finding the reference may be a highly non-trivial task, so I leave it to ...


6

$\newcommand{\R}{\mathbb{R}} \renewcommand{\P}{\operatorname{\mathsf P}} \newcommand{\Ga}{\Gamma} \newcommand{\de}{\delta}$ In view of the spherical symmetry of the distribution of the $l$-dimensional subspace, we can fix it to be, say, the span of the first $l$ vectors of the standard basis of $\R^n$ and, accordingly, let $v=:(Y_1,\dots,Y_n)$ be a random ...


6

I streamlined my proof a bit so it is postable now :-) First, a disclaimer. I have no doubt that there is some slick theorem dating back to 1980's that immediately implies what you want and all one needs is to wait for a while until someone posts a reference to it. Meanwhile, here is a crude computation that gives a rather dismal value of $\alpha$ but still ...


6

Without loss of generality, $R=1$. Let $Z_1,\ldots,Z_n$ be iid standard normal random variables (r.v.'s). Then \begin{equation} \sqrt n\, X_1\overset{\text{D}}=\frac{\sqrt n\,Z_1}{\sqrt{Z_1^2+\cdots+Z_n^2}} \overset{\text{D}}= \frac{Z_1+\cdots+Z_n}{\sqrt{Z_1^2+\cdots+Z_n^2}}=:T_1, \end{equation} where $\overset{\text{D}}=$ denotes the equality in ...


6

First, we need to fix the notation a bit. Let $X_1,X_2,\dots$ be iid zero-mean unit-variance random variables (r.v.'s). For each natural $n$, let the $n$-tuple $(J_1,\dots,J_n):=(J_{n,1},\dots,J_{n,n})$ of r.v.'s be independent of the $X_k$'s and have the multinomial distribution with parameters $n,1/n,\dots,1/n$. For each $k\in[n]:=\{1,\dots,n\}$, the ...


6

The desired statement will not hold. E.g., suppose that $n\ge2$; $X_1,\dots,X_n,Y_1,\dots,Y_n$ are independent; $p=1/2$; $T=1_{X_1\ne Y_1}+n1_{X_1=Y_1}$; and $\delta=1/2$. Then $\mu:=p\,ET>n/4\to\infty$ (as $n\to\infty$), so that $1-\exp(-c\delta^2\mu )\to1$ for any fixed $c>0$. However, $$P\Big(\sum_{i=1}^TY_i\notin(1\pm\delta)\sum_{i=1}^TX_i\Big) \...


6

Your inequality is trivial and useless as written. On its left-hand side we have a probability which is $\le1$ and goes to $0$ as $t\to\infty$, whereas on the right-hand side we have an expression which is $\ge1$ and goes to $\infty$ as $t\to\infty$, because for any good rate function $I$ on $[0,\infty)$ we have $I(t)\to\infty$ as $t\to\infty$. Also, the ...


5

What you have is called an empirical process, although it is usually written with the points and the functions reversed: let $\mathcal{F}$ be a family of functions $\Omega \to \mathbb{R}$ and let $X_1, \dots, X_n$ be i.i.d. elements of $\Omega$. The empirical process indexed by $\mathcal{F}$ is the collection of random variables $\{Z_f : f \in \mathcal F\}$ ...


5

Actually, Bernstein's inequality does not really require boundedness of the i.i.d. random summands; a finite exponential moment of the absolute value of a random summand will suffice. However, here we can just use Markov's inequality. Let $X,X_1,\dots,X_n$ be independent identically distributed random variables (i.i.d. r.v.'s) such that $P(X=z)=\mu(z)\in(0,...


5

Here's a step that seems nice enough to point out. It still leaves a parameter to pick, and I'm not sure it's ever better than applying Bernstein, but it does something different. We can get a probability bound in terms of how much $S_n$ exceeds the Renyi entropy $H_{\alpha}$ of $\mu$ (equivalently, worded in terms of the $\ell_{\alpha}$ norm of $\mu$), for ...


5

An almost complete answer. First of all, indeed the $\lVert \alpha\rVert_2$-based bound mentioned in the question can be shown to be tight for many "simple" $\alpha$'s, such as balanced, or uniform/balanced on a subset of $m$ coordinates. However, it is not tight in general, and the right answer appears to be captured by a quantity, the $K$-functional ...


5

The preprint "Random Point Sets on the Sphere --- Hole Radii, Covering, and Separation" by Johann S. Brauchart, Edward B. Saff, Ian H. Sloan, Yu Guang Wang, and Robert S. Womersley gives the following result in Corollary 3.4: $\mathbb{E}[N^{2/d}\Theta_\text{min}]\to C_d = (\kappa_d/2)^{-1/d}\Gamma(1+\tfrac{1}{d})$ as $N\to\infty$ It also gives a bound on ...


5

This looks like a weak law of large numbers, and in fact a strong law holds: I claim that $\liminf_{t \to \infty} \frac{S_t}{t} \ge \Delta$ almost surely, which implies the desired result. The key is to show that $\frac{M_t}{t} \to 0$ almost surely. Then we have $\frac{S_t}{t} = \frac{M_t}{t} + \frac{D_t}{t} \ge \frac{M_t}{t} + \Delta$ and can take the ...


5

This is worked out in some detail in the paper of Fan, Grama and Liu, J. Math Anal. Appl. 448 (2017), 538-566 (see in particular Theorem 2.1 there, and the references). Unfortunately I do not have an open access to an electronic copy, and it doesn't seem to exist on arXiv.


5

It appears you want to have the following: Let $X_1,\dots,X_n$ be independent zero-mean random variables (r.v.'s ) (or, more generally, martingale-differences) with $S_n:=X_1+\dots+X_n$, $B^2:=EX_1^2+\dots+EX_n^2$, and $M:=\frac1n\sum_1^n M_i$, where $M_i:=\text{ess sup}|X_i|$. Then \begin{equation*} P(S_n\ge x)\overset{\text{(?)}}\le\exp-\frac{x^2}{...


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