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

[wiki_en]

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

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

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

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

== Настройка ==

=== Подкубы ===

Имеется 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 1N \log_2 |A_r|

Плотность энтропии системы в битах равна
s := \frac 1N \log_2 |\cup_r A_r|
== Фазовая структура ==

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

Пусть n(s) — количество кластеров с плотностью энтропии s, тогда это биномиальное распределение|биномиально распределено, таким образом

\begin{aligned
E[n(s)] &= 2^{(1-\alpha)N} P \to 2^{N\Sigma(s)} \\
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}, \\
\end{aligned}


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

Таким образом,
n(s) \to \begin{cases}
2^{N\Sigma(s)} \quad &\text{if }\Sigma(s) > 0\\
0 \quad &\text{if }\Sigma(s) < 0
\end{cases}
почти наверняка как N\to\infty.

Когда \Sigma = 0 точно, две силы точно уравновешивают друг друга, и n(s) не разрушается, а вместо этого сходится по распределению к распределению Пуассона Пуассона(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^* = \max_s (\Sigma (s) + s).

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

Другой фазовый переход происходит, когда
\Sigma(s^*) = 0
то есть
\alpha = \alpha_c := \frac{p}{(2-p)}+\log _2(2-p)

Для \alpha > \alpha_c в пространстве состояний преобладают кластеры с s_c, удовлетворяющие \Sigma(s_c) = 0. Таких кластеров субэкспоненциальное количество.

Вблизи s_c вклад кластеров с плотностью энтропии s = s_c - \delta в общее пространство состояний составляет
\underbrace{2^{Ns_{\text{размер кластеров \times \underbrace{2^{N\Sigma(s)_{\text{количество кластеров = 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

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

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

=== Неудовлетворительная фаза ===
Если \alpha > 1, количество кластеров равно нулю, поэтому состояний нет.

== Расширения ==

== См. также ==

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

* * *
Статистическая механика

Подробнее: https://en.wikipedia.org/wiki/Random_subcube_model