Considerați un grafic obișnuit (pentru fiecare vârf al aceluiași grad) un grafic conectat. Vom fi interesati de comportamentul plimbarilor aleatoare (o plimbare aleatorie este un proces atat de simplu: ajunge intr-un anumit vertex, iar apoi de mai multe ori alegem o margine aleatoare si mergem de-a lungul acesteia). Să fie distribuția de probabilitate pe vârfuri. Cum arată distribuția de probabilități după un pas dintr-o plimbare aleatorie? Este foarte simplu: va fi un vector, în cazul în care matricea de contiguitate este împărțită.
Din moment ce este regulat, distribuția staționară a unei plimbări aleatorii va fi uniformă. Pentru vectorii corespunzători, toate componentele vor fi egale - o vom desemna.
Vom fi interesați de rata de convergență a distribuției de la vârfuri la cea uniformă. De exemplu, să evaluăm. Pentru a face acest lucru, ia în considerare următoarea caracteristică importantă:
Se pare că, cu cât este mai mică, cu atât distribuția este mai rapidă, spre deosebire de distribuția uniformă. Dar mai întâi, să stabilim relația dintre numerele noastre.
Deoarece este simetrică, are o bază ortonormală a vectorilor proprii. Noi o denotăm și valorile proprii corespunzătoare. Vom presupune asta.
matrice stocastică (toate elementele non-negativ, suma fiecărui rând și fiecare coloană - unitate), în timp ce matrici stocastice, nu este greu de înțeles valorile proprii nu depășesc. Vom spune că y are un punct fix - un vector. Astfel, putem presupune că și.
Se pare că. Într-adevăr, subspațiul vectorilor care sunt ortogonali la intervalul liniar. A se întinde vectorii din acest subspațiu la maximum.
Acum, să luăm în considerare rata de convergență a distribuției la uniformă (). Deoarece - distribuția de probabilități este posibil să o reprezentăm sub forma, unde. Acum să facem o evaluare simplă:
Ultima tranziție este corectă, deoarece subspațiul vectorilor ortogonali este invariabil pentru. Rămâne de reținut că, de atunci, și, prin urmare.
Astfel, obținem următoarea estimare:
.
Deci, dacă vrem să demonstreze că mers aleator este rapid converge la distribuirea uniformă, este necesar să se demonstreze că este suficient de mică.
Se pare că această afirmație este adevărată: Dacă un grafic conectat la fiecare nod există o buclă, atunci (vom dovedi acest fapt în următorul post). Prin urmare, este ușor să se obțină că mers aleator de lungime, cu o probabilitate mare de a vizita toate nodurile.