Accueil

Application de la loi de Benford aux suites récurrentes


  Examinez attentivement votre dernier ticket de caisse, s'il est suffisamment long, disons une trentaine d'articles, vous constaterez qu'environ la moitié des prix commencent par un " 1 " ou un " 2 ". Encore plus surprenant, ceci reste vrai indépendamment de l'unité monétaire choisie, francs ou euros ! 
  Incroyable mais vrais et mathématiquement démontrable.


  La loi de Benford ou loi du premier digit défini la probabilité qu'un chiffre particulier soit le premier chiffre d'un nombre pris au hasard dans un ensemble de données.

  En base  b  la probabilité  P(d)  qu'un nombre commence par le digit  d  est donnée par :

   Si, parmi les premiers chiffres d'un ensemble de nombres certains sont plus probables, la distribution des probabilités doit être indépendante du système d'unités . Pour cela la probabilité de trouver un nombre x dans un ensemble de nombres est forcément inversement proportionnel à x :

la quantité de nombres compris entre a et b sera :

   Ainsi, en base 10, la probabilité relative pour que le premier chiffre d'un nombre compris entre 1 et 10 soit le digit d sera donnée par : 

  La probabilité qu'un nombre commence par un " 1 " sera donc log2 ( 30,1% ) et seulement log1,11 ( 4,6 % ) qu'il commence par un " 9 " .L'histogramme ci-contre représente les fréquences relatives des 9 chiffres comme chiffre initial : on y trouve 6 fois plus de " 1 " que de " 9 ".

  La répartition est identique dans la gamme 10 à 100 ou 100 à 1000 …

   La loi de Benford s'applique aux prix, parce que le nombre des articles bon marché l'emporte largement sur le nombre des articles onéreux, vous vérifierez sur votre prochain ticket de caisse qu'environ un tiers des prix commencent par 1.

  Il en est de même pour les populations des agglomérations ( les villages sont plus nombreux que les mégapoles), les constantes physiques, … , mais comment se comportent les suites récurrentes ?

  Considérons un ensemble de nombres, dont N sont compris entre x1 et x2, on peut définir une densité moyenne sur cet intervalle 

  Evaluons la densité moyenne au voisinage du terme Un de la suite de Fibonacci :

     Un = Un-1 +U n-2     avec       U0=1 et U1= 1

 en prenant x1 entre U n-1 et Un et x2 entre Un et Un+1 

puisque Un+1 = Un + Un-1 .

  Cette distribution de probabilité correspond au critère de la loi de Benford: la densité est inversement proportionnelle au nombre considéré. Effectivement les nombres de Fibonacci suivent parfaitement cette loi : sur les 500 premiers termes on relève:

d % théorique % observé
1 30.10 30.13
2 17.60 17.56
3 12.49 12.57
4 9.691 9.381
5 7.918 7.984
6 6.694 6.586
7 5.799 5.788
8 5.115 5.389
9 4.575 4.391

  Le même accord s'observe pour la plupart des suites récurrentes du second ordre : 

un= a un-1+ b un-2    avec a, b, u0 et u1 entiers

sauf :

  • quelques cas particuliers qui bien évidement transgressent la loi de Benford :
    • un ={ 0, 1, 2, 3, 4, 5, 6, ... } c'est à dire un= 2 un-1- b un-2    avec   u0=0    et   u1=1

    • un ={ 1, 3, 2, -1, -3, -2, 1, ... } c'est à dire un= un-1- un-2    avec   u0=1    et   u1=3

  • des écarts apparents, sur des séquences limitées de termes de certaines suites, exprimées dans une base de numération particulière.

  Ainsi, en base 4, les premiers termes de la suite de Fibonacci présentent une alternance régulière du premier chiffre :

U = {1, 1, 2, 3, 11, 20, 31, 111, 202, 313, 1121, 2100, 3221, 11321, 21202, 33123, …}

si bien que dans cette base les termes U2à U16 donnent :

d

% théorique

% observé
1 50 33.33
2 29.25 33.33
5 20.75 33.33

  Plus surprenant avec la suite :

un = 4un-1 + 3un-2
u0 = 2 et u1 = 11
un = {2, 11, 50, 233, 1082, 5027, 23354, 108497, 504050, 2341691,10878914, … }

  Une statistique portant sur les 200 premiers termes donne :

d % théorique % observé
1 30.10 33.33
2 17.60 33.33
5 7.918 33.33

  Là encore 3 chiffres se répartissent équitablement la première place sur un lot de 200 termes successifs, le dernier valant 5.98711… E+133 !

  Deux méthodes pour expliquer ces apparents désaccords:

  • utiliser la formule de Binet pour la suite de Fibonacci (ou une forme plus générale pour les autres suites)

  • partir des règles de récurrences applicables aux partitions de suites récurrentes.

Formule de Binet

   Dès que n croit le second terme devient négligeable et

  Dans les trois suites constituées de termes prélevés de 3 en 3 chaque terme sera 4.236 ... fois supérieur au précédent, si bien qu'en base 4 on y observera des séquences d'environ 4 termes commençant par le même chiffre.

Formule de partition

  A une suite un

un = aun-1 + bun-2

avec

u0 et u1 donnés

on associe la suite Vn qui suit la même règle de récurrence

Vn = aVn-1 + bVn-2

V0 = 2 et V1 = a

  Ceci posé, prélevons des termes de la suite un de m en m , formant ainsi une nouvelle suite, par exemple {u2, u2+m, u2+2m, u2+3m, …} , la règle de récurrence de cette nouvelle suite sera alors :

wn = Vmwn-1 -(-b)mwn-2

  Pour la suite de Fibonacci où a=1 , b=1, u0 =0 et u1 = 1 ,on aura V0 = 2 , V1 = 1 et la suite V sera la suite des nombres de Lucas V={ 2, 1, 3, 4, 7, 11, … }, les 3 suites formées avec les prélèvements de 3 en 3 dans la suite de Fibonacci suivront donc la règle de récurrence :

wn = 4 wn-1 +wn-2

wn-2 étant petit devant 4 wn-1, wn sera peu supérieur à 4 fois wn-1 ce qui explique qu'ils aient souvent le même premier digit en base 4 .

  Pourquoi la seconde pseudo exception est-elle plus spectaculaire ?

  Avec a=4 , b = 3 , u0 = 2 et u1= 11 on a:

V= { 2, 4, 20, 100, …}

et

 -(- b)m = 27

les prélèvements de 3 en trois conduisent donc à des suites obéissant à la relation de récurrence :

wn = 100 wn-1 + 27 wn-2

  Ici la périodicité des 3 digits s'observe sur des séquences de plus de 200 termes :

n w' w" w"'
0 2 - -
1 - 11 -
2 - - 50
3 233 - -
4 - 1082 -
5 - - 5027
6 23354 - -
7 - 108497 -
8 - - 504050
9 2341691 - -
10 - 10878914 -
11 - - 5040729
... ... ... ...
198 2.773 E+132 - -
199 - 1.288 E+133 -
200 - - 5.987 E+133
... ... ... ...
203 - - 6.003E+135
... ... ... ...

mais avec une statistique portant sur un nombre de termes beaucoup plus grand, on vérifierait que la loi de Benford est parfaitement respectée.


  Sites traitant de la loi de Benford

Historique et justification
Eric Weisstein's World of Mathematics http://mathworld.wolfram.com/BenfordsLaw.html
 
Applications aux nombres de Fibonacci
R.Knott http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibmaths.html

Extraire la page pour l'enregistrer ou l'imprimer

robert.mellet