Jump to content

Random subcube model

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Cosmia Nebula (talk | contribs) at 19:03, 3 June 2024 (starting page). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

In statistical mechanics, the random-subcube model (RSM) is an exactly solvable model in statistical physics that captures key properties of hard constraint satisfaction problems (CSPs) and optimization problems. It provides a simplified framework for understanding how the solution space of these problems breaks down into clusters, ultimately leading to a loss of ergodicity and making them difficult to solve.

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, providing a valuable tool for studying their behavior in this regime. 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.

The RSM is a toy model for geometrical organization of solutions, the effects of frozen variables, and the limitations of various algorithms like decimation schemes. It can be further extended to include energy landscapes, allowing for the study of glassy behavior, temperature chaos, and the dynamic transition.

Setup

Subcubes

There are particles. Each particle can be in one of two states .

The state space has states. Not all are available. Only those satisfying the constraints are allowed.

Each constraint is a subset of the state space. Each is a "subcube", structured like where each can be one of .

The available states is the union of these subsets:

Random subcube model

Each random subcube model is defined by two parameters .

To generate a random subcube , sample its components IID according to

Now sample random subcubes, and union them together.

Entropies

The entropy density of the -th cluster in bits is

The entropy density of the system in bits is

Phase structure

Cluster sizes and numbers

Let be the number of clusters with entropy density , then it is binomially distributed, thus where

By the Chebyshev inequality, if , then concentrates to its mean value. Otherwise, since , also concentrates to .

Thus, almost surely as .

When exactly, the two forces exactly balance each other out, and does not collapse, but instead converges in distribution to the Poisson distribution by the law of small numbers.

Liquid phase

For each state, the number of clusters it is in is also binomially distributed, with expectation

So if , then it concentrates to , and so each state is in an exponential number of clusters.

Indeed, in that case, the probability that all states are allowed is

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

Clustered phase

If , 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 clusters of size , therefore, the state space is dominated by clusters with optimal entropy density .

Condensation phase

Another phase transition occurs when that is,

For , the state space is dominated by clusters with , satisfying . There are a subexponential number of such clusters.

Near , the contribution of clusters with entropy density to the total state space is At large , the possible entropy densities are . The contribution of each is

We can tabulate them as follows:

#clusters
contributes

Thus, we see that for any , at limit, only a finite number of clusters contribute over of the total state space. This is the condensation limit.

Unsatisfiable phase

When , the number of clusters is zero, so there are no states.

Applications

See also

References