Теорема Гаммерслі — Кліффорда — це результат у теорії ймовірностей, математичній статистиці та статистичній механіці, який дає необхідні та достатні умови, за яких дискретний розподіл ймовірностей зі строго додатними імовірностями може бути представлений графовим об'єктом відомим як марковське випадкове поле. Це — фундаментальна теорема теорії випадкових полів. Вона стверджує, що розподіл ймовірностей, який має строго додатну функцію маси ймовірності або густину, задовольняє одну з марковських властивостей відносно неорієнтованого графа тоді і тільки тоді, коли цей розподіл є Гіббсівським випадковим полем, тобто його густина може бути факторизована за кліками (або повними підграфами) графа.
Зв’язок між Гіббсівськими випадковими полями та строго додатними за розподілом Марковськими був помічений та у контексті статистичної механіки. Теорема названа на честь Джона Гаммерслі та Пітера Кліффорда, які довели еквівалентність двох типів випадкових полів у неопублікованій роботі 1971 року. Простіші доведення з використанням принципу включень-виключень були незалежно наведені , Престоном та Шерманом в 1973, з подальшим доведенням у виконнанні в 1974.
Схема доведення
Показати, що Гіббсівське випадкове поле задовольняє кожну властивість Маркова, — тривіально. Наприклад:
На зображенні праворуч Гіббсівське поле над заданим графом має вигляд . Якщо зафіксувати змінні та , то глобальна властивість Маркова за визначенням даватиме (див. ), оскільки , утворюють бар'єр між , та , .
За умови фіксації константних та , , де та . Це означає, що .
Щоб довести, що кожен строго додатний розподіл ймовірностей, який задовольняє локальну властивість Маркова, також є Гіббсівським випадковим полем, потрібно довести наступну лему, яка дозволяє об'єднувати різні факторизації:
Лема 1
Нехай — множина всіх випадкових змінних, а та — довільні множини змінних. (Тут, для довільної множини змінних, позначеної символом , цей же символ також позначає і довільний вибір конкретних константних значень цих змінних з .)
Якщо
для функцій та , тоді існують функції та такі, що
Іншими словами, надає спосіб покроково побудувати подальшу факторизацію за шаблоном .
Щоб використати як шаблон для подальшої факторизації , потрібно зафіксувати всі змінні поза . Нехай — операція що задає довільне фіксоване присвоєння константних значень змінним з (змінні, що не належать ). Для довільної множини змінних , нехай — це призначення , обмежене змінними з .
Крім того, щоб факторизувати лише , інші множники мають бути незначущими відносно змінних з . Для цього факторизація
має бути перетворена наступним чином:
Для всіх : — це , де всі змінні поза зафіксовані як сталі згідно з операцією присвоєння .
Нехай
та
для кожного , тоді
Найважливіше те, що , коли константні значення, присвоєні , не суперечать значенням, заданим , тобто "зникає", коли всі змінні поза зафіксовані згідно з .
Фіксуючи всі змінні поза згідно з , маємо
Оскільки ,
Нехай , тоді:
і нарешті:
Лема 1 обгрунтовує спосіб узгодження двох різних факторизацій розподілу . З локальної властивості Маркова тоді випливає, що для будь-якої випадкової змінної існують множники та такі, що:
де — сусіди вершини . Ітеративне покрокове застосування Леми 1 призводить до факторизації у добуток потенціалів відповідно до графових клік (див. зображення праворуч).
Кінець доведення
Див. також Марковське випадкове поле Умовне випадкове поле
Примітки
Додаткова література