peace on you all. I have this problem now i don't know how he reached to the final from i'm not good at math in some things so i couldn't understand the proof. this is the problem. Know about the expected value i will write down some notes i concluded from my previous blog.
1- the problem want's the expected minimum value in a k-element subset of [1, 2, ..., n].
2- i see that i have 3 element at each subset and my array [1, 2, ..., n] has n element in it does it mean i have 1/3 chances to get minimum element at array of size n so n * (1/k). Now that what i could reach to compare it to the final from of the prof of this problem But the final form is equal to (N+1)/(K+1) of this function F(N, K).
any explanation but with some easy prof. cause i didn't understand by math(words).
thanks for your time.
Expected value of the minimum $$$m$$$ can be expressed as $$$P(m \ge 1) + P(m \ge 2) + \cdots + P(m \ge n)$$$. An explanation for this can be found here.
What is $$$P(m \ge i)$$$? It's the probability that all $$$k$$$ chosen elements fall among the largest $$$n + 1 - i$$$ elements (out of the possible $$$n$$$). So the expression works out as follows
Add the (k+1)th person (we'll call him X) and also add a new number 0 at the beginning. After all K+1 people select the numbers, let Y be the probability variable defined by
i) Y = i/(N+1) if X choose the smallest number out of all K+1 people, where i is the order statistic of X. ii) 0 if X did not choose the smallest number out of all K+1 people.
Note that the expected value of Y is preciesly the probability which X choose the smallest number, which is 1/(K+1) since there are K+1 people.
Now think of the probability distribution of (N+1)Y. The expected value of this is precisely F(N, K). i.e.
F(N, K) = EXP((N+1)Y) = (N+1) EXP(Y) = (N+1)/(K+1).