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

answered Aug 29 '16 at 23:48

Gerald Edgar

35.5k44 gold badges105105 silver badges196196 bronze badges

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

answered Jan 28 '19 at 23:08

Iosif Pinelis

69.4k66 gold badges6666 silver badges125125 bronze badges

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

answered Jan 30 '21 at 19:34

Terry Tao

89.3k2424 gold badges344344 silver badges422422 bronze badges

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

37.3k66 gold badges107107 silver badges232232 bronze badges

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

answered Sep 25 '18 at 20:49

Iosif Pinelis

69.4k66 gold badges6666 silver badges125125 bronze badges

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

pr.probability probability-distributions limits-and-convergence measure-concentration geometric-probability

answered Nov 13 '18 at 14:19

Iosif Pinelis

69.4k66 gold badges6666 silver badges125125 bronze badges

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

answered Oct 23 '16 at 14:32

Nate Eldredge

27.2k44 gold badges9090 silver badges134134 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}{...

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

#### Related Tags

measure-concentration × 315pr.probability × 262

st.statistics × 77

random-matrices × 56

probability-distributions × 55

inequalities × 35

stochastic-processes × 26

reference-request × 25

gaussian × 23

geometric-probability × 22

measure-theory × 19

martingales × 16

fa.functional-analysis × 11

convex-geometry × 11

co.combinatorics × 9

mg.metric-geometry × 9

asymptotics × 9

limits-and-convergence × 9

linear-algebra × 8

geometric-measure-theory × 8

optimal-transportation × 8

large-deviations × 8

free-probability × 8

dg.differential-geometry × 7

lower-bounds × 7