Bonjour,
je galère de bon matin sur un problème qui ne me semblait pas si compliqué.
Longueur des hashes
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
-
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 !
-
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.
Bonjour!
Catégories
- 165.6K Toutes les catégories
- 65 Collège/Lycée
- 22.2K Algèbre
- 37.7K Analyse
- 6.3K Arithmétique
- 61 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 26 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.8K Géométrie
- 86 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 29 Mathématiques et finance
- 344 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.4K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 805 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres