# Tag Info

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