MACM's blog

mathematical expectation of the minimal element
By MACM, history, 5 years ago, In English

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.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

  • 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

$$$\frac{1}{\binom{n}{k}}\sum_{i = 1}^{n} \binom{n + 1 - i}{k}$$$
  • The summation evaluates to $$$\binom{n + 1}{k + 1}$$$ (by the well-known hockey stick identity). So the expected value is given by
$$$\frac{\binom{n+1}{k+1}}{\binom{n}{k}} = \frac{n+1}{k+1}$$$
→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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).

→ Reply