{"id":2381,"date":"2018-08-11T13:29:56","date_gmt":"2018-08-11T18:29:56","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=2381"},"modified":"2018-08-15T18:26:27","modified_gmt":"2018-08-15T23:26:27","slug":"rug-quality-control","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/rug-quality-control\/","title":{"rendered":"Rug quality control"},"content":{"rendered":"

This Riddler puzzle<\/a> is about rug manufacturing. How likely are we to avoid defects if manufacture the rugs randomly?<\/p>\n

\nA manufacturer, Riddler Rugs\u2122, produces a random-pattern rug by sewing 1-inch-square pieces of fabric together. The final rugs are 100 inches by 100 inches, and the 1-inch pieces come in three colors: midnight green, silver, and white. The machine randomly picks a 1-inch fabric color for each piece of a rug. Because the manufacturer wants the rugs to look random, it rejects any rug that has a 4-by-4 block of squares that are all the same color. (Its customers don\u2019t have a great sense of the law of large numbers, or of large rugs, for that matter.)<\/p>\n

What percentage of rugs would we expect Riddler Rugs\u2122 to reject? How many colors should it use in the rug if it wants to manufacture a million rugs without rejecting any of them?\n<\/p><\/blockquote>\n

Here is my solution:
\n[Show Solution]<\/a><\/p>\n

\nSince every possible rug is equally likely to occur, the probability of a rug being rejected is equal to the total number of defective rugs divided by the total number of rugs. Let’s assume the rug is $n\\times n$, there are $d$ distinct color choices, and we’re looking to avoid $m\\times m$ same-color patches. There are $N = (n-m+1)^2$ different $m\\times m$ patches on the rug. For easier bookkeeping, let’s number these using a single index $1 \\le i \\le N$. Let’s define the following event:
\n\\[
\nX_{i} = \\left\\{
\n\\begin{array}{l}\\text{the }i^\\text{th} \\text{ }m\\times m \\text{ patch}\\\\\\text{is all the same color}\\end{array}\\right.
\n\\]The union of these events $X = \\bigcup_{i=1}^N X_{i}$ describes the case where there is at least one same-color patch on the rug and therefore the rug must be rejected. We seek to compute the probability $\\mathbb{P}(X)$.<\/p>\n

The inclusion-exclusion principle<\/a> allows us to express $X$ in terms of the $X_i$, which will be useful because of the inherent symmetry present in the problem. Specifically, each $X_i$ has the same probability of occurrence! If we define the probabilities:
\n\\begin{align}
\nS_1 &= \\sum_{1\\le i \\le N} \\mathbb{P}(X_i) \\\\
\nS_2 &= \\sum_{1\\le i\\lt j\\le N} \\mathbb{P}(X_i \\cap X_j) \\\\
\n&\\,\\,\\,\\vdots \\\\
\nS_k &= \\sum_{1\\le i_1 \\lt\\cdots\\lt i_k\\le n} \\mathbb{P}(X_{i_1} \\cap \\cdots \\cap X_{i_k})
\n\\end{align}then the inclusion-exclusion principle states that:
\n\\[
\n\\mathbb{P}(X) = \\sum_{k=1}^N (-1)^{k-1}S_k
\n\\]We mentioned that the individual probabilities $\\mathbb{P}(X_i)$ are easy to compute. Indeed, each color occurs with probability $1\/d$ and there are $m^2$ cells in each patch. So the probability that all cells are of a particular color is $1\/d^{m^2}$. Multiplying by $d$ to account for the $d$ possible colors, we obtain:
\n\\[
\n\\mathbb{P}(X_i) = \\frac{1}{d^{m^2-1}}\\qquad\\text{for all }i
\n\\]Therefore, $S_1 = N\/d^{m^2-1}$. Setting $n=100,\\,m=4,\\,d=3$, we find:
\n\\[
\nS_1 = 0.065573\\%
\n\\]To compute $S_2$, we must compute the probability of the intersection of two events, i.e. the probability that two patches are simultaneously mono-colored. There are two possibilities:
\n\\[
\n\\mathbb{P}(X_i \\cap X_j) = \\begin{cases}
\n\\frac{1}{d^{2(m^2-1)}} & \\begin{array}{l}\\text{if the patches don’t overlap}\\end{array}\\\\
\n\\frac{1}{d^{c-1}} & \\begin{array}{l}
\n\\text{if the patches overlap and}\\\\
\n\\text{together cover }c\\text{ cells in total}
\n\\end{array}
\n\\end{cases}
\n\\]This follows because when patches don’t overlap, the events are independent, so the probability that both patches are mono-colored is the product of probabilities that each is mono-colored. When the patches overlap, however, they can only both be mono-colored if they are both the same<\/em> color! And here, the probability depends on how much the patches overlap. I wrote a simple script that loops over all pairs of patches, computes the above probabilities, and sums them up. The result was:
\n\\[
\nS_2 = 0.0017071\\%
\n\\]We could continue in this fashion, computing $S_3,S_4,\\dots$ but this is a hopeless endeavor as we must account for the probability that $k$ patches are simultaneously mono-colored… which will get messy in a hurry. Instead, we’ll use an additional piece to the inclusion-exclusion principle, called the Bonferroni inequality<\/a>, which states that as we add and subtract the $S_k$ terms on our way to computing $\\mathbb{P}(X)$, they alternate between providing upper and lower bounds!. This means that we can use $S_1$ and $S_2$ to compute an approximation:
\n\\[
\nS_1-S_2 \\le \\mathbb{P}(X) \\le S_1
\n\\]Substituting the numbers we computed above, we obtain:<\/p>\n

$\\displaystyle
\n0.063866\\% \\lt \\mathbb{P}(\\text{rug is rejected}) \\lt 0.065573\\%
\n$<\/span><\/p>\n

It’s reasonable to expect that $S_k$ will continue to decrease as $k$ increases. If we assume that the $S_k$ will decrease geometrically, that would give us $S_3 \\approx 0.000044\\%$, which would tighten our bound to $0.06387 \\lt \\mathbb{P}(X) \\lessapprox 0.06391\\%$. So if I had to guess a single number, it would be that the probability of rejection is about $0.0639\\%$.<\/p>\n

For the second part of the problem, we are asked about how many colors we should use in order to be ensured that we can manufacture one million rugs and have no rejections. Each rug is independently manufactured, so if we call $p$ the probability of one rug being rejected, the probability that no rugs get rejected after one million rugs are made is:
\n\\[
\n\\mathbb{P}(\\text{no rejections}) = (1-p)^{1,000,000}
\n\\]Since we don’t know the exact value of $p$, we can again compute upper and lower bounds. Since we want a conservative estimate of how many colors to use, it makes sense to under-estimate<\/em> the probability of having no rejections. This amounts to using our upper bound<\/em> for $p$. Here is a plot showing the probability of no rejections in the entire batch, as a function of $d$, the number of colors used.<\/p>\n

\"\"<\/a><\/p>\n

Remember that these are lower bounds<\/em> on the probability that no rugs get rejected. The true probability will be higher. Based on this fact, we’ll likely be safe if we pick $6$ colors.<\/p>\n

Here are the probabilities in tabular form, and I also included the corresponding upper bound using the Bonferroni inequality discussed earlier.<\/p>\n\n\n\n\n\n\n\n\n\n\n
Colors<\/th>\nlower bound on probability<\/th>\nupper bound on probability<\/th>\n<\/tr>\n
$3$<\/td>\n$0$<\/td>\n$3.9\\times 10^{-8}$<\/td>\n<\/tr>\n
$4$<\/td>\n$0.01564\\%$<\/td>\n$93.320\\%$<\/td>\n<\/tr>\n
$5$<\/td>\n$73.4684\\%$<\/td>\n$99.901\\%$<\/td>\n<\/tr>\n
$6$<\/td>\n$98.0188\\%$<\/td>\n$99.996\\%$<\/td>\n<\/tr>\n
$7$<\/td>\n$99.802\\%$<\/td>\n$100\\%$<\/td>\n<\/tr>\n
$8$<\/td>\n$99.973\\%$<\/td>\n$100\\%$<\/td>\n<\/tr>\n
$9$<\/td>\n$99.9954\\%$<\/td>\n$100\\%$<\/td>\n<\/tr>\n
$10$<\/td>\n$99.9991\\%$<\/td>\n$100\\%$<\/td>\n<\/tr>\n<\/table>\n

The upper bound makes a big jump when we add a fourth color, and as discussed previously, this bound is likely the tighter of the two. So although we argued for 6 colors before, this is probably overly conservative and we could get away with using 5 colors.<\/p>\n<\/div>\n

<\/p>\n","protected":false},"excerpt":{"rendered":"

This Riddler puzzle is about rug manufacturing. How likely are we to avoid defects if manufacture the rugs randomly? A manufacturer, Riddler Rugs\u2122, produces a random-pattern rug by sewing 1-inch-square pieces of fabric together. The final rugs are 100 inches by 100 inches, and the 1-inch pieces come in three colors: midnight green, silver, and … Continue reading “Rug quality control”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":2395,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[18,8,2,34],"class_list":["post-2381","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-linearity-of-expectation","tag-probability","tag-riddler","tag-statistics"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2381","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=2381"}],"version-history":[{"count":16,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2381\/revisions"}],"predecessor-version":[{"id":2402,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2381\/revisions\/2402"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/2395"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=2381"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=2381"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=2381"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}