Does Every Ranking Occur Infinitely Many Times Almost Surely?

Question

$n$ competitors vie for the championship each year. They are evenly matched, so the probability of the championship going to a given competitor in any year is $\frac{1}{n}$. The competitors’ performances, and thus the event of any competitor winning the championship, in every year are i.i.d. We start with each competitor holding $0$ championship titles. There are $n!$ total orderings of the players. Is it almost surely the case that each of these total orderings will reflect the number of titles held by competitors infinitely many times? This seems very intuitive. Can this be strengthened like so: almost surely, the set of time indices at which a given total ordering occurs will have natural density $\frac{1}{n!}$?

Answer 1

Here is one particular way of doing the details on the $n=2$ case from my comment (showing that even though the number of times player 1 is winning goes to infinity, as does player 2 winning, the fraction of time that player 1 is winning does not converge to 1/2 almost surely, or even in probability).

For each player $i \in \{1,2\}$ and time $t \in \{1, 2, 3, ...\}$ define $$ X_i[t] = \left\{\begin{array}{cc} 1 & \mbox{ if player $i$ wins the game at time $t$} \\ 0 & \mbox{ else} \end{array}\right.$$ Define $Z[0]=0$ and for $t \in \{1, 2, 3, ...\}$ define $$Z[t] = \sum_{k=1}^t(X_1[k]-X_2[k])$$
Then $\{Z[t]\}_{t=0}^{\infty}$ is a symmetric random walk (it either increases or decreases by 1 every step, equally likely, and independent of past steps). It is well known to cross the origin infinitely often, and so there will be infinitely many times at which player 1 has strictly more accumulated wins, and infinitely many times at which player 2 has strictly more accumulated wins.

At each time $t \in \{1, 2, 3, ...\}$ define \begin{align} F[t]&= \frac{\mbox{Number of slots in $\{1, ..., t\}$ that player 1 has strictly more wins}}{t}\\ &=\frac{1}{t}\sum_{k=1}^t 1_{\{Z[k]>0\}} \end{align} We show that $F[t]$ does not converge to 1/2 in probability. Suppose it does (we reach a contradiction). Fix $\epsilon=1/100$. Then $P[|F[t] -1/2|\geq\epsilon]\rightarrow 0$. For each $k \in \{1, 2, 3, ...\}$ define the events $A_k$, $B_k$, $C_k$ by \begin{align} A_k &= \{Z[2k]\geq 2\sqrt{k}\}\\ B_k &= \left(\inf_{t \in \{2k, ..., 3k\}}\{Z[t]-Z[2k]\}\right)\geq -\sqrt{k} \\ C_k &= \{F[2k]\geq 1/2- \epsilon\} \end{align} Observe that $A_k$ and $B_k$ are independent, and that $P[C_k]\rightarrow 1$. By the central limit theorem:
$$P[A_k] = P\left[\frac{Z[k]}{\sqrt{2k}}\geq \sqrt{2}\right] \rightarrow P[G\geq \sqrt{2}]=Q(\sqrt{2}) $$ where $G \sim N(0,1)$ and $Q(x)$ is the Gaussian tail function. Further, it can be shown that there is a constant $c>0$ such that $P[B_k]\geq c$ for all sufficiently large $k$. Define $$ D_k = A_k \cap B_k \cap C_k$$ Then \begin{align} P[D_k] &=P[A_k \cap B_k \cap C_k] \\ &=P[A_k \cap B_k] - P[A_k\cap B_k \cap C_k^c] \\ &=P[A_k]P[B_k] - P[A_k\cap B_k \cap C_k^c] \\ &\geq P[A_k]P[B_k] - P[C_k^c] \end{align} Since $P[C_k^c]\rightarrow 0$ we get $$\liminf_{k\rightarrow\infty}P[D_k] \geq Q(\sqrt{2})c>0$$ However, by construction, the event $D_k$ means that $F[2k]\geq 1/2-\epsilon$, but that during $\{2k,..., 3k\}$, which is a full $1/3$ of the total time of the random walk, player 1 consistently had more wins than player 2. Thus $$F[3k] = F[2k]\frac{2k}{3k} + \frac{k}{3k} \geq (1/2-\epsilon)(2/3) + (1/3) = 0.66$$ where $0.66$ follows by using $\epsilon=1/100$. That means $$D_k \subseteq \{F[3k]\geq 0.66\}$$ It means that $$\liminf_{k\rightarrow\infty}P[F[3k]\geq 0.66] > 0$$ So $F[3k]$ does not converge to $1/2$ in probability.

Answer 2

Regarding details on my other comment on $n$ players and all $n!$ rankings occurring infintely often almost surely: It is similar to showing how if $\{X_i\}$ are i.i.d. with mean $m$ and variance $\sigma^2$, then $\frac{1}{\sqrt{n\sigma^2}}\sum_{i=1}^n (X_i-m)$ does not converge to anything (though CLT ensures the distribution converges).

---

For each player $i \in \{1, ..., n\}$ and each $t \in \{1, 2, 3, ...\}$ define $$ X_i[t] = \left\{\begin{array}{cc} 1 & \mbox{ if player $i$ wins the game at time $t$} \\ 0 & \mbox{ else} \end{array}\right.$$ Define \begin{align} Y_1[t] &= X_1[t]-X_2[t]\\ Y_2[t] &= X_2[t]-X_3[t]\\ ...&\\ Y_{n-1}&=X_{n-1}[t] - X_n[t] \end{align} and define $Y[t]=(Y_1[t], ..., Y_{n-1}[t]) \in \mathbb{N}^{n-1}$. Observe that $\{Y[t]\}_{t=1}^{\infty}$ are i.i.d. vectors. The summation $\sum_{t=1}^T Y[t]$ is a vector that establishes the relative ordering in the number of wins of each player. Observe that $E[Y[t]]=0$ for all $t$ and the covariance is $\Lambda = E[Y[t]Y[t]^{\top}]$ (which does not depend on $t$). [I believe $\Lambda$ is an invertible Toeplitz matrix, I reduced the dimension to $n-1$ since the $n$-dimensional vector $(X_1[t], ..., X_n[t])$ does not have an invertible covariance matrix. I am not quite sure what the multidimensional CLT implies when the covariance matrix is not invertible.]

Define for $t_0 \in \{1, 2, 3, ...\}$ and $T \in \{1, 2, 3, ...\}$: $$ G(t_0, T) =\frac{1}{\sqrt{T}}\sum_{t=t_0}^{t_0+T-1}Y[t] $$ The multidimensional CLT ensures that for any $t_0 \in \{1, 2, 3, ...\}$ we have $$\lim_{T\rightarrow\infty} P[G(t_0,T)\leq x] = P[N\leq x] \quad \forall x \in \mathbb{R}^n$$ where $N$ is a $(n-1)$-dimensional jointly Gaussian variable with mean 0 and covariance matrix $\Lambda$. https://en.wikipedia.org/wiki/Central_limit_theorem

Now divide the timeline into consecutive frames of steps. Let $F_k$ be the size of frame $k \in \{1, 2, 3, ...\}$. Assume frame sizes grow rapidly so that $F_{k+1}$ is "way way larger" than $F_1+...+F_k$. Let $T_k=F_1+...+F_k$. Then $$G(1,T_{k+1}) = \frac{\sum_{t=1}^{T_k}Y[t]}{\sqrt{T_{k+1}}} + G(T_k+1, F_{k+1})\frac{\sqrt{F_{k+1}}}{\sqrt{T_{k+1}}}$$ Since $-\vec{1}\leq Y[t]\leq \vec{1}$ for all $t$ (where $\vec{1}$ is a $(n-1)$-dimensional vector of 1s) we get $$ \frac{(-\vec{1})T_k}{\sqrt{T_{k+1}}} + G(T_k+1, F_{k+1})\frac{\sqrt{F_{k+1}}}{\sqrt{T_{k+1}}}\leq G(1,T_{k+1})\leq \frac{(\vec{1})T_k}{\sqrt{T_{k+1}}} + G(T_k+1, F_{k+1})\frac{\sqrt{F_{k+1}}}{\sqrt{T_{k+1}}}$$ We assume the frames grow so rapidly that $\frac{T_k}{\sqrt{T_{k+1}}}\rightarrow 0$ and $\sqrt{F_{k+1}/T_{k+1}}\rightarrow 1$. The point is that the value of the vector $G(1,T_{k+1})$, which determines the relative player scores at time $T_{k+1}$, is asymptotically independent of anything that happened on previous frames (so it largely only depends on what happens in frame $k+1$). So it is "almost" like we independently select a new vector on each new frame $k$. Now this vector asymptotically has a joint Gaussian distribution with all $n!$ rankings equally likely. So it is "almost" like independently selecting a new ranking every frame, equally likely over all $n!$ choices, so we will get all such $n!$ rankings infinitely often (with prob 1).

[Now I wish I could be more precise than using all the "almost" words but I do not know a way to do that without significantly expanding on the complexity of the argument...What I have here is enough for me to be convinced myself. I'm sure someone like Paul Erdos could define some martingale and prove the result in 2 lines. =) ]