Time required to unify all particles in the scheme of equiprobable allocation into a sequence of cell layers (Q1033936): Difference between revisions

This is one of a series of papers on the following kind of discrete-time Markov chain. Imagine that one starts with \(n\) sticky particles, so that one could combine any number of them into a ``unified particle''; during this process, particles once unified remain unified, so that each outcome of the process admits a fixed set of at most \(n\) particles, unified or otherwise. Unification is determined by allocating unified particles to cells: for each integer \(t\), there is a set of \(n_t\) cells available, so that at time \(t\), particles are assigned to cells, and any collection of particles assigned to the same cell are unified into a single particle that remains a single particle for the remainder of the process. Each iteration consists of taking the \(\psi_t \leq n_t\) particles in the \(n_t\) cells at time \(t\), and independently distributing them uniformly in the next array of \(n_{t+1}\) cells, unifying those collections of particles that end up in the same cell during this iteration. The process is Markov and independent of the size of the individual particles, and we obtain the random variables \(n = \psi_0 \geq \psi_1 \geq \psi_2 \geq \cdots \geq \lim_{t\to\infty}\psi_t \geq 1\); we are also interested in the random variable \(\tau_n = \min\{t {:} \, \psi_t = \lim_{t\to\infty}\psi_t \}\). The primary result is both interesting and suggestive: if \(\min_t n_t > 1\), then \[ \mathbb{P}\left[ \lim_{t\to\infty}\psi_t > 1 \right] > 0 \Longleftrightarrow \sum_{t=1}^{\infty} n_t^{-1} < \infty. \] The bulk of the article is devoted to the special case \(1 < n_1 = n_2 = n_3 = \cdots\). Let \(\xi_1, \xi_2, \xi_3, \ldots\) be independent and with cumulative distribution functions \(\mathbb{P}\left[ \xi_j \leq x \right] = 1 - \exp(-xj(j+1)/2)\) for \(x \geq 0\), and let \(\xi = \sum_{j=1}^{\infty} \xi_j\). Then as \(n \to \infty\), the random variables \(\tau_n/n\) converge in distribution to \(\xi\).