A leader-election procedure using records (Q682267): Difference between revisions

The authors analyze a leader-election procedure which, unlike its classical version using independent, identically distributed (i.i.d.) Bernoulli trials, is based on the records in a sequence of i.i.d. continuous random variables. The procedure starts with an infinite number of players labeled by \(1, 2, 3, \dots\) who independently generate random numbers from an arbitrary continuous distribution. Those players holding a record value, that is, a value larger than those of all preceding players, stay in the game for the next round. Each round is run independently from the previous ones and in the same manner after relabeling the players still in the game by \(1, 2, 3, \dots,\) while keeping the original order. Note that player 1 always remains in the game and retains his number. Denote by \(\xi^{(n)}_i = \mathbf 1 \{\)in round \(n\), the player with the current number \(i\) survives\(\}\), (\(i, n \in \mathbb N\)) the indicator function of the event in the braces. Denote by \(N_M^{(n)}\) the number of players among \(1, 2, \dots, M\) who survived the first \(n\) rounds (\(M, n \in \mathbb N\)). Let \(S^{(n)}_j = \inf \{ i\in \mathbb N: N_i^{(n)}=j \}\), for \(j, n \in \mathbb N\) be the original numbers of the players who survived the first \(n\) rounds. Obviously, \(1=S^{(n)}_1<S^{(n)}_2<\dots\); Let \(T(M)\) be the number of rounds until only one player (which is of course the first one) among \(1, 2, \dots, M\) remains, thus \(T(M)=\inf \{ n\in \mathbb N: N_M^{(n)}=1 \}\) for \(M \in \mathbb N\). Let \(K(M)\) be the counting process of records and \(\nu(K)=\inf \{ j\in \mathbb N: K(j)=k \}\) be the associated process of record times as the corresponding first-passage time process. Hence, \(K(M)\) is the number of records in the sample of size \(M\), whereas \(\nu(K)\) is the index of the \(k\)-th record in the infinite sample. The main results of the paper are the following 2 statements. {Theorem 1.} The sequence \((T(M)- \log^{*}M)_{M\in \mathbb N}\) is tight, but it does not converge in distribution. Here, \(\log^{*}M\) is the iterated logarithm. The modified iterated exponentials (or the modified tetratron), for \(\rho \geq 1\) recursively defined by \(E_{0}(\rho)=\rho\) and \(E_{n}(\rho)=e^{E_{n-1}(\rho)-1}\) for \(n\in \mathbb N\). {Theorem 2.} \((T([E_n(\rho)]) - n)_{\rho > 1} \mathop{\longrightarrow}\limits^{\mathrm{f.d.d.}} (T^*(\rho))_{\rho > 1}\) as \(n \to\infty\), where \(\mathop{\longrightarrow}\limits^{\mathrm{f.d.d.}}\) is the weak convergence of finite-dimensional distributions, while \((T^{*}(\rho))_{\rho > 1}\) is a stochastically continuous process with nondecreasing, càdlàg sample paths satisfying the stochastic fixed-point equation \((T^{*}(e ^{\rho-1}))_{\rho > 1} \mathop{=}\limits^{\mathrm{f.d.d.}} (T^{*}(\rho)+1)_{\rho > 1}\). In particular, for each \(\rho > 1\), \(T([E_{n}(\rho)])-n\) converges in distribution to \(T^*(\rho)\) as \(n \to\infty\). The random variables \(T^*(\rho)\), \((\rho > 1)\) are integer-valued with \(P(T^*(\rho)=k)>0\) for all \(k\in Z\) and further pairwise distinct in law. The authors further provide an appropriate and apparently new kind of normalization (based on tetrations) such that the original labels of persons who stay in the game until round \(n\) converge (as \(n\to \infty\)) to some random non-Poisson point process and study its properties.