TD8 : Probabilité d’être un multiple de a, Problème du secrétaire

EX 1

1.

\[P(X=k) = \binom{k-1}{n-1} p^{n-1} q^{k-(n-1)}×p\]

2.

La somme des probas vaut 1.

EX 2

1.

Sinon, la proba serait diffuse (elle ne chargerait pas les singletons), et la somme $\sum_{n∈ℕ} p(n)$ vaudrait 0.

2.

a.

1. \[P(ℕ) = \sum_{n∈ℕ} \frac{1}{2^{n+1}} = 1\]
2. $P$ est bien $𝜎$-additive, avec le théorème de sommation par paquets.

b.

1. \[P(2ℕ) = \sum_{n∈ℕ} \frac{1}{2^{2n+1}} \\ = \frac 1 2 \sum_{n∈ℕ} \frac{1}{4^n} \\ = \frac 2 3\]
2. \[P(2ℕ+1) = 1 - \frac 2 3 \\ = \frac 1 3\]

C’est assez contre-intuitif.

3.

a.

\[P(aℕ)P(bℕ) = \frac{1}{ab} = P(abℕ) = P(aℕ ∩ bℕ)\]

car $abℕ = aℕ ∩ bℕ$, puisque $a∧b =1$.

b.

i)

Démonstration d’Euclide : si on note $N$ le produit des nombres premiers, $N+1$ est premier et divise 1 : absurde.

ii).

A)

On note $H_N$ la somme partielle de rang $N$ de la série harmonique.

\[H_N - \ln N ≥ 0\]

car $f : x \mapsto \frac 1 x$ décroît sur $[1, +∞]$.

Donc pour tout $k∈[1, N]$

\[\frac 1 k ≥ \int_k^{k+1} \frac{dx}{x} ≥ \frac{1}{k+1}\]

Donc en sommant pour $k=1$ à $N-1$, il vient :

\[H_{N-1} ≥ \ln(N)\]

et comme $(H_n)_n$ croît strictement, le résultat est acquis.

B)

La décomposition facteur premier (DFP) de tout $i∈⟦1, N⟧$ est de la forme :

\[\prod_i p^{v_p(i)}\]

Donc

\[H_N ≤ \prod_{p∈P_N}(\sum_i \frac{1}{p^i})\]

C)

\[\prod_{p∈P_N}(\sum_i \frac{1}{p^i}) = \prod_{p∈P_N}(1 + \frac 1 p + \frac{1}{p(p-1)}) \\ ≤ \prod_{p∈P_N}(\exp(\frac 1 p + \frac{1}{p(p-1)})) \\ ≤ \exp(\sum_{P_N} \frac 1 p + \frac{1}{p(p-1)}) \\ ≤ \exp(\sum_{P_N} \frac 1 p + \frac{1}{p-1} - \frac 1 p) \\ ≤ \exp(\sum_{P_N} \frac{1}{p-1}) \\ ≤ \exp(\sum_{P_N} \frac 1 p + 1)\]

car

\[\sum_{P_N} (\frac{1}{p-1} - \frac 1 p) = \sum_{P_N} \frac{1}{p(p-1)} \\ ≤ \sum_{i=1}^N \frac{1}{i(i-1)} \\ ≤ \sum_{i=2}^N \frac{1}{i-1} - \frac 1 i \\ ≤ 1 - \frac 1 N ≤ 1\]

iv)

Donc

\[H_N ≤ \exp(\sum_{P_N} \frac 1 p + 1)\]

Donc en prenant le log : le résultat est acquis.

v)

\[\ln \prod_{P_N}(1 - \frac 1 p) = \sum_{P_N} \ln(1-\frac 1 p) \\ = - \sum_{P_N} \frac 1 p + O(1/p^2)\]

qui diverge en $-∞$ quand $N⟶+∞$.

c).

EX 3

1.

$P(A_k) =$

• $0$ si $k≤j$

• Si $k≥j$ :

  \[A_k = \lbrace \text{ le $k$-ième cadeau est le premier présenté d'une valeur supérieure au $1$er, au $2$ème, ⋯, au $j$-ième}\rbrace \\ = \lbrace \text{ les cadeaux $j, j+1, ⋯, k$ sont d'une valeur inférieure au $1$er OU au $2$ème OU ⋯ OU au $j$-ième}\rbrace \\ ∩ \lbrace \text{ le $k$-ième cadeau est d'une valeur supérieure au $1$-er, au $1$er, au $2$ème, ⋯, au $j$-ième}\rbrace\]

EX 4

1.

\[p_r = 2×\binom{2n-r}{n}(\frac 1 2)^{n-r}(\frac 1 2)^{n}×\frac 1 2\]

2.

\[q_r = 2×\binom{2n-r-1}{n-1}(\frac 1 2)^{n-r}(\frac 1 2)^{n-1}×\frac 1 2\]

3.

\[q = 2×\binom{2n}{n}(\frac 1 2)^{n}(\frac 1 2)^{n}×\frac 1 2\]

NB :

\[q = \sum_r q_r \times (\frac{1}{2})^{r+1}\]

EX 5

1.

Lemme des coalitions.

2.

$$P(X_1 = 0) = 1, P(X_1 = k) = 0$ pour $k>0$

3.