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

answered Jan 29 '13 at 20:57

Kevin P. Costello

5,25611 gold badge2121 silver badges3333 bronze badges

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

answered Feb 25 '14 at 3:18

Anton Petrunin

35.1k55 gold badges9393 silver badges214214 bronze badges

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

answered Oct 23 '16 at 14:32

Nate Eldredge

25.1k44 gold badges8585 silver badges128128 bronze badges

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

#### Related Tags

measure-concentration × 239pr.probability × 194

st.statistics × 51

probability-distributions × 44

random-matrices × 34

inequalities × 26

stochastic-processes × 20

reference-request × 19

measure-theory × 19

gaussian × 19

martingales × 15

geometric-probability × 14

co.combinatorics × 9

fa.functional-analysis × 8

mg.metric-geometry × 8

asymptotics × 8

geometric-measure-theory × 7

dg.differential-geometry × 6

linear-algebra × 6

it.information-theory × 6

limits-and-convergence × 6

isoperimetric-problems × 6

large-deviations × 6

convex-geometry × 5

limit-theorems × 5