Test des suites croissantes

Ce test, proposé par Knuth, s'appelle aussi le «run up test».

Méthode

1. Compter le nombre de sous-séquences croissantes de chaque longueur dans une séquence aléatoire de n nombres:

   	ri = nombre de sous-séquences croissantes de longueur i	si i = 1, 2, 3, 4, 5
   	ri = nombre de sous-séquences croissantes de longueur > 5	si i = 6

   Exemple

   Séquence:	855	108	226	32	132	56	545	642	103	108	201	809	901	151
   	1	2		2		3			5					1

   Ce qui donne: r₁ = 2, r₂ = 2, r₃ = 1, r₄ = 0, r₅ = 1, r₆ = 0

2. Calculer avec les coefficients a_ij et b_i ci-dessous:

   a j i 4529.4 9044.9 13568 18091 22615 27892 9044.9 18097 27139 36187 45234 55789 13568 27139 40721 54281 67852 83685 18091 36187 54281 72414 90470 111580 22615 45234 67852 90470 113262 139476 27892 55789 83685 111580 139476 172860

   b 1/6 5/24 11/120 19/720 29/5040 1/840

3. Pour une valeur de n élevée (disons plus de 4000 nombres) R suit une distribution du c² avec 6 degrés de liberté (et non pas 5). Si le seuil de tolérance est de 5%, la suite aléatoire passera donc le test si R<12.59 (voir tableau).

Exercice

Programmez en Mathematica le test des suites croissantes. Testez avec le test des suites croissantes les générateurs que vous avez déjà programmés. Fonctions Mathematica utiles: For, If, Print.

Référence

• Donald E. Knuth, The art of Computer Programming, Vol. 2 (Seminumerical Algorithms), Addison-Wesley, pp. 66-69

Didier Müller, 7.1.03