[3] Quenched law of large numbers and quenched central limit theorem for multi-player leagues with ergodic strengths (with Benedetta Cavalli)

Notation: Given \(n\in\mathbb{N}=\{1,2,3,\dots\}\), we set \([n]=\{1,2,\dots,n\}\) and \([n]_0=\{0,1,2,\dots,n\}\). We also set \(\mathbb{R}_+=\mathbb{R}\cap[0,\infty)\).

The model

We consider a league of \(2n\in2\mathbb{N}\) teams denoted by \(\{T_{i}\}_{i\in [2n-1]_0}\) whose initial random strengths are denoted by \(\{S_{i}\}_{i\in [2n-1]_0}\in \mathbb{R}_+^{2n}\).

In the league every team \(T_i\) plays \(2n-1\) matches, one against each of the remaining teams \(\{T_{j}\}_{j\in [2n-1]_0\setminus\{i\}}\). Note that there are in total \({2n}\choose{2}\) matches in the league. These matches are played in \(2n-1\) different days in such a way that each team plays exactly one match every day.

For all \(i\in[2n-1]_0\), the initial strength \(S_i\) of the team \(T_i\) is modified every day according to a discrete time \(\mathbb{R}_+\)-valued stochastic process \(\textbf{$\xi$}^i=(\xi^i_j)_{j\in \mathbb{N}}\). More precisely, the strength of the team \(T_i\) on the \(p\)-th day is equal to \( S_i\cdot  \xi^i_p\in \mathbb{R}_+\).

We now describe the rules for determining the winner of a match in the league. We fix a function \(f:\mathbb R_+^2\to[0,1]\) that controls the winning probability of a match between two teams given their strengths. When a team with strength \(x\) plays a match against another team with strength \(y\), its probability of winning the match is equal to \(f(x,y)\) and its probability of loosing is equal to \(1-f(x,y)\) (we are excluding the possibility of having a draw). Therefore, if the match between the teams \(T_i\) and \(T_j\) is played the \(p\)-th day, then, conditionally on the random variables \(S_i, S_j, \xi^i_p, \xi^j_p\), the probability that \(T_i\) wins is \(f(S_i\cdot \xi^i_p,S_j\cdot \xi^j_p)\).

Moreover, conditionally on the strengths of the teams, the results of different matches are independent.

Assumptions

The goal of this work is to study the model defined above when the number \(2n\) of teams in the league is large. We want to look at the limiting behavior of the number of wins of a team with initial strength \(s\in \mathbb{R}_+\)at the end of the league. More precisely, given \(s\in \mathbb{R}_+\), we assume w.l.o.g. that the team \(T_{0}\) has deterministic initial strength \(s\), i.e. \(S_{0}=s\) a.s., and we set

\(W_n(s):=\text{Number of wins of the team }T_{0}\text{ at the end of a league with \(2n\) players}.\)

We investigate a quenched law of large numbers and a quenched central limit theorem for \(W_n(s)\). In the following two subsections we state some assumptions on the model.

Assumptions for the law of large numbers

We make the following natural assumptions on the function \(f:\mathbb R_+^2\to[0,1]\:\):

  • \(f(x,y)\) is measurable;
  • \(f(x,y)\) is weakly-increasing in the variable \(x\) and weakly-decreasing in the variable \(y\).

Recall also that it is not possible to have a draw, i.e. \(f(x,y)+f(y,x)=1\), for all \(x,y\in \mathbb{R}_+\).

Before describing our additional assumptions on the model, we introduce some further quantities. Fix a Borel probability measure \(\nu\) on \(\mathbb{R}_+\); let \(\xi=(\xi_\ell)_{\ell\in \mathbb{N}}\) be a discrete time \(\mathbb{R}_+\)-valued stochastic process such that \(
\xi_\ell\stackrel{d}{=}\nu,\) for all  \(\ell\in \mathbb{N},
\) and (this is a weak-form of the stationarity property for stochastic processes):
\(
\left(\xi_\ell, \xi_k\right)\stackrel{d}{=} \left(\xi_{\ell+\tau}, \xi_{k+\tau}\right), \quad\text{for all}\quad \ell,k,\tau\in\mathbb{N}.
\)

We further assume that the process \(\xi\) is weakly-mixing, that is, for every \(A \in \sigma(\xi_1)\) and every collection of sets \(B_\ell \in \sigma(\xi_\ell)\), it holds that
\(
\frac{1}{n} \sum_{\ell=1}^n \left|\mathbb{P}(A \cap B_\ell)-\mathbb{P}(A)\mathbb{P}(B_\ell)\right|\rightarrow 0.
\)

The additional assumptions on our model are the following:

  •  For all \(i\in[2n-1]_0\), the stochastic processes \( \xi^i\) are independent copies of \(\xi\).
  • The initial random strengths \(\{S_i\}_{i\in[2n-1]}\) of the teams different than \(T_0\) are i.i.d. random variables on \(\mathbb{R}_+\) with distribution \(\mu\), for some Borel probability measure \(\mu\) on \(\mathbb{R}_+\).
  • The initial random strengths \(\{S_i\}_{i\in[2n-1]}\) are independent of the processes \(\{ \xi^i\}_{i\in[2n-1]_0}\) and of the process \( \xi\).
Further assumptions for the central limit theorem

In order to prove a central limit theorem, we need to make some stronger assumptions. The first assumption concerns the mixing properties of the process \(\xi\). For \(k \in \mathbb{N}\), we introduce the two \(\sigma\)-algebras \(\mathcal{A}_1^{k} = \sigma \left(\xi_1, \dots, \xi_k \right)\) and \(\mathcal{A}_k^{\infty} = \sigma \left(\xi_k, \dots \right)\) and we define for all \(n\in\mathbb{N}\),
\(
\alpha_n = \sup_{k \in \mathbb{N}, A \in \mathcal{A}_1^{k},B \in \mathcal{A}_{k+n}^{\infty}}
\left| \mathbb{P} \left( A \cap B \right) – \mathbb{P}(A)\mathbb{P}(B) \right|.
\)
We assume that \(
\sum_{n=1}^{\infty} \alpha_n < \infty.
\)
Note that this condition, in particular, implies that the process \(\xi\) is strongly mixing, that is, \(\alpha_n \to 0\) as \(n \to \infty\).

Finally, we assume that there exist two sequences \(p=p(n)\) and \(q=q(n)\) such that:

  • \(p\to +\infty\) and \(q\to+\infty\),
  • \(q=o(p)\) and \(p=o(n)\) as \(n \to \infty\),
  • \(n p^{-1 } \alpha_q =o(1)\),
  • \(\frac{p}{n} \cdot \sum_{j=1}^p j \alpha_j = o(1)\).

Main results

Let \(V, V’, U, U’\) be four independent random variables such that \(V\stackrel{d}{=}V’\stackrel{d}{=}\nu\) and \(U\stackrel{d}{=} U’\stackrel{d}{=}\mu\). Given a deterministic sequence \(\vec{s}=(s_i)_{{i\in\mathbb{N}}}\in\mathbb{R}^{\mathbb{N}}_{+}\), denote by \(\mathbb{P}_{\vec{s}}\) the law of the random variable \(\frac{W_n(s)}{2n}\) when the initial strengths of the teams \((T_i)_{i\in[2n-1]}\) are equal to \(\vec{s}=(s_i)_{{i\in[2n-1]}}\), i.e. we study \(\frac{W_n(s)}{2n}\) on the event

\(S_0=s\quad \text{ and }\quad(S_i)_{{i\in[2n-1]}}=(s_i)_{{i\in[2n-1]}}.\)

 

Theorem (Quenched law of large numbers).
Suppose that the assumptions for the law of large numbers hold. Fix any \(s\in\mathbb{R}_+\). For \(\mu^{\mathbb{N}}\)-almost every sequence \(\vec{s}=(s_i)_{{i\in\mathbb{N}}}\in\mathbb{R}^{\mathbb{N}}_{+}\), under \(\mathbb{P}_{\vec{s}}\) the following convergence in probability holds

\(
\frac{W_n(s)}{2n}\to\ell(s)=\mathbb{E}\left[f\left(s\cdot V, U\cdot V’\right)\right]=\int_{\mathbb{R}^3_+} f\left(s\cdot v,u\cdot v’\right)d\nu(v)d\nu(v’)d\mu(u).
\)

 

Theorm (Quenched central limit theorem).
Suppose that the assumptions for the law of large numbers and the central limit theorem hold. Fix any \(s\in\mathbb{R}_+\). For \(\mu^{\mathbb{N}}\)-almost every sequence \(\vec{s}=(s_i)_{i\in\mathbb{N}}\in\mathbb{R}^{\mathbb{N}}_{+}\), under \(\mathbb{P}_{\vec{s}}\) the following convergence in distribution holds

\(
\frac{W_n(s)- \mathbb{E}_{\vec{s}}[W_n(s)] }{\sqrt{2n}}\to \mathcal{N}\left(0,\sigma(s)^2 + \rho(s)^2\right),
\)

where, for \(F_s(x,y)=\mathbb{E}\left[f\left(s\cdot x,y\cdot  V’\right)\right]\) and \(\tilde F_s \left(x,y\right) = F_s\left(x,y \right) – \mathbb{E}[F_s\left(V, y\right)]\),
\(
\sigma(s)^2=\mathbb{E}\left[F_s(V,U)-\left(F_s(V,U)\right)^2\right]=\ell(s)-\mathbb{E}\left[\left(F_s(V,U)\right)^2\right]
\)
and
\(
\rho(s)^2= \mathbb{E} \left[ \tilde F_s (V, U)^2 \right] + 2 \cdot \sum_{k=1}^{\infty} \mathbb{E}\left[ \tilde F_s(\xi_1, U) \tilde F_s (\xi_{1+k}, U’) \right],
\)
the last series being convergent.

To obtain our results, we also prove the following general result that we believe to be of independent interest.

Theorem.
Let \(\xi=(\xi_\ell)_{\ell\in \mathbb{N}}\) be a discrete time \(\mathbb{R}_+\)-valued stochastic process such that \(
\xi_\ell\stackrel{d}{=}\nu,\) for all  \(\ell\in \mathbb{N},
\) and \(
\left(\xi_\ell, \xi_k\right)\stackrel{d}{=} \left(\xi_{\ell+\tau}, \xi_{k+\tau}\right),\) for all \(\ell,k,\tau\in\mathbb{N}.
\) Suppose that the assumptions for the central limit theorem hold. Let \(g:\mathbb{R}^2_+\to\mathbb{R}_+\) be a bounded, measurable function, and define \(\tilde g :\mathbb{R}^2_+\to\mathbb{R}\) by \(\tilde g (x,y) = g(x,y) – \mathbb{E} \left[ g\left(V, y\right) \right]\). Then, the quantity
\(
\rho_g^2 = \mathbb{E} \left[ \tilde g (V, U)^2 \right] + 2 \cdot \sum_{k=1}^{\infty} \mathbb{E}\left[ \tilde g(\xi_1, U) \tilde g (\xi_{1+k},  U’) \right]
\)
is finite. Moreover, for \(\mu^{\mathbb{N}}\)-almost every sequence \((s_i)_{{i\in\mathbb{N}}}\in\mathbb{R}^{\mathbb{N}}_{+}\), the following convergence in distribution holds

\(
\frac{\sum_{j=1}^{2n-1}\tilde g\left(\xi_j,s_j\right)}{\sqrt{2n}}\to \mathcal{N}(0,\rho_g^2).
\)

 

ArXiv