I found the below equation when studying probabilities:

(Here $$$n,k$$$ are positive integers and $$$n\ge k$$$)

but failed to prove it.

Can anyone offer precious help to me. Thanks

# | User | Rating |
---|---|---|

1 | tourist | 3979 |

2 | Benq | 3623 |

3 | MiracleFaFa | 3604 |

4 | Radewoosh | 3545 |

5 | maroonrk | 3534 |

6 | slime | 3511 |

7 | greenheadstrange | 3430 |

8 | ecnerwala | 3342 |

9 | sunset | 3338 |

10 | xtqqwq | 3331 |

# | User | Contrib. |
---|---|---|

1 | YouKn0wWho | 210 |

2 | Monogon | 200 |

3 | Um_nik | 193 |

4 | awoo | 191 |

5 | -is-this-fft- | 184 |

6 | sus | 177 |

7 | Errichto | 175 |

8 | antontrygubO_o | 173 |

9 | maroonrk | 167 |

9 | SecondThread | 167 |

I found the below equation when studying probabilities:

(Here $$$n,k$$$ are positive integers and $$$n\ge k$$$)

but failed to prove it.

Can anyone offer precious help to me. Thanks

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/23/2022 08:53:48 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I'm so sorry that I check the Left Hand Side and find it is wrong.

It's maybe a correct equation now as I've fixed it.

Consider the sum (without the $$$ n {n-1 \choose k-1} $$$):

This looks somewhat like the expansion of $$$(1-x)^{n-k}$$$, without the $$$x^i$$$ term and with the extra $$$\frac{1}{k+i+1}$$$ term. Let's write it:

Now, we need to get $$$ k+i+1 $$$ in the denominator somehow. To do this, we will first multiply both sides with $$$x^k$$$:

Finally, to get the original sum $$$ S $$$, we integrate both sides from $$$0$$$ to $$$1$$$:

The RHS is $$$ \mathrm{B}(k+1, n-k+1) $$$ (Beta function), so

Thus, LHS = $$$ n {n-1 \choose k-1} S = \frac{n(n-1)!k!(n-k)!}{(n-k)!(k-1)!(n+1)!} = \frac{k}{n+1} $$$

Thank you very much but I found the equation when doing your process from the bottom to the top.

But I want to know whether other direct way exists or not……

I think I have a somewhat indirect probabilistic proof in terms of random variables (I remember seeing this technique quite some time back).

Suppose we have $$$n - k$$$ independent exponentially distributed random variables $$$X_i$$$ with $$$\lambda = 1$$$. We will compute the value of the MGF of $$$X$$$ at $$$-k-1$$$, and for computing this in another way, we will need an independent exponentially distributed random variable $$$Y$$$ with $$$\lambda = k + 1$$$, since it's a standard result that for exponentially distributed random variable $$$Y = Exp(\lambda)$$$, $$$P[X \le Y] = E[\exp(-\lambda X)] = \text{mgf}_X(-\lambda)$$$.

Let $$$X = \max X_i$$$ be the random variable that computes the maximum of the $$$n - k$$$ random variables, and let $$$X'_i$$$ be the random variable that computes the maximum of the first $$$i$$$ random variables among the $$$X_j$$$s. Firstly we try to find an expression for the CDF of $$$X$$$ (the usual trick with the products of CDFs won't work for this part, but we'll use it later on).

Let $$$M = \min X_i$$$ the the random variable that computes the minimum of the $$$n - k$$$ random variables.

For that, note that $$$P[X \ge x] = \int_0^t p_{M}(s) P[X \ge x \mid M = s] ds$$$ $$$= \int_0^t p_M(s) P[\text{max of everything else} \ge x \mid M = s] ds = \int_0^t p_M(s) P[\text{max of everything else} \ge x - s] ds$$$. The last probability comes from the fact that exponential random variables are memoryless. Since the second expression is just the expression to compute the sum of random variables identical in distribution to $$$M$$$ and $$$X_{n - k - 1}'$$$, by doing this $$$n - k - 1$$$ more times, we get the fact that if $$$M_i$$$ is the min of $$$i$$$ exponential random variables, then $$$X$$$ is identically distributed to $$$M_1 + \ldots + M_{n - k}$$$.

Note that the CDF of the min of $$$r$$$ iid exponential random variables with $$$\lambda = l$$$ is the same as that of a single exponentially distributed random variable with $$$\lambda = rl$$$, so the distribution of $$$X$$$ is $$$\sum_{i = 1}^{n - k} Exp(\lambda = i)$$$ where all random variables in the sum are identical.

Using this and the fact that for independent random variables, the MGF of their sum is the product of the individual MGFs, we get $$$P[X \le Y] = \prod_{i = 1}^{n - k}\frac{i}{k + i + 1} = \frac{1}{\binom{n+1}{k+1}}$$$.

Now let's fix $$$Y = y$$$. Then since the CDF of max of independent random variables is the product of their CDFs, we have $$$P[X \le y] = (1 - \exp(-y))^{n - k}$$$. Using the binomial theorem and varying $$$y$$$, we have $$$P[X \le Y] = \int_0^\infty p(y) P[X \le y] dy = \sum_{i = 0}^{n - k} \binom{n - k}{i} (-1)^i \int_0^\infty (k + 1) \exp(-(k + 1)y) \cdot \exp(-iy) dy$$$ $$$= \sum_{i = 0}^{n - k} \binom{n - k}{i} (-1)^i \frac{k+1}{k+i+1}$$$.

So finally, we get LHS = $$$n \cdot \binom{n - 1}{k - 1} \cdot \sum_{i = 0}^{n - k} \binom{n - k}{i} (-1)^i \frac{1}{k + i + 1} = n \cdot \binom{n - 1}{k - 1} \cdot \frac{P[X \le Y]}{k + 1}$$$ $$$ = k \cdot \binom{n}{k} \cdot \frac{1}{\binom{n+1}{k+1}} \cdot \frac{1}{k+1} = \frac{k}{n + 1}$$$.