The Bohnenblust-Spitzer algorithm and its applications (Q1612308)

Starting from a sequence of \(n\) real number \(x_1,x_2,\dots, x_n\), which are supposed to be linearly independent over \(\mathbb{Z}\), and any permutation \(\sigma= (\sigma_1,\sigma_2,\dots, \sigma_n)\), one can form the partial sums \(s_k(\sigma)= x_{\sigma_1}+ x_{\sigma_2}+\cdots+ x_{\sigma_k}\), for \(1\leq k\leq n\). Then, the word representation for \(\sigma\) can be broken into blocks, corresponding to the faces of \(M(\sigma)\), which is the least concave majorant of the set of \(n\) points \(p_k= (k,s_k(\sigma))\). This furnishes a new permutation \(\tau\), and the Bohnenblust-Spitzer algorithm is the procedure for the mapping \(\sigma\to\tau\). Its power comes from the fact that many of the geometric features of the graph of \(M(\sigma)\) can be written in the general form \[ Z_f(\tau)= \sum_{C\in\tau} f\Biggl(|C|, \sum_{i\in C} x_i\Biggr), \] where \(C\in\tau\) means that \(C\) is a cycle of \(\tau\). Consequently, one can get precise probabilistic information about the geometry of random walks. The author obtains means, variances and concentration inequalities for several random variables associated with a random walk, including the number of vertices and length of the convex minorant, concave majorant and convex hull. He also provides an interesting and exhaustive discussion about related problems and different approaches.