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
1984
0 references
file storage
0 references
disk
0 references
optimization
0 references
organ pipe permutation
0 references
0.6906639933586121
0 references
0.6827317476272583
0 references
0.6817682981491089
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