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.