The box parameter for words and permutations (Q2440552): Difference between revisions

Let \(w=w_1\ldots w_n\) be a word of length \(n\), where the letters are positive integers. For \(1\leqslant j<k\leqslant n\), the indicator variable \(\chi_{j,k}\) is defined by \[ \chi_{j,k}(w)= \begin{cases} 1 &\quad \text{ if } \min\{w_j ,w_k\} < w_\ell < \max\{w_j ,w_k\} \text{ for all } j < \ell < k,\\ 0 & \quad \text{ otherwise}\end{cases} \] and the box parameter, denoted by Box, is \(\sum_{1\leqslant j<k\leqslant n}\chi_{j,k}\). Let \(\{1,\ldots,M\}\) be an alphabet, where each letter occurs with probability \(\frac1M\), and different letters are independent from each other, and put \(H_M^{(d)}=\sum_{1\leqslant k\leqslant M}\frac1{k^d}\). The author shows that the expectation of the box parameter of random words of length \(n\) over \(\{1,\ldots,M\}\) is \(2n-2n\frac{H_M}M-2H_M+2H_M^{(2)}\). A formula for the variance of the box parameter of random words of length \(n\) over \(\{1,\ldots,M\}\) is also given. If all permutations of \(n\) letters are equally likely, then it is shown that the expected value is \(2n-2H_n\). Finally, if the letter \(k\) appears with (geometric) probability \(pq^{k-1}\), with \(p + q = 1\), and the letters are independent from each other, then the author finds a formula for the expected value and it is proved that it tends to \(2n-2H_n\) as \(q\) tends to 1.