無限洗牌回原狀

Buttoning up misfit pairs

I’m thinking about the Poincaré recurrence theorem, which suggests that in a finite measure-preserving dynamical system, certain states must recur infinitely often, given specific conditions. For a deck of cards, if the process is truly random and measure-preserving, considering all permutations, the probability that it eventually returns to the original arrangement is 1.

Assessing recurrence

I’m figuring out the probability of a deck of cards returning to its original order after shuffles. Since each shuffle is independent, the chance of it never returning is near zero, meaning it will almost surely return.

Comparing concepts

I’m noting that the Poincaré recurrence theorem is distinct from the properties of a Markov chain or random walk. It’s interesting to see the unique characteristics of each approach.

Assessing the scenario

Interpreting the Poincaré recurrence theorem for a deck of cards, it's almost certain to return to the original order after infinite shuffles, though the timescale for this event is extraordinarily vast.

Connecting concepts

A deck of cards, with its finite state and random shuffling, matches a measure-preserving dynamical system. This means that according to the Poincaré recurrence theorem, the deck will eventually return to the original order.

Thought about 龐加萊回歸定理與撲克牌 花的時間為 34 秒

簡短結論
若採用「每次洗牌都等機率產生撲克牌所有排列」的理想模型，那麼從機率論或馬可夫鏈的角度，可知「經過無限次洗牌後，幾乎必然（機率為 1）會回到原本的排序」。這樣的結論雖可以用「龐加萊回歸定理」(Poincaré Recurrence Theorem) 或馬可夫鏈的「遍歷性」(ergodicity) 來理解，不過嚴格說來，龐加萊回歸定理本身是針對「測度守恆」的動力系統所下的結論，而隨機洗牌則通常會用馬可夫鏈遍歷性的概念來得到「最終幾乎必然回到任何狀態（包含原排序）」的結果。

1. 為什麼能「幾乎必然」回到原狀態？

1. 撲克牌的排列總數是有限的
   一副 52 張撲克牌（以 A-K 為例，假設還區分花色）所有可能的排列共有 $52!$ 種，這是一個非常巨大的但「有限」的數目。

2. 若每次洗牌都能等機率產生任一種排列

   • 把每次洗牌想像成「在所有 $52!$ 種可能排列中，選出一種」的隨機過程。
   • 只要「從任何一個排列都能有機會到達任何另一個排列」，這個隨機過程就不可約(irreducible) 且遍歷(ergodic)。

3. 馬可夫鏈遍歷性

   • 上述的「從任何狀態都有可能走到另一個狀態」條件，使得這個「隨機洗牌」可以視為一個有限狀態、不可約且非週期(aperiodic) 的馬可夫鏈。
   • 依照馬可夫鏈理論，長時間（無限次）進行後，該系統「最終會以機率 1 拜訪到所有狀態無數次」，也就是包括「回到初始排序」在內的所有可能狀態。

4. 以機率論計算

   • 每次洗牌想成一次獨立試驗，回到原排序的機率是 $1 / 52!$。
   • 計算「永遠不回到原排序」的機率，可以視為無限多次都沒有抽中那個特定排列： $$\left(1 - \frac{1}{52!}\right)^n \quad \xrightarrow[n \to \infty]{} 0.$$
   • 亦即，當洗牌次數 $n$ 趨近無限大時，「從未回到原排序」的機率趨近 0，所以「曾經回到原排序」的機率趨近 1。

2. 與龐加萊回歸定理的關係

• 龐加萊回歸定理
  通常敘述為：在一個「相空間（phase space）有有限測度且測度守恆」的動力系統中，幾乎所有初始狀態（除了測度為 0 的例外集合）都會在未來的某一時刻再次回到（或非常接近）它的初始位置。

• 洗牌是否真能用龐加萊回歸定理？

  • 嚴謹地說，龐加萊回歸定理是針對「連續或離散時間演化」且「測度守恆（體積守恆）」的「確定性」動力系統。
  • 而「隨機洗牌」更常被用馬可夫鏈的概念來處理：在「有限、不可約、非週期、且狀態轉移機率均正」的馬可夫鏈中，從任一初始狀態出發，經過足夠多次轉移後，走遍所有狀態的機率也是 1。
  • 從機率觀點的出發點雖不同，但兩種理論背後都有「系統若能遍歷所有狀態，就能再度『回到』任何先前出現過的狀態」的精神。

3. 實務上的「重回原排序」與時間尺度

• 即使理論上「幾乎必然」會回到原排序，但 $52!$ 數量級極為巨大，在實務上等待這種事件發生幾乎不可能在可觀察時間內達成。
• 換句話說：「經過足夠長時間後終究會重現」在理論上是正確的，但那個「足夠長」往往遠超過宇宙壽命。

4. 總結

• 答案：可以。
  不管是從龐加萊回歸定理的大框架，或是更貼切的「馬可夫鏈遍歷性」觀點來看，只要「每次洗牌都給予所有排列同等機會」，一副已排序好的撲克牌在無限次洗牌下，理論上會「幾乎必然（機率為 1）」回到原狀態。
• 但由於 $52!$ 極大，若要在現實中「等到它真的回到最初排序」，遠比宇宙年齡還久，所以在實務上幾乎無法觀察到。