Competitive Programming Algorithm Sock Drawing Probability Question

0 votes
First let me paste the question.

This problem is based on an (almost) true story. A child, who shall remain nameless, has a large pile of clean socks. This pile contains m pairs of socks with pictures and patterns and n pure white socks. Each pair of socks consists of two identical socks and every pair is unique — no two pairs look the same. All pure white socks are identical. Each day, the child randomly selects two socks from the pile, puts them on, and heads for school. But today is a picture day and the child needs to wear two identical socks. So the child randomly selects two socks and if both socks are identical, the child puts them on and heads out the door. If the two socks are not identical, the child throws the socks into the laundry basket (they are now dirty — don’t ask why) and continues the same process of randomly selecting two socks from the pile of remaining clean socks. As this process continues, the parents are starting to get worried: Will this child ever make it to school today? Please help them to compute the probability that the child will not find a pair of identical socks using this process. This problem is based on an (almost) true story.

First of all, the limitations are n<=500 pairs of socks, and m<=200 white socks. I've really tried to solve question every way i can. I used permutation of 7! and then count the paired socks. At test problem, there are 3 white and 2 paired socks. I could only solve this by counting all paired socks in 7! permutations. Which is O(n^n) and really inefficient. Can you help me how i can solve this question? I used python by the way, and this is a competitive programming question.

I'm just solving these questions for fun, it's an open question. I've really tried 2 days to solve this, but still couldn't. Appreciate any help.

At initial test answer, there are 3 white socks and 2 paired socks (total of 7 socks). And the answer is:0.457142857142857
Mar 23 in Machine Learning by Nandini
• 5,480 points
90 views

1 answer to this question.

0 votes

Another way to look at the problem is that the child pulls pairs of socks until there are none or just one left, then looks for a matching pair. Calculate the solution using Probability 101 after computing Pr(no pair is a white match) and Pr(no pair is a patterned match | no pair is a white match).

Pr(no pair is a white match): If and only if m+2 >=2n, a white match is assured. If m+2 <2n, no pair is a white match unless and until either m is odd and there are exactly mpairs with exactly one white sock and the leftover sock is white, or m is even and there are exactly m-1 pairs with exactly one white sock and the leftover sock is white.
Consider the patterned socks to be indistinguishable for this calculation. The socks can be drawn in (m + 2n) different ways. When m is even, count the number of ways to draw the socks without a white pair as (m/2 + n) pick m ways to choose pairings with a white sock times 2m ways to draw those pairs. When m is odd, we obtain (((m1)/2 + n) select (m-1)) *2m-1 ways to have a white leftover sock and ((m1)/2 pick m) 2m ways to have a patterned leftover sock.

Pr(no pair is a patterned match | no pair is a white match): I'll take care of the situation where m is even, and you or someone else can take care of the other case. We have a total of m/2 + n pairs, with m containing exactly one white sock and n -m/2 pairs containing two patterned socks. The alternating sum is obtained by using inclusion-exclusion on subsets of matching patterns.

        i                    1            1                  1
 ∑  (−1)  (m choose i) (---------- × ---------- × … × ---------------)
i≥0                     2n + m − 1   2n + m - 3       2n + m - 2i + 1

If the number of ways to choose the I patterns is m choose I and the probability that all I are matched is the product (for each pattern in some order, we reveal the first sock and then compute the probability that its mate matches).

The odd case works similarly to the other examples, except that we divide them into groups based on whether the residual sock is white or not.

answered Mar 25 by Dev
• 6,000 points

Related Questions In Machine Learning

0 votes
1 answer

probability of getting three of a kind by drawing 5 cards

from collections package import counter to count ...READ MORE

answered Mar 25 in Machine Learning by Nandini
• 5,480 points
100 views
0 votes
1 answer
0 votes
1 answer

Calculate Z-Score from Probability Value - R programming

It's named qnorm qnorm(p=0.841344746068543) Output 1 The following family of functions ...READ MORE

answered Apr 4 in Machine Learning by Nandini
• 5,480 points
488 views
0 votes
1 answer

Example to run KNN algorithm using python

Have a look at this one: from sklearn.datasets ...READ MORE

answered May 9, 2019 in Machine Learning by Harvy
946 views
0 votes
1 answer

What is the difference between tree depth and height?

To answer your question, you will have ...READ MORE

answered Feb 9 in Python by Rahul
• 9,680 points
226 views
0 votes
0 answers
0 votes
1 answer

Why would anyone use set instead of unordered_set?

Unordered sets must compensate for their O(1) ...READ MORE

answered Jun 1 in C++ by Damon
• 4,960 points
307 views
+1 vote
2 answers

Different data structures in R

The different data types in R are ...READ MORE

answered Aug 26, 2019 in Data Analytics by anonymous
• 33,050 points
585 views
0 votes
1 answer

Is Genetic Algorithm a Machine Learning Method?

A pure Genetic Algorithm solution does not ...READ MORE

answered Feb 15 in Machine Learning by Dev
• 6,000 points
96 views
0 votes
1 answer

DBSCAN algorithm and clustering algorithm for data mining

You can use any distance function with ...READ MORE

answered Mar 4 in Machine Learning by Dev
• 6,000 points
342 views
webinar REGISTER FOR FREE WEBINAR X
REGISTER NOW
webinar_success Thank you for registering Join Edureka Meetup community for 100+ Free Webinars each month JOIN MEETUP GROUP