Случайная модель субкуба

В статистической механике модель случайного субкуба (RSM) представляет собой точно решаемую модель, которая воспроизводит ключевые свойства задач удовлетворения жестких ограничений (CSP) и задач оптимизации, таких как геометрическая организация решений, эффекты замороженных переменных и ограничения различные алгоритмы, такие как схемы прореживания.

RSM состоит из набора N двоичных переменных , где решения определяются как точки в гиперкубе . Модель вводит кластеры, которые представляют собой случайные субкубы гиперкуба, представляющие группы решений, имеющих определенные характеристики. По мере увеличения плотности ограничений пространство решений претерпевает ряд фазовых переходов, подобных тем, которые наблюдаются в CSP, таких как случайная k-выполнимость ( k-SAT ) и случайная k-раскраска (k-COL). Эти переходы включают кластеризацию, конденсацию и, в конечном итоге, невыполнимую фазу, когда решений не существует.

RSM эквивалентен этим реальным CSP в пределе большого размера ограничения. Примечательно, что он воспроизводит распределение размеров кластеров и свойства замораживания k-SAT и k-COL в пределе больших k. Это похоже на то, как модель случайной энергии является пределом большого p модели p-спинового стекла .

Настраивать

Подкубы

Есть $N$ частицы. Каждая частица может находиться в одном из двух состояний $-1,+1$ .

Государственное пространство $\{-1,+1\}^{N}$ имеет $2^{N}$ государства. Не все доступны. Допускаются только те, которые удовлетворяют ограничениям.

Каждое ограничение является подмножеством $A_{i}$ государственного пространства. Каждый $A_{i}$ представляет собой «субкуб», структурированный как $A_{i}=\prod _{j\in 1:N}A_{ij}$ где каждый $A_{ij}$ может быть одним из $\{-1\},\{+1\},\{-1,+1\}$ .

Доступные состояния представляют собой объединение этих подмножеств: $S=\cup _{i}A_{i}$

Случайная модель субкуба

Каждая случайная модель субкуба определяется двумя параметрами. $\alpha ,p\in (0,1)$ .

Чтобы создать случайный субкуб $A_{i}$ , образец его компонентов $A_{ij}$ IID согласно ${\begin{aligned}Pr(A_{ij}&=\{-1\})&=p/2\\Pr(A_{ij}&=\{+1\})&=p/2\\Pr(A_{ij}&=\{-1,+1\})&=1-p\end{aligned}}$

Теперь образец $2^{(1-\alpha )N}$ случайные субкубы и объедините их вместе.

Энтропии

Плотность энтропии $r$ -й кластер в битах $s_{r}:={\frac {1}{N}}\log _{2}|A_{r}|$

Плотность энтропии системы в битах равна $s:={\frac {1}{N}}\log _{2}|\cup _{r}A_{r}|$

Фазовая структура

Размеры и количество кластеров

Позволять $n(s)$ — количество кластеров с плотностью энтропии $s$ , то оно распределено биномиально , таким образом ${\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}}$ где ${\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}}$

По неравенству Чебышева , если $\Sigma >0$ , затем $n(s)$ концентрируется до своего среднего значения. В противном случае, поскольку $E[n(s)]\to 0$ , $n(s)$ также концентрируется на $0$ по неравенству Маркова .

Таким образом, $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}}$ почти наверняка как $N\to \infty$ .

Когда $\Sigma =0$ именно, две силы точно уравновешивают друг друга, и $n(s)$ не коллапсирует, а сходится по распределению к распределению Пуассона $Poisson(1)$ по закону малых чисел.

Жидкая фаза

Для каждого состояния количество кластеров, в которых оно находится, также распределено биномиально с ожиданием $2^{(1-\alpha )N}(1-p/2)^{N}=2^{N(\log _{2}(2-p)-\alpha )}$

Итак, если $\alpha <\log _{2}(2-p)$ , то он концентрируется на $2^{N(\log _{2}(2-p)-\alpha )}$ , и поэтому каждое состояние находится в экспоненциальном числе кластеров.

Действительно, в этом случае вероятность того, что все состояния разрешены, равна $[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$

Таким образом, почти наверняка все состояния разрешены, а плотность энтропии равна 1 биту на частицу.

Кластерная фаза

Если $\alpha >\alpha _{d}:=\log _{2}(2-p)$ , то оно экспоненциально концентрируется до нуля, и поэтому большинство состояний не входят ни в один кластер. Те, кто это делает, крайне маловероятно, что они будут участвовать более чем в одном. Таким образом, мы обнаруживаем, что почти все состояния находятся в нулевых кластерах, а из состояний хотя бы в одном кластере почти все находятся только в одном кластере. Таким образом, пространство состояний представляет собой, грубо говоря, непересекающееся объединение кластеров.

Почти наверняка существуют $n(s)=2^{N\Sigma (s)}$ кластеры размером $2^{Ns}$ , следовательно, в пространстве состояний доминируют кластеры с оптимальной плотностью энтропии $s^{*}=\arg \max _{s}(\Sigma (s)+s)$ .

Таким образом, на кластерной фазе пространство состояний почти полностью разделено между $2^{N\Sigma (s^{*})}$ кластеры размером $2^{Ns^{*}}$ каждый. Грубо говоря, пространство состояний выглядит как экспоненциально множество кластеров одинакового размера.

Фаза конденсации

Другой фазовый переход происходит, когда $\Sigma (s^{*})=0$ , то есть, $\alpha =\alpha _{c}:={\frac {p}{(2-p)}}+\log _{2}(2-p)$ Когда $\alpha >\alpha _{c}$ оптимальная плотность энтропии становится недостижимой, поскольку почти наверняка существуют нулевые кластеры с плотностью энтропии $s^{*}$ . Вместо этого в пространстве состояний доминируют кластеры с энтропией, близкой к $s_{c}$ , более масштабное решение $\Sigma (s_{c})=0$ .

Около $s_{c}$ , вклад кластеров с плотностью энтропии $s=s_{c}-\delta$ к общему пространству состояний $\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 )}$ В целом $N$ , возможные плотности энтропии равны $s_{c},s_{c}-1/N,s_{c}-2/N,\dots$ . Вклад каждого составляет $2^{Ns_{c}},2^{Ns_{c}}2^{-(1+\Sigma '(s_{c}))},2^{Ns_{c}}2^{-2(1+\Sigma '(s_{c}))},\dots$

Мы можем свести их в таблицу следующим образом:


$s$	$s_{c}$	$s_{c}-1/N$	$s_{c}-2/N$
#кластеры	$1$	$2^{\Sigma '(s_{c})}$	$2^{2\Sigma '(s_{c})}$
способствует	${\frac {1}{1-2^{-(1+\Sigma '(s_{c}))}}}$	${\frac {2^{-(1+\Sigma '(s_{c}))}}{1-2^{-(1+\Sigma '(s_{c}))}}}$	${\frac {2^{-2(1+\Sigma '(s_{c}))}}{1-2^{-(1+\Sigma '(s_{c}))}}}$

Таким образом, мы видим, что для любого $\epsilon >0$ , в $N\to \infty$ предел, сверх $1-\epsilon$ всего пространства состояний покрыто только конечным числом кластеров. Пространство состояний выглядит разбитым на кластеры с экспоненциально убывающими размерами. Это фаза конденсации.

Неудовлетворительная фаза

Когда $\alpha >1$ , количество кластеров равно нулю, поэтому состояний нет.

Расширения

RSM можно расширить, включив в него энергетические ландшафты, что позволит изучать стеклообразное поведение, температурный хаос и динамический переход.

См. также

Модель случайной энергии

Ссылки

Мора, Тьерри; Здеборова, Ленка (01.06.2008). «Случайные субкубы как игрушечная модель для задач удовлетворения ограничений» . Журнал статистической физики . 131 (6): 1121–1138. arXiv : 0710.3804 . Бибкод : 2008JSP...131.1121M . дои : 10.1007/s10955-008-9543-x . ISSN 1572-9613 .
Здеборова, Ленка (25 июня 2008 г.). «Статистическая физика задач жесткой оптимизации». Акта Физика Словакия . 59 (3): 169–303. arXiv : 0806.4112 . Бибкод : 2008PhDT.......107Z .
Мезар, Марк; Монтанари, Андреа (22 января 2009 г.). Информация, физика и вычисления . Издательство Оксфордского университета. ISBN 978-0-19-154719-5 .