Random subcube model

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (June 2024) (Learn how and when to remove this message)

In statistical mechanics, the random-subcube model (RSM) is an exactly solvable model that reproduces key properties of hard constraint satisfaction problems (CSPs) and optimization problems, such as geometrical organization of solutions, the effects of frozen variables, and the limitations of various algorithms like decimation schemes.

The RSM consists of a set of N binary variables, where solutions are defined as points in a hypercube. The model introduces clusters, which are random subcubes of the hypercube, representing groups of solutions sharing specific characteristics. As the density of constraints increases, the solution space undergoes a series of phase transitions similar to those observed in CSPs like random k-satisfiability (k-SAT) and random k-coloring (k-COL). These transitions include clustering, condensation, and ultimately the unsatisfiable phase where no solutions exist.

The RSM is equivalent to these real CSPs in the limit of large constraint size. Notably, it reproduces the cluster size distribution and freezing properties of k-SAT and k-COL in the large-k limit. This is similar to how the random energy model is the large-p limit of the p-spin glass model.

There are N {\displaystyle N} particles. Each particle can be in one of two states − 1 , + 1 {\displaystyle -1,+1} .

The state space { − 1 , + 1 } N {\displaystyle \{-1,+1\}^{N}} has 2 N {\displaystyle 2^{N}} states. Not all are available. Only those satisfying the constraints are allowed.

Each constraint is a subset A i {\displaystyle A_{i}} of the state space. Each A i {\displaystyle A_{i}} is a "subcube", structured like A i = ∏ j ∈ 1 : N A i j {\displaystyle A_{i}=\prod _{j\in 1:N}A_{ij}} where each A i j {\displaystyle A_{ij}} can be one of { − 1 } , { + 1 } , { − 1 , + 1 } {\displaystyle \{-1\},\{+1\},\{-1,+1\}} .

The available states is the union of these subsets: S = ∪ i A i {\displaystyle S=\cup _{i}A_{i}}

Each random subcube model is defined by two parameters α , p ∈ ( 0 , 1 ) {\displaystyle \alpha ,p\in (0,1)} .

To generate a random subcube A i {\displaystyle A_{i}} , sample its components A i j {\displaystyle A_{ij}} IID according to P r ( A i j = { − 1 } ) = p / 2 P r ( A i j = { + 1 } ) = p / 2 P r ( A i j = { − 1 , + 1 } ) = 1 − p {\displaystyle {\begin{aligned}Pr(A_{ij}&=\{-1\})&=p/2\\Pr(A_{ij}&=\{+1\})&=p/2\\Pr(A_{ij}&=\{-1,+1\})&=1-p\end{aligned}}}

Now sample 2 ( 1 − α ) N {\displaystyle 2^{(1-\alpha )N}} random subcubes, and union them together.

The entropy density of the r {\displaystyle r} -th cluster in bits is s r := 1 N log 2 ⁡ | A r | {\displaystyle s_{r}:={\frac {1}{N}}\log _{2}|A_{r}|}

The entropy density of the system in bits is s := 1 N log 2 ⁡ | ∪ r A r | {\displaystyle s:={\frac {1}{N}}\log _{2}|\cup _{r}A_{r}|}

Let n ( s ) {\displaystyle n(s)} be the number of clusters with entropy density s {\displaystyle s} , then it is binomially distributed, thus E [ n ( s ) ] = 2 ( 1 − α ) N P → 2 N Σ ( s ) + o ( N ) V a r [ n ( s ) ] = 2 ( 1 − α ) N P ( 1 − P ) V a r [ n ( s ) ] E [ n ( s ) ] 2 → 2 − N Σ ( s ) {\displaystyle {\begin{aligned}E[n(s)]&=2^{(1-\alpha )N}P\to 2^{N\Sigma (s)+o(N)}\\Var[n(s)]&=2^{(1-\alpha )N}P(1-P)\\{\frac {Var[n(s)]}{E[n(s)]^{2}}}&\to 2^{-N\Sigma (s)}\end{aligned}}} where P := ( N s N ) p ( 1 − s ) N ( 1 − p ) s N , Σ ( s ) := 1 − α − D K L ( s ‖ 1 − p ) D K L ( s ‖ 1 − p ) := s log 2 ⁡ s 1 − p + ( 1 − s ) log 2 ⁡ 1 − s p {\displaystyle {\begin{aligned}P&:={\binom {N}{sN}}p^{(1-s)N}(1-p)^{sN},\\\Sigma (s)&:=1-\alpha -D_{KL}(s\|1-p)\\D_{KL}(s\|1-p)&:=s\log _{2}{\frac {s}{1-p}}+(1-s)\log _{2}{\frac {1-s}{p}}\end{aligned}}}

By the Chebyshev inequality, if Σ > 0 {\displaystyle \Sigma >0} , then n ( s ) {\displaystyle n(s)} concentrates to its mean value. Otherwise, since E [ n ( s ) ] → 0 {\displaystyle E[n(s)]\to 0} , n ( s ) {\displaystyle n(s)} also concentrates to 0 {\displaystyle 0} by the Markov inequality.

Thus, n ( s ) → { 2 N Σ ( s ) + o ( N ) if  Σ ( s ) > 0 0 if  Σ ( s ) < 0 {\displaystyle n(s)\to {\begin{cases}2^{N\Sigma (s)+o(N)}\quad &{\text{if }}\Sigma (s)>0\\0\quad &{\text{if }}\Sigma (s)<0\end{cases}}} almost surely as N → ∞ {\displaystyle N\to \infty } .

When Σ = 0 {\displaystyle \Sigma =0} exactly, the two forces exactly balance each other out, and n ( s ) {\displaystyle n(s)} does not collapse, but instead converges in distribution to the Poisson distribution P o i s s o n ( 1 ) {\displaystyle Poisson(1)} by the law of small numbers.

For each state, the number of clusters it is in is also binomially distributed, with expectation 2 ( 1 − α ) N ( 1 − p / 2 ) N = 2 N ( log 2 ⁡ ( 2 − p ) − α ) {\displaystyle 2^{(1-\alpha )N}(1-p/2)^{N}=2^{N(\log _{2}(2-p)-\alpha )}}

So if α < log 2 ⁡ ( 2 − p ) {\displaystyle \alpha <\log _{2}(2-p)} , then it concentrates to 2 N ( log 2 ⁡ ( 2 − p ) − α ) {\displaystyle 2^{N(\log _{2}(2-p)-\alpha )}} , and so each state is in an exponential number of clusters.

Indeed, in that case, the probability that all states are allowed is [ 1 − [ 1 − ( 1 − p / 2 ) N ] 2 ( 1 − α ) N ] 2 N ∼ e − e − 2 N ( log 2 ⁡ ( 2 − p ) − α ) + N ln ⁡ 2 → 1 {\displaystyle [1-[1-(1-p/2)^{N}]^{2^{(1-\alpha )N}}]^{2^{N}}\sim e^{-e^{-2^{N(\log _{2}(2-p)-\alpha )}+N\ln 2}}\to 1}

Thus almost surely, all states are allowed, and the entropy density is 1 bit per particle.

If α > α d := log 2 ⁡ ( 2 − p ) {\displaystyle \alpha >\alpha _{d}:=\log _{2}(2-p)} , then it concentrates to zero exponentially, and so most states are not in any cluster. Those that do are exponentially unlikely to be in more than one. Thus, we find that almost all states are in zero clusters, and of those in at least one cluster, almost all are in just one cluster. The state space is thus roughly speaking the disjoint union of the clusters.

Almost surely, there are n ( s ) = 2 N Σ ( s ) {\displaystyle n(s)=2^{N\Sigma (s)}} clusters of size 2 N s {\displaystyle 2^{Ns}} , therefore, the state space is dominated by clusters with optimal entropy density s ∗ = arg ⁡ max s ( Σ ( s ) + s ) {\displaystyle s^{*}=\arg \max _{s}(\Sigma (s)+s)} .

Thus, in the clustered phase, the state space is almost entirely partitioned among 2 N Σ ( s ∗ ) {\displaystyle 2^{N\Sigma (s^{*})}} clusters of size 2 N s ∗ {\displaystyle 2^{Ns^{*}}} each. Roughly, the state space looks like exponentially many equally-sized clusters.

Another phase transition occurs when Σ ( s ∗ ) = 0 {\displaystyle \Sigma (s^{*})=0} , that is, α = α c := p ( 2 − p ) + log 2 ⁡ ( 2 − p ) {\displaystyle \alpha =\alpha _{c}:={\frac {p}{(2-p)}}+\log _{2}(2-p)} When α > α c {\displaystyle \alpha >\alpha _{c}} , the optimal entropy density becomes unreachable, as there almost surely exists zero clusters with entropy density s ∗ {\displaystyle s^{*}} . Instead, the state space is dominated by clusters with entropy close to s c {\displaystyle s_{c}} , the larger solution to Σ ( s c ) = 0 {\displaystyle \Sigma (s_{c})=0} .

Near s c {\displaystyle s_{c}} , the contribution of clusters with entropy density s = s c − δ {\displaystyle s=s_{c}-\delta } to the total state space is 2 N s ⏟ size of clusters × 2 N Σ ( s ) ⏟ number of clusters = 2 N ( s + Σ ( s ) ) = 2 N ( s c − δ − Σ ′ ( s c ) δ ) {\displaystyle \underbrace {2^{Ns}} _{\text{size of clusters}}\times \underbrace {2^{N\Sigma (s)}} _{\text{number of clusters}}=2^{N(s+\Sigma (s))}=2^{N(s_{c}-\delta -\Sigma '(s_{c})\delta )}} At large N {\displaystyle N} , the possible entropy densities are s c , s c − 1 / N , s c − 2 / N , … {\displaystyle s_{c},s_{c}-1/N,s_{c}-2/N,\dots } . The contribution of each is 2 N s c , 2 N s c 2 − ( 1 + Σ ′ ( s c ) ) , 2 N s c 2 − 2 ( 1 + Σ ′ ( s c ) ) , … {\displaystyle 2^{Ns_{c}},2^{Ns_{c}}2^{-(1+\Sigma '(s_{c}))},2^{Ns_{c}}2^{-2(1+\Sigma '(s_{c}))},\dots }

We can tabulate them as follows:

s {\displaystyle s}	s c {\displaystyle s_{c}}	s c − 1 / N {\displaystyle s_{c}-1/N}	s c − 2 / N {\displaystyle s_{c}-2/N}
#clusters	1 {\displaystyle 1}	2 Σ ′ ( s c ) {\displaystyle 2^{\Sigma '(s_{c})}}	2 2 Σ ′ ( s c ) {\displaystyle 2^{2\Sigma '(s_{c})}}
contributes	1 1 − 2 − ( 1 + Σ ′ ( s c ) ) {\displaystyle {\frac {1}{1-2^{-(1+\Sigma '(s_{c}))}}}}	2 − ( 1 + Σ ′ ( s c ) ) 1 − 2 − ( 1 + Σ ′ ( s c ) ) {\displaystyle {\frac {2^{-(1+\Sigma '(s_{c}))}}{1-2^{-(1+\Sigma '(s_{c}))}}}}	2 − 2 ( 1 + Σ ′ ( s c ) ) 1 − 2 − ( 1 + Σ ′ ( s c ) ) {\displaystyle {\frac {2^{-2(1+\Sigma '(s_{c}))}}{1-2^{-(1+\Sigma '(s_{c}))}}}}

Thus, we see that for any ϵ > 0 {\displaystyle \epsilon >0} , at N → ∞ {\displaystyle N\to \infty } limit, over 1 − ϵ {\displaystyle 1-\epsilon } of the total state space is covered by only a finite number of clusters. The state space looks partitioned into clusters with exponentially decaying sizes. This is the condensation phase.

When α > 1 {\displaystyle \alpha >1} , the number of clusters is zero, so there are no states.

This section needs expansion. You can help by adding missing information. (June 2024)

The RSM can be extended to include energy landscapes, allowing for the study of glassy behavior, temperature chaos, and the dynamic transition.

• Random energy model

• Mora, Thierry; Zdeborová, Lenka (2008-06-01). "Random Subcubes as a Toy Model for Constraint Satisfaction Problems". Journal of Statistical Physics. 131 (6): 1121–1138. arXiv:0710.3804. Bibcode:2008JSP...131.1121M. doi:10.1007/s10955-008-9543-x. ISSN 1572-9613.
• Zdeborová, Lenka (2008-06-25). "Statistical Physics of Hard Optimization Problems". Acta Physica Slovaca. 59 (3): 169–303. arXiv:0806.4112. Bibcode:2008PhDT.......107Z.
• Mézard, Marc; Montanari, Andrea (2009-01-22). Information, Physics, and Computation. Oxford University Press. ISBN 978-0-19-154719-5.