În mecanica statistică, modelul subcubului aleatoriu (random-subcube model, RSM) este un model exact rezolvabil care reproduce proprietăți esențiale ale problemelor dificile de tip (CSP) și ale , precum organizarea geometrică a soluțiilor, efectele variabilelor înghețate și limitele unor algoritmi, cum ar fi schemele de decimare.
Modelul RSM constă dintr-un set de N , unde soluțiile sunt definite ca puncte într-un hipercub. Modelul introduce clustere (grupuri), care sunt subcuburi aleatorie ale hipercubului și reprezintă grupuri de soluții ce împărtășesc anumite caracteristici comune. Pe măsură ce densitatea constrângerilor crește, spațiul soluțiilor trece printr-o serie de transformări de fază similare celor observate în CSP-uri precum satisfiabilitatea aleatorie k (k-SAT) și colorarea aleatorie k (k-COL). Aceste transformări includ apariția clusterelor, condensarea și, în final, faza nesatisfiabilă în care nu mai există soluții.
Modelul RSM devine echivalent cu aceste CSP-uri reale în limita în care dimensiunea constrângerilor devine mare. În particular, el reproduce distribuția dimensiunilor clusterelor și proprietățile de înghețare ale k-SAT și k-COL în limita k mare. Aceasta este analogă situației în care modelul energiei aleatorii reprezintă limita p mare a modelului p-spin de sticlă de spin.
Configurație
Subcuburi
Există particule. Fiecare particulă poate fi în una dintre două stări, sau .
Spațiul stărilor conține stări. Nu toate sunt accesibile; sunt permise doar acelea care satisfac constrângerile.
Fiecare constrângere este un subansamblu al spațiului stărilor. Fiecare este un „subcub”, definit prin
unde fiecare poate fi una dintre mulțimile , sau .
Stările permise sunt reuniunea acestor submulțimi:
Modelul subcubului aleatoriu
Fiecare model subcub aleatoriu este definit de doi parametri .
Pentru a genera un subcub aleatoriu , componentele sale sunt eșantionate independent și identic distribuit (IID) conform
Apoi se generează astfel de subcuburi aleatorie și se ia reuniunea lor.
Entropii
Densitatea entropiei clusterului al -lea, exprimată în biți, este
Densitatea entropiei sistemului este
Structura fazelor
Dimensiunea și numărul clusterelor
Fie numărul de clustere cu densitatea entropiei . Această variabilă are distribuție binomială, astfel că
unde
Prin , dacă , atunci se concentrează în jurul valorii medii. În caz contrar, deoarece , converge către 0 conform .
Prin urmare,
aproape sigur când .
Dacă exact, cele două efecte se echilibrează, iar converge în distribuție către o .
Faza lichidă
Pentru fiecare stare, numărul clusterelor care o conțin are distribuție binomială cu valoare așteptată
Dacă , atunci această valoare este exponențial mare, ceea ce înseamnă că fiecare stare aparține unui număr exponențial de clustere.
În acest caz probabilitatea ca toate stările să fie permise este
Astfel, aproape sigur toate stările sunt permise, iar densitatea entropiei este 1 bit pe particulă.
Faza cu clustere
Dacă , atunci numărul clusterelor care conțin o stare devine exponențial mic. Majoritatea stărilor nu aparțin niciunui cluster, iar cele care aparțin apar aproape întotdeauna într-un singur cluster.
Spațiul stărilor poate fi considerat aproximativ o a clusterelor.
Există aproape sigur
clustere de dimensiune . Spațiul stărilor este dominat de clustere cu densitatea entropiei optimă
În această fază, spațiul stărilor este împărțit aproape complet întreclustere, fiecare având dimensiunea
În mod aproximativ, spațiul stărilor apare ca un număr exponențial de clustere de dimensiuni comparabile.
Faza de condensare
O altă transformare de fază apare atunci când
adică
Pentru , densitatea optimă a entropiei devine inaccesibilă deoarece aproape sigur nu există clustere cu . În schimb, spațiul stărilor este dominat de clustere cu entropie apropiată de , soluția mai mare a ecuației
Pentru , contribuția clusterelor la spațiul total este
În limita , aproape întreg spațiul stărilor este acoperit de un număr finit de clustere. Dimensiunile clusterelor scad exponențial — aceasta este faza de condensare.
Faza nesatisfiabilă
Când , numărul clusterelor devine zero, astfel că nu mai există stări admise.
Note
Bibliografie
Vezi și Modelul energiei aleatorii
Categorie:Mecanică statistică