The Organ Pipe Permutation (Q3343419)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3878336
Language Label Description Also known as
default for all languages
No label defined
    English
    The Organ Pipe Permutation
    scientific article; zbMATH DE number 3878336

      Statements

      The Organ Pipe Permutation (English)
      0 references
      0 references
      0 references
      0 references
      1984
      0 references
      file storage
      0 references
      disk
      0 references
      optimization
      0 references
      organ pipe permutation
      0 references
      Let \((p_ 1,p_ 2,...,p_ n)\) be a probability distribution, \(\pi =(\pi_ 1,\pi_ 2,...,\pi_ n)\) be a permutation of 1,2,...,n and \(X_ 1,X_ 2,...,X_ k\) be k independent and identically distributed random variables with distribution \(P(X=i)=p\pi_ i\). It is known that the organ pipe permutation \(\pi^*\) makes the range \[ D(k,\pi)=\max_{1\leq j\leq k}X_ j-\min_{1\leq j\leq k}X_ j \] a stochastic minimum for \(k=2\) [\textit{P. P. Bergmans}, Inf. Control 20, 331- 350 (1972; Zbl 0241.05021)], and minimal on the average for general k [\textit{J. R. Bitner} and \textit{C. K. Wong}, SIAM J. Comput. 8, 479-498 (1979; Zbl 0441.68030)]. We prove the stochastic minimality for general k and study a natural extension of the organ pipe permutation that is optimal when certain constraints are placed on the possible choices of \(\pi\).
      0 references

      Identifiers