The Sock Problem Revisited
Document Type
Article
Publication Title
The College Mathematics Journal
Abstract
When matching n pairs of socks, drawn randomly one at a time, there is a question of how big the pile of unmatched socks is expected to get. Each permutation of socks drawn has a corresponding Dyck path, with the total number of Dyck paths equaling the n-th Catalan number. However, some discussions failed to take into account that not every Dyck path is equally likely in the process of sorting socks. In this paper we will take the probabilities of the Dyck paths into account, and find a method of finding the expected maximum size of the unmatched sock pile. We also find the first two terms of the asymptotic series for this maximum, and give a conjecture on the third term.
First Page
193
Last Page
203
DOI
10.1080/07468342.2021.1897371
Publication Date
5-27-2021
Recommended Citation
Paulsen, William, "The Sock Problem Revisited" (2021). Faculty Publications. 6.
https://arch.astate.edu/scm-mathfac/6
