16

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


11

You might be interested in something Jelani Nelson wrote me in an email on Oct. 13, 2011: "Another notion of derandomizing JL is the following: come up with a distribution over embeddings that can be sampled using as few random bits as possible so that, for any vector $x$ in $R^d$, a random vector has its $\ell_2$ norm preserved up to $1+\epsilon$ with ...


11

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


10

One useful trick that comes in handy sometimes (I originally saw it in this paper of Talagrand, though it may go further back): We can view a random permutation in $S_n$ as being generated as follows: Start with the identity permutation, and successively perform transpositions of the form $(n, a_n)$, then $(n-1, a_{n-1})$, and so on down to $(2, a_2)$, where ...


10

In the general case (especially for high codimension) there will not be such a relation: Every compact Riemannian manifold can be isometrically embedded into the Euclidean space $R^N$. As the image of the submanifold is compact, you can change the metric "near infinity" such that it defines a metric on the sphere $S^N.$ But in special cases, there might be ...


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


8

Yes, it is true for any $n$. The easiest way to see it is by using the fact that your condition means precisely that $X$ and $Y$ can be realized on the same probability space $\Omega$ in such a way that $Y\ge X$.


8

Without further assumptions you can't do better than the union bound (which should be $n e^{-\epsilon^2}$ as you've written things). If $X_i$ are identically distributed and the events $(|X_i| > \epsilon_0)$ are disjoint then you get equality in the union bound for the maximum whenever $\epsilon \ge \epsilon_0$. If the $X_i$ are $\epsilon$ times ...


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


7

For $n>100$ let $F_n = (k/n)_{k=1}^{n -1}$ and for $x= k/n $ in $F_n$ let $I_{k,n}$ be a symmetric interval around $x$ having length $n^{-n}/(n-1)$. Set $f_n = n^n \sum_{k=1}^{n-1} 1_{I_{k,n}}$. It is clear that $f_n$ converges weak$^*$ to $1_{[0,1]}$. But the $(f_n)$ are essentially disjointly supported and hence are equivalent to the unit vector ...


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


6

Short version: the set $\{\mu(B):B\in\mathcal{B}\}$ is a closed set for any probability space $(X,\mathcal{B},\mu)$. For atomic spaces this follows from an elementary topological argument, and for non-atomic spaces it is a closed interval by a classical (and easy) result of Sierpinski. Longer version with details: Let $A_n=A'_n\cup A''_n$ where $A'_n$ is ...


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

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

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


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


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

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


5

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


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