User:Richard Pinch/sandbox-15

Ranked poset

A partially ordered set $(X,{\le})$ with a rank function $r : X \rightarrow \mathbf{N}$ such that $r(m) = 0$ for some minimal element $m \in X$, and $r(q) = r(p)+1$ when $q$ covers $p$: that is, $p. < q$ and there is no $x$ with $p < x < q$.

A graded poset is one in which every minimal element has rank $0$ and every maximal element has the same rank.

References

• K. Engel, Sperner Theory, Encyclopedia of Mathematics and its Applications 65, Cambridge (1997) ISBN 0-521-45206-6 Zbl 0868.05001

Cage

A trivalent graph with given girth and minimum number of vertices. A $k$-cage is a cage of girth $k$.

References

• W.T. Tutte, "Connectivity in graphs", Mathematical Expositions 15, University of Toronto Press (1966) Zbl 0146.45603

Girth

One of the numerical characteristics of a graph: the size of the smallest cycle in an undirected graph which is not a forest.

References

• W.T. Tutte, "Connectivity in graphs", Mathematical Expositions 15, University of Toronto Press (1966) Zbl 0146.45603

Subgaussian distribution

A probability distribution with tails comparable to those of the Gaussian distribution. A random variable $X$ with mean $\mu$ is sub-Gaussian if there is a positive constant $\sigma$ such that $$ \mathsf{E}[\exp(\lambda(X-\mu))] \le \exp(\lambda^2\sigma^2/2) $$ for all real $\lambda$.

Clearly any normal random variable $N(\mu,\sigma^2)$ is sub-Gaussian with parameter $\sigma$.

A random variable is sub-Gaussian if and only if it has a moment generating function satisfying $$ \mathsf{E}[\exp(\lambda X)] \le \exp(\lambda^2\sigma^2/2) $$ for all real $\lambda$.

References

• Martin J. Wainwright, "High-dimensional Statistics", Cambridge (2019) ISBN 978-1-108-49802-9

Markov inequality in probability theory

A simple inequality giving a bound on the probability of deviation of a random variable with finite expectation from a given value. Let $X(\omega)$ be a random variable. Then $$ \mathsf{P}\{|X| > \epsilon\} \le \frac{\mathsf{E}X}{\epsilon} \ . $$

The inequality follows from comparing the indicator function of the set $\{\omega : |X(\omega)| > \epsilon\}$ with the random variable $X/\epsilon$ and then taking expectations.

Application of Markov's inequality to the random variable $Y = (X-\mu)^2$ yields the Chebyshev inequality in probability theory. More generally, if $X$ has a central moment of order $k$ about $\mu$, then $$ \mathsf{P}\{|X-\mu| > \epsilon\} \le \frac{\mathsf{E}[|X-\mu|^k]}{\epsilon^k} \ . $$

If $X-\mu$ has a moment generating function in the neighbourhood $[-b,b]$ of zero, then for $0 \le \lambda \le b$ $$ \mathsf{P}\{|X-\mu| > \epsilon\} = \mathsf{P}\{\exp(\lambda|X-\mu|) > \exp(\lambda\epsilon)\} \le \frac{\mathsf{E}[\exp(\lambda|X-\mu|)]}{\exp(\lambda\epsilon)} $$ so that we obtain the Chernoff inequality $$ \log \mathsf{P}\{|X-\mu| > \epsilon\} \le \inf_{0\le\lambda\le b} \log \mathsf{E}[\exp(\lambda|X-\mu|)] - \lambda\epsilon \ . $$

References

• Geoffrey Grimmett, David Stirzaker, "Probability and Random Processes" (4th ed), Oxford (2020) ISBN 0-19-884759-9
• Martin J. Wainwright, "High-dimensional Statistics", Cambridge (2019) ISBN 978-1-1-8-49802-9

Steinitz exchange lemma

A lemma on linearly independent sets and spanning sets in a vector space from which it is possible to deduce that dimension is well-defined.

Let $X = \{x_1,\ldots,x_m\}$ be a linearly independent set and $Y = \{y_1,\ldots,y_n\}$ a spanning set in a vector space $V$. Then $m \le n$ and $Y$ can be re-ordered so that $\{x_1,\ldots,x_m,y_{m+1},\ldots,y_n$ is also a spanning set.

As a corollary, if $X$ and $Y$ are both bases (linearly independent and spanning) for $V$, then $n = m$. Hence all bases for $V$ have the same size, and this shows that the dimension of $V$ is well-defined.

References

• P. M. Cohn, "Classic Algebra" Wiley (2000) ISBN 047187731X

Hopf constant

A constant $q_\infty$ associated with the Milne problem in radiative transfer theory. It may be defined as $$ q_\infty = \frac{1}{\pi} \int_0^{\pi/2} \left({\frac{3}{\sin^2\theta} - \frac{1}{1-\theta\cot\theta}} \right) d\theta \ . $$ Its numerical value is $$ q_\infty = 0.7104460895 \dots\ . $$

References

• Steven R. Finch, Mathematical Constants, Cambridge University Press (2003) ISBN 0-521-81805-2 Zbl 1054.00001

Hoeffding inequality

A simple inequality giving a bound on the probability of deviation of a sum of independent random variables from a given value. Let $X_1,\ldots,X_n$ be independent sub-Gaussian random variables with means $\mu_i$ and sub-Gaussian parameters $\sigma_i$. Then $$ \mathsf{P}\left\{{\sum_{i=1}^n (X_i-\mu_i) > t }\right\} < \exp\left({-\frac{t^2}{2\sum_{i=1}^n \sigma_i^2} }\right) \ . $$ In particular, if the $X_i$ are bounded, $|X_i|<b$ then they are sub-Gaussian with parameter $b$ and the inequality takes the form $$ \mathsf{P}\left\{{\sum_{i=1}^n (X_i-\mu_i) > t }\right\} < \exp\left({-\frac{t^2}{2 n b^2} }\right) \ . $$

References

• Martin J. Wainwright, "High-dimensional Statistics", Cambridge (2019) ISBN 978-1-108-49802-9