On sums of products of Bernoulli variables and random permutations (Q1827473): Difference between revisions

Let \(\{X_k\}_{k\geq 1}\) be independent Bernoulli random variables, where the distribution of \(X_k\) is \(q_k\delta_0+ p_k\delta_1\), \(p_k= 1-q_k\) situated in \((0, 1)\). The random number \(S_n= \sum^n_{k=1} X_k X_{k+1}\) can be interpreted as the number of runs of length 2, and if \(\sum^\infty_{k=1} p_k p_{k+1}< \infty\), then \(S= \sum^\infty_{k=1} X_k X_{k+1}\) is shown to exist almost surely (Borel-Cantelli lemma). P. Diaconis noticed (1996) surprisingly that, when \(p_k= 1/k\) for all \(k\), \(S\) is Poisson distributed with mean 1, using a combinatorial argument. The same result was obtained by M. Emery (1998). The aim of the present paper is twofold: to provide a third, simpler analytic proof of the Diaconis result, together with its generalization. Specifically, taking \(p_k=1/(1+ B)\), with \(B> 0\), Section 2 shows that the distribution of \(S\) is a Beta mixture of Poisson distributions. Section 3 contains remarks concerning the case when \(X_n\) are independently distributed, \(p_k= p\) for all \(k\). Since \(S_n\) is known to be type II binomial of order 2, the authors obtain the generating function of \(S_n\) for \(p= \sqrt{\lambda n}+ O(1/\sqrt{n})\), with \(\lambda\) the Poisson parameter. Section 4 investigates the case \(p_k= 1/(1+ B)\) with \(B\) assumed to be a nonnegative integer. In this case, the distribution \(S_n\) is related to a certain distribution (arising in the matching type problem) of the random permutation \(\pi\) of the set \(\{1,2,\dots, n+ B\}\).