Problem of the Nile

The problem of the Nile is a mathematical problem related to equal partitions of measures. The problem was first presented by Ronald Fisher in 1936–1938.[1] It is presented by Dubins and Spanier in the following words:[2]

"Each year, the Nile would flood, thereby irrigating or perhaps devastating parts of the agricultural land of a predynastic Egyptian village. The value of different portions of the land would depend upon the height of the flood. In question was the possibility of giving to each of the k residents, piece of land whose value would be 1/k of the total land value, no matter what the height of the flood."

Formally, for each height h, there is a nonatomic measure vh on the land, which represents the land values when the height of the Nile is h.

In general, there can be infinitely many different heights, and hence, infinitely many different measures. William Feller showed in 1938 that a solution for the general case might not exist.[3]

When the number of different heights (= measures) is finite, a solution always exists. This was first noted by Jerzy Neyman in 1946, and proved as a corollary of the Dubins–Spanier theorems in 1961. The problem in this case is called the exact division or consensus division problem.

A related problem is the problem of similar regions studied by Neyman and Pearson.[4] Here, instead of partitioning the land into k subsets, one only looks for a single subset, whose value for each measure vh is r times the total value (where r is a given constant in [0,1]). From existence perspective, the problem is equivalent to the problem of the Nile, as noted by Georges Darmois.[5] However, they differ in the number of required cuts. The optimal number of required cuts for any r is described in the Stromquist–Woodall theorem.

References
  1. R. A. Fisher. "Quelques remarques sur l'estimation en statistique". Byotypolagie, 1938, pp. 153–159. R. A. Fisher. "Uncertain inference". Proc. Amer. Acad. Arts Sci., vol. 77, 1936, pp. 245–257.
  2. Dubins, Lester Eli; Spanier, Edwin Henry (1961). "How to Cut a Cake Fairly". The American Mathematical Monthly. 68 (1): 1–17. doi:10.2307/2311357. JSTOR 2311357.
  3. Note on regions similar to the sample space, Statistical Research Memoirs, Cambridge, 1938, 116–125.
  4. J. Neyman and E. S. Pearson, "On the problem of the most efficient tests of statistical hypotheses", Philos. Trans. Roy. Soc. London. Ser A, vol. 231, 1932–33, pp. 289–377 (Separately as A 702).
  5. G. Darmois, "Resumes exhaustifs et probleme du Nil", C.R. Acad. Sci. Paris, vol. 222, 1946, pp 266–268.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.