Content deleted Content added
→The secretary problem: rm pirate copy of same reference |
MalnadachBot (talk | contribs) m Fixed Lint errors - replaced obsolete center tags. (Task 12) |
||
Line 44:
Let ''B(k)'' (resp. ''H(k)'') be the event "there is right-to-left minimum (resp. maximum) at rank ''k''", i.e. ''B(k)'' is the set of the permutations <math>\scriptstyle\ \mathfrak{S}_n</math> which exhibit a right-to-left minimum (resp. maximum) at rank ''k''. We clearly have
<div class="center"><math>\{\omega\in B(k)\}\Leftrightarrow\{L(k,\omega)=0\}\quad\text{and}\quad\{\omega\in H(k)\}\Leftrightarrow\{L(k,\omega)=k-1\}.</math></
Thus the number ''N<sub>b</sub>(ω)'' (resp. ''N<sub>h</sub>(ω)'') of right-to-left minimum (resp. maximum) for the permutation ''ω'' can be written as a sum of independent [[Bernoulli random variable]]s each with a respective parameter of 1/k :
<div class="center"><math>N_b(\omega)=\sum_{1\le k\le n}\ 1\!\!1_{B(k)}\quad\text{and}\quad N_b(\omega)=\sum_{1\le k\le n}\ 1\!\!1_{H(k)}.</math></
Indeed, as ''L(k)'' follows the uniform law on <math>\scriptstyle\ [\![1,k]\!],</math>
<div class="center"><math>\mathbb{P}(B(k))=\mathbb{P}(L(k)=0)=\mathbb{P}(H(k))=\mathbb{P}(L(k)=k-1)=\tfrac1k.</math></
The [[generating function]] for the Bernoulli random variable <math>1\!\!1_{B(k)}</math> is
<div class="center"><math>G_k(s)=\frac{k-1+s}k,</math></
therefore the generating function of ''N<sub>b</sub>'' is
<div class="center"><math>G(s)=\prod_{k=1}^nG_k(s)\ =\ \frac{s^{\overline{n}}}{n!}</math></
(using the [[Falling and rising factorials|rising factorial]] notation),
which allows us to recover the product formula for the generating function of the
| |||