Generalizations of the Sock matching problem

Collection problems–the task of acquiring items from a population to meet a specified objective–arise in many fields, including numismatics and fraud detection, yet underlying connections between various collection problems remain unexplored. This paper provides a unifying framework for collection problems that organizes well-known examples, such as the Coupon Collector’s Problem (CCP) and the Birthday Problem (BP), and the lesser-known Sock Matching Problem (SMP), within a common structure. This paper then generalizes the classic SMP in two directions: first, to account for a collector’s current progress when computing the expected completion time; and second, to account for population loss by introducing the Sock Matching Problem with Loss (SMPL). Exact solution procedures, based on Markov chains, are developed for computing the expected completion time for each case. Finally, two case studies demonstrate the practical utility of these results while illustrating computational limitations for large instances, motivating the need for alternative formulations and approximation techniques.