Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-10T11:13:33.844Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Random Sampling of Pairs, with Pedestrian Examples

Part of: Combinatorial probability Probabilistic methods, simulation and stochastic differential equations

Published online by Cambridge University Press:  04 January 2016

Richard Arratia  and
Stephen DeSalvo
Richard Arratia*
Affiliation:
University of Southern California
Stephen DeSalvo*
Affiliation:
University of California, Los Angeles
*
∗ Postal address: Department of Mathematics, University of Southern California, Los Angeles, CA 90089, USA.
∗∗ Postal address: Department of Mathematics, University of California, Los Angeles, CA 90095, USA. Email address: stephen.desalvo@gmail.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

For a collection of objects such as socks, which can be matched according to a characteristic such as color, we study the innocent phrase ‘the distribution of the color of a matching pair’ by looking at two methods for selecting socks. One method is memoryless and effectively samples socks with replacement, while the other samples socks sequentially, with memory, until the same color has been seen twice. We prove that these two methods yield the same distribution on colors if and only if the initial distribution of colors is a uniform distribution. We conjecture a nontrivial maximum value for the total variation distance of these distributions in all other cases.

Keywords

Total variation distancerandom samplingcomputational algebraic geometryPoisson processpair-derived distribution

MSC classification

Primary: 65C50: Other computational problems in probability
Secondary: 60C05: Combinatorial probability

Information

Type
General Applied Probability
Information
Advances in Applied Probability , Volume 47 , Issue 1 , March 2015 , pp. 292 - 305
Copyright
© Applied Probability Trust 

References

Arratia, R. and DeSalvo, S. (2011). Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example. Preprint. Available at http://uk.arxiv.org/abs/1110.3856v5 Google Scholar
Cover, T. M. and Thomas, J. A. (1991). Elements of Information Theory, John Wiley, New York.Google Scholar
Cox, D., Little, J. and O'Shea, D. (2007). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3rd edn. Springer, New York.CrossRefGoogle Scholar
Feller, W. (1968). An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd edn. John Wiley, New York.Google Scholar
Folland, G. B. (1999). Real Analysis: Modern Techniques and Their Applications, 2nd edn. John Wiley, New York.Google Scholar
Lawler, G. F. (1995). Introduction to Stochastic Processes. Chapman & Hall, New York.Google Scholar
Rudin, W. (1976). Principles of Mathematical Analysis, 3rd edn. McGraw-Hill, New York.Google Scholar