與聚合隨機漫步的對偶(duality with coalescing random walks)
與聚合隨機漫步的對偶,是使投票者模型可解的精確分析機制。其想法是把一個困難的前向問題——大時刻 t 的意見組態是什麼?——翻譯成關於一群相遇即合併的隨機漫步的較易後向問題。它是交互作用粒子系統中對偶的原型範例,也是投票者模型的整個平衡結構得以寫出的緣由。
精確陳述用到對偶函數。對投票者模型,相關函數為 H(eta, A) = 1{ eta 在有限集 A 上恆為 1 }(等價地研究有限集上一致性的指示函數)。論斷是 E_eta[ H(eta_t, A) ] = E_A[ H(eta, A_t) ],左邊 eta_t 是從組態 eta 出發的投票者模型、A 是固定有限集,右邊 A_t 是從集合 A 出發、運行時間 t 的聚合隨機漫步系統,而 eta 固定在時刻 0。用白話說:欲知時刻 t 位點 A 上的意見,從 A 的每個位點逆時間送出一個隨機漫步者;每個漫步者反向追隨模仿箭頭;每當兩漫步者落在同一位點便聚合為一(因兩者皆複製自同源);時間 t 後存活的漫步者坐落在祖先位點上,而 A 在時刻 t 的意見恰是那些祖先在時刻 0 的意見。相異祖先數只能遞減,這就是聚合。對偶之所以成立,是因為投票者生成元 L 在 eta 變數中作用於 H(eta, A) 等於聚合漫步生成元在 A 變數中作用於同一 H——這是逐項可驗的代數恆等式。
此方法的威力在於對偶漫步的常返與暫態決定了原系統的相圖:以機率 1 聚合(d <= 2)迫使共識,而多個相異祖先正存活(d >= 3)則給出共存與一族連續統的不變測度。誠實的提醒是:這美妙的自對偶是特殊的:它成立是因為投票者模型為線性(其速率透過意見相左鄰居的比例線性依賴組態)。多數交互作用粒子系統並非自對偶;它們可能有不同的對偶(接觸過程以另一種單調意義對偶於自身;排他過程透過另一種對偶函數自對偶),或根本沒有可用的對偶。聚合漫步對偶亦與族群遺傳學中踏腳石(stepping-stone)與 Moran 模型的對偶概念緊密相連,那裡的後向系譜正是聚合過程(coalescent)。
欲計算在密度 rho 乘積測度下出發的投票者模型中,兩位點 x 與 y 在時刻 t 一致的機率,從 x 與 y 跑兩個聚合隨機漫步。它們一致,若已在時刻 t 前聚合(則共享一個祖先、故一個意見),或雖未聚合卻恰好出發於相同意見。在 d <= 2 隨 t 增大,聚合機率趨於 1,故 P(x 與 y 一致) -> 1:叢聚。
時刻 t 的前向意見,藉由逆向追溯祖先譜系並合併之來解碼——投票者模型的聚合系譜。
與聚合漫步的自對偶是投票者模型線性帶來的奢侈品;不要假設任意 IPS 都有這種對偶。對偶漫步逆時間運行,而兩個獨立漫步的常返/暫態(d<=2 對 d>=3)正是控制共識與共存的關鍵。