Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Chebyshev's Inequality"

(Chebyshevs inequality)
 
m
 
(9 intermediate revisions by 7 users not shown)
Line 1: Line 1:
−
Chebyshev's inequality, named after [[Pafnuty Chebyshev]], states that if  
+
'''Chebyshev's inequality''', named after [[Pafnuty Chebyshev]], states that if  
 
<math> a_1\geq a_2\geq ... \geq a_n </math> and <math> b_1\geq b_2\geq ... \geq b_n </math> then the following inequality holds:
 
<math> a_1\geq a_2\geq ... \geq a_n </math> and <math> b_1\geq b_2\geq ... \geq b_n </math> then the following inequality holds:
  
−
<math>\displaystyle n \left(\sum_{i=1}^{n}a_ib_i\right)\geq\left(\sum_{i=1}^{n}a_i\right)\left(\sum_{i=1}^{n}b_i\right)</math>.
+
<math>n \left(\sum_{i=1}^{n}a_ib_i\right)\geq\left(\sum_{i=1}^{n}a_i\right)\left(\sum_{i=1}^{n}b_i\right)</math>.
  
 
On the other hand, if <math> a_1\geq a_2\geq ... \geq a_n </math> and  
 
On the other hand, if <math> a_1\geq a_2\geq ... \geq a_n </math> and  
 
<math> b_n\geq b_{n-1}\geq ... \geq b_1 </math> then:
 
<math> b_n\geq b_{n-1}\geq ... \geq b_1 </math> then:
−
<math>\displaystyle n \left(\sum_{i=1}^{n}a_ib_i\right)\leq\left(\sum_{i=1}^{n}a_i\right)\left(\sum_{i=1}^{n}b_i\right)</math>.
+
<math>n \left(\sum_{i=1}^{n}a_ib_i\right)\leq\left(\sum_{i=1}^{n}a_i\right)\left(\sum_{i=1}^{n}b_i\right)</math>.
 
==Proof==
 
==Proof==
 
Chebyshev's inequality is a consequence of the [[Rearrangement inequality]], which gives us that the sum <math>S=a_1b_{i_1}+a_2b_{i_2}+...+a_nb_{i_n} </math> is maximal when <math>i_k=k</math>.
 
Chebyshev's inequality is a consequence of the [[Rearrangement inequality]], which gives us that the sum <math>S=a_1b_{i_1}+a_2b_{i_2}+...+a_nb_{i_n} </math> is maximal when <math>i_k=k</math>.
Line 12: Line 12:
 
Now, by adding the inequalities:
 
Now, by adding the inequalities:
  
−
<math> \displaystyle \sum_{i=1}^{n}a_ib_i\geq a_1b_1+a_2b_2+...+a_n b_{n}</math>,
+
<math>\sum_{i=1}^{n}a_ib_i\geq a_1b_1+a_2b_2+...+a_n b_{n}</math>
  
−
<math> \displaystyle \sum_{i=1}^{n}a_ib_i\geq a_1b_2+a_2b_3+...+a_nb_1</math>,
+
<math>\sum_{i=1}^{n}a_ib_i\geq a_1b_2+a_2b_3+...+a_nb_1</math>
  
−
...
+
<math>\cdots</math>
  
−
<math> \displaystyle \sum_{i=1}^{n}a_ib_i\geq a_1b_n+a_2b_1+...+a_nb_{n-1}</math>
+
<math>\sum_{i=1}^{n}a_ib_i\geq a_1b_n+a_2b_1+...+a_nb_{n-1}</math>
  
 
we get the initial inequality.
 
we get the initial inequality.
 +
 +
[[Category:Algebra]]
 +
[[Category:Inequalities]]

Latest revision as of 19:32, 13 March 2022

Chebyshev's inequality, named after Pafnuty Chebyshev, states that if $a_1\geq a_2\geq ... \geq a_n$ and $b_1\geq b_2\geq ... \geq b_n$ then the following inequality holds:

$n \left(\sum_{i=1}^{n}a_ib_i\right)\geq\left(\sum_{i=1}^{n}a_i\right)\left(\sum_{i=1}^{n}b_i\right)$.

On the other hand, if $a_1\geq a_2\geq ... \geq a_n$ and $b_n\geq b_{n-1}\geq ... \geq b_1$ then: $n \left(\sum_{i=1}^{n}a_ib_i\right)\leq\left(\sum_{i=1}^{n}a_i\right)\left(\sum_{i=1}^{n}b_i\right)$.

Proof

Chebyshev's inequality is a consequence of the Rearrangement inequality, which gives us that the sum $S=a_1b_{i_1}+a_2b_{i_2}+...+a_nb_{i_n}$ is maximal when $i_k=k$.

Now, by adding the inequalities:

$\sum_{i=1}^{n}a_ib_i\geq a_1b_1+a_2b_2+...+a_n b_{n}$

$\sum_{i=1}^{n}a_ib_i\geq a_1b_2+a_2b_3+...+a_nb_1$

$\cdots$

$\sum_{i=1}^{n}a_ib_i\geq a_1b_n+a_2b_1+...+a_nb_{n-1}$

we get the initial inequality.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Chebyshev%27s_Inequality&oldid=172594"