View Single Post
Old 10-28-2016, 01:52 AM
CountVonCount CountVonCount is offline
Join Date: Oct 2016
Posts: 17
Default Re: Discussion of the VC proof

Originally Posted by CountVonCount View Post
I don't understand why the RHS is greater or equal to the LHS. The only legitimation I see for this is, that the distribution of P[S] is uniform, but this has not been stated in the text.
Or do I oversee here anything and this is also valid for all kinds of distribution?
I got it by myself.
When we have a uniform distribution of P[S] the outcome of the product-sum

\sum_S P[S] \times P[A|S]

is simply the average of all P[A|S], since

\sum_S P[S] = 1

And an average is of course less than or equal to the maximum of P[A|S].
If P[S] is not distributed uniformly we still have an average, but a weighted average. But also here the result is always less than or equal to the maximum. Because you cannot find weighting factors that are in sum 1 but will lead to a higher result as the maximum P[A|S].
Reply With Quote