Longueur des hashes

Bonjour,
je galère de bon matin sur un problème qui ne me semblait pas si compliqué.
Soit $\mathcal{A}$ un alphabet fini de cardinal $a$. Soit $n \in \mathbb{N}^*$, $(L_{i,j})_{i \in \mathbb{N},j<n}$ des variables aléatoires indépendantes uniformes sur $\mathcal{A}$.
Je cherche la loi du plus petit entier $k$ tel que pour tout $j_1, j_2 < n$, si $j_1 \neq j_2$, alors $L_{0,j_1}\cdots L_{k-1,j_1}$ et $L_{0,j_2}\cdots L_{k-1,j_2}$ sont des chaînes de caractères différentes. En fait, je cherche plutôt des bornes sur la queue de cette loi, i.e. pour tout $\alpha$, savoir estimer un $M$ à partir duquel $\mathbb{P}[k > M] < \alpha$ et, si vous voulez tout savoir, trouver un $M$ tel que pour $n = 1000000$, $a = 16$, on ait $\mathbb{P}[k > M] < 10^{-5}$.
Bien sûr, la probabilité de l'événement "pour tout $j_1, j_2 < n$, si $j_1 \neq j_2$, alors $L_{0,j_1}\cdots L_{k-1,j_1}$ et $L_{0,j_2}\cdots L_{k-1,j_2}$ sont des chaînes de caractères différentes" est $\frac{a^k!}{(a^k - n)!a^{kn}}$ mais je ne sais pas trop quoi en faire.

EDIT : Ajout d'un truc manquant.

Réponses

  • Calli
    Modifié (March 2023)
    Salut,
    On a \[\mathbb{P}(k\leqslant M)= \frac{a^{M} !}{(a^{M} -n) !a^{Mn} } = \frac{a^{M} (a^M-1 )\cdots (a^{M} -n+1)}{a^{Mn}} = \prod_{i=1}^{n-1} \left(1- \frac{i}{a^{M}} \right)\] donc, $n$ étant fixé, \[\mathbb{P}(k>M)= 1-\exp \!\left( \sum_{i=1}^{n-1} \ln \!\left(1- \frac{i}{a^{M}} \right)\right) \underset{M\rightarrow \infty }{\sim}  - \sum_{i=1}^{n-1} \ln \!\left(1- \frac{i}{a^{M}} \right) \sim\sum_{i=1}^{n-1} \frac{i}{a^{M}} = \frac{n(n-1)}{2a^{M}}\] Donc $$\mathbb{P}(k>M) \approx \alpha\ \overset{\sim}\Leftrightarrow\ M \approx \log_a\left(\frac{n(n-1)}{2\alpha}\right)\approx 13{,}9$$ en gros. Pour être plus précis, pour tout $x\in {]0,1[}$, on a par concavité : $\forall y\in [0,x],\; \ln (1-y)\geqslant -c_{x} y$ avec $c_{x} := \frac{\lvert\ln (1-x)\vert}x$ (et $c_{x} \approx 1$ quand $x\approx 0$). Donc si $\frac{n-1}{a^M} \leqslant x$, on a : \[\mathbb{P}(k>M) =1-\exp \!\left( \sum_{i=1}^{n-1} \ln \!\left(1- \frac{i}{a^{M}} \right)\right)\leqslant - \sum_{i=1}^{n-1} \ln \!\left(1- \frac{i}{a^{M}} \right)\leqslant  \sum_{i=1}^{n-1} \frac{c_{x} i}{a^{M}} = \frac{c_{x} n(n-1)}{2a^{M}} .\] Donc il suffit de trouver $x$ et $M$ tels que $\frac{n-1}{a^M} \leqslant x$ et $ \frac{\lvert\ln (1-x)\vert}x\, \frac{ n(n-1)}{2a^{M}} \leqslant \alpha $. Et si on cherche le cas d'égalité pour optimiser, il suffit de prendre le $x\in{]0,1[}$ tel que $\frac{\lvert\ln(1-x)\rvert n}{2} =\alpha$ puis de poser $M=\log_a \big(\frac{n-1}x\big)$. Bref, $$M := \log_a(n-1)-\log_a \left( 1-\exp\left(-\frac\alpha{2n}\right)\right) \approx 14{,}4.$$ convient, si pas d'erreur.
  • Je vais regarder !
  • Georges Abitbol
    Modifié (March 2023)
    Je viens de noter un typo : dans ta deuxième égalité, le $-1$ ne doit pas être dans l'exposant ! Je lis, je lis.

    Bon, ok, ça me va ! Merci beaucoup, Calli !
Connectez-vous ou Inscrivez-vous pour répondre.