Namespaces
Variants
Actions

Difference between revisions of "Kolmogorov inequality"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (tex encoded by computer)
m (fix tex)
 
Line 15: Line 15:
  
 
$$  
 
$$  
\| x  ^ {(} k) \| _ {L _ {q}  }  \leq  \  
+
\| x  ^ {(k)} \| _ {L _ {q}  }  \leq  \  
 
C  \| x \| _ {L _ {r}  }  ^  \nu  \cdot
 
C  \| x \| _ {L _ {r}  }  ^  \nu  \cdot
\| x  ^ {(} n) \| _ {L _ {p}  } ^ {1 - \nu } ,
+
\| x  ^ {(n)\| _ {L _ {p}  } ^ {1 - \nu } ,
 
$$
 
$$
  
Line 26: Line 26:
 
\nu  = \  
 
\nu  = \  
  
\frac{n - k - p  ^ {-} 1 + q  ^ {-} 1 }{n - p  ^ {-} 1 + r  ^ {-} 1 }
+
\frac{n - k - p  ^ {-1} + q  ^ {-1} }{n - p  ^ {-1} + r  ^ {-1} }
 
  ,
 
  ,
 
$$
 
$$
Line 45: Line 45:
 
\omega ( \delta )  = \  
 
\omega ( \delta )  = \  
 
\sup \  
 
\sup \  
\{ {\| x  ^ {(} k) \| _ {L _ {q}  } } : {
+
\{ {\| x  ^ {( k)} \| _ {L _ {q}  } } : {
 
\| x \| _ {L _ {r}  } \leq  \delta ,\  
 
\| x \| _ {L _ {r}  } \leq  \delta ,\  
\| x  ^ {(} n) \| _ {L _ {p}  } \leq  1 } \}
+
\| x  ^ {( n)} \| _ {L _ {p}  } \leq  1 } \}
 
$$
 
$$
  
 
of the operator  $  D  ^ {k} $
 
of the operator  $  D  ^ {k} $
on the class  $  \{ {x \in L _ {r} } : {\| x  ^ {(} n) \| _ {L _ {p}  } \leq  1 } \} $
+
on the class  $  \{ {x \in L _ {r} } : {\| x  ^ {( n)} \| _ {L _ {p}  } \leq  1 } \} $
 
is expressed by the formula  $  \omega ( \delta ) = \omega ( 1) \delta $,  
 
is expressed by the formula  $  \omega ( \delta ) = \omega ( 1) \delta $,  
 
that is, Kolmogorov's inequality holds with constant  $  C = \omega ( 1) $.
 
that is, Kolmogorov's inequality holds with constant  $  C = \omega ( 1) $.
Line 77: Line 77:
 
\max _ {1 \leq  m \leq  n } \  
 
\max _ {1 \leq  m \leq  n } \  
 
\left |
 
\left |
\sum _ { k= } 1 ^ { m }  ( X _ {k} - a _ {k} ) \  
+
\sum _ { k=1 } ^ { m }  ( X _ {k} - a _ {k} ) \  
 
\right |
 
\right |
 
\geq  \epsilon \right \}
 
\geq  \epsilon \right \}
Line 83: Line 83:
 
\frac{1}{\epsilon  ^ {2} }
 
\frac{1}{\epsilon  ^ {2} }
  
\sum _ { k= } 1 ^ { n }  \sigma _ {k}  ^ {2} ,
+
\sum _ { k=1 } ^ { n }  \sigma _ {k}  ^ {2} ,
 
$$
 
$$
  
Line 92: Line 92:
 
$$  
 
$$  
 
1 -  
 
1 -  
\frac{( \epsilon + 2 c )  ^ {2} }{\sum _ { k= } 1 ^ { n }  \sigma _ {k}  ^ {2} }
+
\frac{( \epsilon + 2 c )  ^ {2} }{\sum _ { k=1 } ^ { n }  \sigma _ {k}  ^ {2} }
  
 
  \leq  {\mathsf P}
 
  \leq  {\mathsf P}
Line 98: Line 98:
 
\max _ {1 \leq  m \leq  n } \  
 
\max _ {1 \leq  m \leq  n } \  
 
\left |
 
\left |
\sum _ { k= } 1 ^ { m }  ( X _ {k} - \sigma _ {k} ) \  
+
\sum _ { k=1 } ^ { m }  ( X _ {k} - \sigma _ {k} ) \  
 
\right |
 
\right |
 
\geq  \epsilon \right \} .
 
\geq  \epsilon \right \} .
Line 105: Line 105:
 
These inequalities were established by A.N. Kolmogorov . Kolmogorov's inequality is remarkable both as to its proof (the method of argument in probability theory is new) and in the result itself (the estimate for the maximum of the sums is the same as that for the last sum in the Chebyshev inequality).
 
These inequalities were established by A.N. Kolmogorov . Kolmogorov's inequality is remarkable both as to its proof (the method of argument in probability theory is new) and in the result itself (the estimate for the maximum of the sums is the same as that for the last sum in the Chebyshev inequality).
  
In the proof of the Kolmogorov inequality essential use is made of the properties of conditional mathematical expectations of functions and sums  $  S _ {k+} p $
+
In the proof of the Kolmogorov inequality essential use is made of the properties of conditional mathematical expectations of functions and sums  $  S _ {k+p} $
 
under the condition that  $  X _ {1} \dots X _ {k} $
 
under the condition that  $  X _ {1} \dots X _ {k} $
 
are fixed. These properties arise from the independence of the  $  X _ {k} $.
 
are fixed. These properties arise from the independence of the  $  X _ {k} $.
Line 113: Line 113:
 
1) The Kolmogorov inequality remains true if the condition of independence of the variables  $  X _ {n} $
 
1) The Kolmogorov inequality remains true if the condition of independence of the variables  $  X _ {n} $
 
is replaced by the condition that  $  \{ X _ {n} \} $
 
is replaced by the condition that  $  \{ X _ {n} \} $
is an [[Absolutely-unbiased sequence|absolutely-unbiased sequence]], that is, if the sequence of sums  $  S _ {n} = \sum _ {k=} 1 ^ {n} X _ {k} $
+
is an [[Absolutely-unbiased sequence|absolutely-unbiased sequence]], that is, if the sequence of sums  $  S _ {n} = \sum _ {k=1}  ^ {n} X _ {k} $
 
forms a [[Martingale|martingale]].
 
forms a [[Martingale|martingale]].
  

Latest revision as of 19:16, 5 January 2021


Kolmogorov's inequality in approximation theory is a multiplicative inequality between the norms in the spaces $ L _ {s} ( J) $ of functions and their derivatives on the real axis (or half-line):

$$ \| x ^ {(k)} \| _ {L _ {q} } \leq \ C \| x \| _ {L _ {r} } ^ \nu \cdot \| x ^ {(n)} \| _ {L _ {p} } ^ {1 - \nu } , $$

where

$$ 0 \leq k < n,\ \ \nu = \ \frac{n - k - p ^ {-1} + q ^ {-1} }{n - p ^ {-1} + r ^ {-1} } , $$

and $ C $ does not depend on $ x $. Such inequalities were first studied by G.H. Hardy (1912), J.E. Littlewood (1912), E. Landau (1913), and J. Hadamard (1914). A.N. Kolmogorov [1] obtained the best possible constant $ C $ for the most important case $ J = ( - \infty , + \infty ) $, $ p = q = r = \infty $ and arbitrary $ k $, $ n $.

Kolmogorov's inequality is connected with problems of best numerical differentiation and the stable calculation of the (unbounded) operator $ D ^ {k} $ of $ k $- fold differentiation. In fact, the modulus of continuity

$$ \omega ( \delta ) = \ \sup \ \{ {\| x ^ {( k)} \| _ {L _ {q} } } : { \| x \| _ {L _ {r} } \leq \delta ,\ \| x ^ {( n)} \| _ {L _ {p} } \leq 1 } \} $$

of the operator $ D ^ {k} $ on the class $ \{ {x \in L _ {r} } : {\| x ^ {( n)} \| _ {L _ {p} } \leq 1 } \} $ is expressed by the formula $ \omega ( \delta ) = \omega ( 1) \delta $, that is, Kolmogorov's inequality holds with constant $ C = \omega ( 1) $.

Kolmogorov's inequality is a special case of inequalities relating to the imbedding of classes of differentiable functions (see Imbedding theorems).

References

[1] A.N. Kolmogorov, "On inequalities between the upper bounds of the successive derivatives of an arbitrary function on an infinite interval" Transl. Amer. Math. Soc. (1) , 2 (1962) pp. 233–243 Uchen. Zap. Moskov. Univ. Mat. , 3 : 30 (1939) pp. 3–16
[2] S.B. Stechkin, "Best approximation of linear operators" Math. Notes , 1 (1967) pp. 91–99 Mat. Zametki , 1 : 2 (1967) pp. 137–148
[3] L.V. Taikov, "Kolmogorov-type inequalities and the best formulas for numerical differentiation" Math. Notes , 4 (1968) pp. 631–634 Mat. Zametki , 4 : 2 (1968) pp. 233–238
[4] V.V. Arestov, "Precise inequalities between norms of functions and their derivatives" Acta Sci. Math. , 33 (1972) pp. 243–267 (In Russian)

Comments

Landau's work [a1] should be mentioned in particular: he initiated in 1913 a new kind of extremum problem, i.e. obtaining sharp inequalities between the supremum norms of derivatives. The analogue of Kolmogorov's theorem for the half-line $ \mathbf R _ {+} $ has been established by I.J. Schoenberg and A. Cavaretta [a3]; cf. also [a2]. For a beautiful survey concerning these problems see [a4]. Norm inequalities for the difference operator have been studied rather recently; see e.g. [a5].

References

[a1] E. Landau, "Einige Ungleichungen für zweimal differentierbare Funktionen" Proc. London Math. Soc. , 13 (1913) pp. 43–49
[a2] H.G. ter Morsche, "Interpolation and extremal properties of -spline functions" , Univ. Eindhoven (1982) (Thesis)
[a3] I.J. Schoenberg, A. Cavaretta, "Solution of Landau's problem concerning higher derivatives on the halfline" , Proc. Internat. Conf. Constructive Function Theory , Bulgarian Acad. Sci. (1972) pp. 297–308
[a4] I.J. Schoenberg, "The elementary cases of Landau's problem of inequalities between derivatives" Amer. Math. Monthly , 80 (1973) pp. 121–158
[a5] H.G. Kaper, B.E. Spellman, "Best constants in norm inequalities for the difference operator" Trans. Amer. Math. Soc. , 299 (1987) pp. 351–372

Kolmogorov's inequality in probability theory is an inequality for the maximum of sums of independent random variables. It is a generalization of the classical Chebyshev inequality in probability theory. Let $ X _ {1} \dots X _ {n} $ be independent random variables with finite mathematical expectations $ a _ {n} = {\mathsf E} X _ {n} $ and variances $ \sigma _ {n} ^ {2} = {\mathsf D} X _ {n} $. Then, for any $ \epsilon > 0 $,

$$ {\mathsf P} \left \{ \max _ {1 \leq m \leq n } \ \left | \sum _ { k=1 } ^ { m } ( X _ {k} - a _ {k} ) \ \right | \geq \epsilon \right \} \leq \frac{1}{\epsilon ^ {2} } \sum _ { k=1 } ^ { n } \sigma _ {k} ^ {2} , $$

and if the variables are bounded ( $ | X _ {i} | \leq c $ with probability $ 1 $), then

$$ 1 - \frac{( \epsilon + 2 c ) ^ {2} }{\sum _ { k=1 } ^ { n } \sigma _ {k} ^ {2} } \leq {\mathsf P} \left \{ \max _ {1 \leq m \leq n } \ \left | \sum _ { k=1 } ^ { m } ( X _ {k} - \sigma _ {k} ) \ \right | \geq \epsilon \right \} . $$

These inequalities were established by A.N. Kolmogorov . Kolmogorov's inequality is remarkable both as to its proof (the method of argument in probability theory is new) and in the result itself (the estimate for the maximum of the sums is the same as that for the last sum in the Chebyshev inequality).

In the proof of the Kolmogorov inequality essential use is made of the properties of conditional mathematical expectations of functions and sums $ S _ {k+p} $ under the condition that $ X _ {1} \dots X _ {k} $ are fixed. These properties arise from the independence of the $ X _ {k} $.

The Kolmogorov inequality admits numerous generalizations, of which one can mention the following.

1) The Kolmogorov inequality remains true if the condition of independence of the variables $ X _ {n} $ is replaced by the condition that $ \{ X _ {n} \} $ is an absolutely-unbiased sequence, that is, if the sequence of sums $ S _ {n} = \sum _ {k=1} ^ {n} X _ {k} $ forms a martingale.

2) If $ g ( t) \geq 0 $ is a convex monotone function and $ {\mathsf E} g ( | S _ {n} | ) < \infty $, then

$$ {\mathsf P} \left \{ \max _ {1 \leq m \leq n } \ | S _ {m} | \geq \epsilon \right \} \leq {\mathsf E} g ( | S _ {n} | ) \frac{1}{g ( \epsilon ) } . $$

3) If the $ X _ {k} $, $ k = 1 \dots n $, are symmetric about the origin, then

$$ {\mathsf P} \left \{ \max _ {1 \leq m \leq n } \ | S _ {m} | \geq \epsilon \right \} \leq 2 {\mathsf P} \{ | S _ {n} | \geq \epsilon \} ; $$

see Lévy inequality.

4) For arbitrary independent random variables $ X _ {1} , X _ {2} \dots $

$$ {\mathsf P} \left \{ \max _ {1 \leq m \leq n } \ | S _ {m} | > \delta + \epsilon \right \} \leq \frac{1}{1 - p } {\mathsf P} \{ | S _ {n} | > \epsilon \} , $$

provided that $ \delta > 0 $ and $ 0 < p < 1 $ are chosen so that $ {\mathsf P} \{ | S _ {m} | > \delta \} \leq p $ for all $ m $, $ 1 \leq m \leq n $.

The following property of sums of independent variables can be seen in all versions of Kolmogorov's inequality: The "spread" of the maximum sum has the same order of magnitude as the "spread" of the final sum.

Just as the Chebyshev inequality is applied in the derivation of the law of large numbers, so the Kolmogorov inequality is applied in the proof of the strong law of large numbers (the Kolmogorov criterion for convergence of $ S _ {n} / n \rightarrow 0 $ almost-everywhere). The proof of convergence theorems for series of random variables is based on the use of the Kolmogorov inequality.

References

[1a] A.N. Kolmogorov, "Ueber die Summen durch den Zufall bestimmter unabhängiger Grössen" Math. Ann. , 99 (1928) pp. 309–319
[1b] A.N. Kolmogorov, "Bemerkungen zur meiner Arbeit "Ueber die Summen durch den Zufall bestimmter unabhängiger Grössen" " Math. Ann. , 102 (1929) pp. 484–488
[2] A.N. Kolmogorov, "Foundations of the theory of probability" , Chelsea, reprint (1950) (Translated from German)
[3] M. Loève, "Probability theory" , Princeton Univ. Press (1963)

A.V. Prokhorov

Comments

References

[a1] W. Feller, "An introduction to probability theory and its applications", 2 , Wiley (1966) pp. Sect. VII.8
How to Cite This Entry:
Kolmogorov inequality. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Kolmogorov_inequality&oldid=47516
This article was adapted from an original article by Yu.N. Subbotin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article