2017-09-17

Proof of the Markov Inequality.

In the proof for the Markov Inequality in the August 30th Lecture, the asserted statement below shows greater than equal to:
.
`Pr[x ge k cdot E(x)] le 1/k`
.
However, in the proof, exclusively greater than is used:
.
`E(x) = sum_i i cdot p_i = sum_(i le k cdot E(x)) i cdot p_i + sum_(i > k cdot E(x)) i cdot p_i > k cdot E(x) cdot Pr[x>k cdot E(x)]`
.
I assume the inclusion of equality is intended based on the Wikipedia article (which uses a slightly different formulation of the expression).
In the proof for the Markov Inequality in the [[http://www.cs.sjsu.edu/faculty/pollett/256.1.17f/Lec20170830.html#(11)|August 30th Lecture]], the asserted statement below shows greater than equal to: . @BT@Pr[x ge k cdot E(x)] le 1/k@BT@ . However, in the proof, exclusively greater than is used: . @BT@E(x) = sum_i i cdot p_i = sum_(i le k cdot E(x)) i cdot p_i + sum_(i > k cdot E(x)) i cdot p_i > k cdot E(x) cdot Pr[x>k cdot E(x)]@BT@ . I assume the inclusion of equality is intended based on the [[https://en.wikipedia.org/wiki/Markov%27s_inequality|Wikipedia article]] (which uses a slightly different formulation of the expression).

-- Proof of the Markov Inequality
I didn't quite get your last sentence, but yeah, it was supposed to be an inequality not a strict inequality. The proof was based on Papadimitriou, but there was a typo in that book too. I added a little bit more to the proof to make it clearer.
I didn't quite get your last sentence, but yeah, it was supposed to be an inequality not a strict inequality. The proof was based on Papadimitriou, but there was a typo in that book too. I added a little bit more to the proof to make it clearer.

-- Proof of the Markov Inequality
Concerning the different formulation, the Wikipedia article used a more general form where `a=k \cdot E[x]`. Hence, their version of the Markov Inequality was:
.
`Pr[x \geq a] \leq \frac{E[x]}{a}`
.
Concerning the "equality" comment, I think I wrote it in a poor way. Your comment of "strict inequality" captured my intent; I was not familiar with that phrasing which is much more succinct than what i original wrote.
(Edited: 2017-09-18)
Concerning the different formulation, the Wikipedia article used a more general form where @BT@a=k \cdot E[x]@BT@. Hence, their version of the Markov Inequality was: . @BT@Pr[x \geq a] \leq \frac{E[x]}{a}@BT@ . Concerning the "equality" comment, I think I wrote it in a poor way. Your comment of "strict inequality" captured my intent; I was not familiar with that phrasing which is much more succinct than what i original wrote.
X