Random Analysis: Element-Location Probabilities¶
Problem setter's element-location recurrence. Codex (GPT-6) supplies a C++17 implementation with rolling arrays. Program: alternative-element-probabilities.cpp. See the main editorial for the preferred method and comparison.
Track one original element¶
Write \(M=998244353\) .
Temporarily distinguish elements by original index, even when their values coincide. Fix the element initially at \(s\) , and let \(q_j\) be its current probability of occupying position \(j\) . Initially \(q_s=1\) and all other entries are zero.
In round \(i\) , save \(c=q_i\) . For \(j\ne i\) , an element already at \(j\) remains there with probability \((n-1)/n\) ; one at \(i\) moves to \(j\) with probability \(1/n\) . These events are disjoint, giving
Its probability of ending this round at position \(i\) is
because the element occupies exactly one position. The argument holds for every preceding state, so induction gives the correct final distribution.
Form the answer¶
Write this distribution as \(q_{s,j}\) . Run the process for every original element, accumulating \(E_j=\sum_s a_s q_{s,j}\) . Linearity of expectation proves the result without assuming independent element positions.
Complexity and tradeoffs¶
Each original element runs \(n\) rounds with \(n\) updates, giving \(O(n^3+\log M)\) time. Its distribution uses \(O(n)\) rolling space. The expectation accumulator also uses \(O(n)\) , so total space is \(O(n)\) .
This method directly describes each element's destination and provides an independent comparison for faster recurrences. It is a correct backup; see the main timing results. Always use the saved old \(c\) within a round.