-
Notifications
You must be signed in to change notification settings - Fork 8
/
Copy pathsock-buffer.html
132 lines (120 loc) · 6.57 KB
/
sock-buffer.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
<!DOCTYPE html>
<html>
<head>
<link rel="canonical" href="https://hardmath123.github.io/sock-buffer.html"/>
<link rel="stylesheet" type="text/css" href="/static/base.css"/>
<title>Buffering the Sock Stream - Comfortably Numbered</title>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<meta charset="utf-8"/>
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no" />
<link rel="alternate" type="application/rss+xml" title="Comfortably Numbered" href="/feed.xml" />
<!--
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script>
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$']]}
});
</script>
-->
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.css" integrity="sha384-Um5gpz1odJg5Z4HAmzPtgZKdTBHZdw8S29IecapCSB31ligYPhHQZMIlWLYQGVoc" crossorigin="anonymous">
<script defer src="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.js" integrity="sha384-YNHdsYkH6gMx9y3mRkmcJ2mFUjTd0qNQQvY9VYZgQd7DcN7env35GzlmFaZ23JGp" crossorigin="anonymous"></script>
<script defer src="https://cdn.jsdelivr.net/npm/[email protected]/dist/contrib/auto-render.min.js" integrity="sha384-vZTG03m+2yp6N6BNi5iM4rW4oIwk5DfcNdFfxkk9ZWpDriOkXX8voJBFrAO7MpVl" crossorigin="anonymous"></script>
<script>
document.addEventListener("DOMContentLoaded", function() {
renderMathInElement(document.body, {
// customised options
// • auto-render specific keys, e.g.:
delimiters: [
{left: '$$', right: '$$', display: true},
{left: '$', right: '$', display: false},
{left: '\\begin{align}', right: '\\end{align}', display: true},
{left: '\\(', right: '\\)', display: false},
{left: '\\[', right: '\\]', display: true}
],
// • rendering keys, e.g.:
throwOnError : false
});
});
</script>
</head>
<body>
<header id="header">
<script src="static/main.js"></script>
<div>
<a href="/"><span class="left-word">Comfortably</span> <span class="right-word">Numbered</span></a>
</div>
</header>
<article id="postcontent" class="centered">
<section>
<h1>Buffering the Sock Stream</h1>
<center><em><p>How much space do I need to do my laundry?</p>
</em></center>
<h4>Saturday, April 13, 2019 · 2 min read</h4>
<p>It’s the end of week 4 of the quarter and you’ve decided it’s finally time to
do some laundry. You somehow transport the massive mound of clothing in your
closet to the laundry room, occupy all three machines and also the dishwasher,
and finally transport the now-slightly-less-smelly mound of clothing back up
the stairs to your room. Then you turn on your favorite Pink Floyd album and
begin folding…</p>
<p>You pull out items of clothing from the heap one by one. Shirts and pants you
can fold immediately, but socks pose some difficulty: you can’t put them away
until they have been paired. So you put them aside on your bedside table to be
processed later. Soon, however, the pile of socks on your bedside table grows
too large, and the table can only fit so much sock on it.</p>
<p>So you decide to try and manage the situation by eagerly pairing up socks. If
you pull a sock out of the heap of clothes and see its partner on the bedside
table, you pair them up and put them away. Otherwise, you put the unpaired sock
on the bedside table.</p>
<p>Suppose you own an infinite number of socks, each of which is uniformly one of
$ k $ colors. How big does your bedside table need to be? Let’s call the pile
of clean clothes the “stream,” and the bedside table the “buffer.” Then the
question is, what is the distribution of the buffer size over time as a
function of $ k $?</p>
<p>Here is one way to think about this: if $ k = 1 $ then the buffer size is 0
half the time and 1 half the time; the distribution is normal at mean 0.5 and
variance 0.25. For larger $ k $, we can think of this as just a superposition
of multiple buffers, one for each $ k $. The means and variances add, so we
expect the distribution to be normal with mean $ k/2 $ and standard deviation
$ \sqrt{k}/2 $.</p>
<p>Here is another way to think about this: we have a Markov process where the
transition from state $ i $ to $ i + 1 $ is with probability $ (k - i)/k
$ and to $ i - 1 $ is with probability $ i/k $ for $ 0 \leq i \leq k $.
We can create a matrix representing this transition system; then, eigenvectors
of this matrix (with eigenvalue 1, and normalized to sum 1) represent
equilibrium probability distributions.</p>
<p>So, incredibly, we’ve shown that the coordinates of the $ \lambda=1 $
eigenvector for this matrix can be computed using the normal CDF. What a
fascinating correspondence!</p>
<p>If you don’t believe it, the graph below shows the normal-CDF predictions
(orange line) and the elements of the eigenvector (blue dots) for $ k = 100
$. The IPython notebook that generated this graph is
<a href="static/sock-graph.ipynb">here</a>.</p>
<p><img src="static/sock-graph.png" alt="sock graph"></p>
</section>
<div id="comment-breaker">◊ ◊ ◊</div>
</article>
<footer id="footer">
<div>
<ul>
<li><a href="https://github.com/kach">
Github</a></li>
<li><a href="feed.xml">
Subscribe (RSS feed)</a></li>
<li><a href="https://twitter.com/hardmath123">
Twitter</a></li>
<li><a href="https://creativecommons.org/licenses/by-nc/3.0/deed.en_US">
CC BY-NC 3.0</a></li>
</ul>
</div>
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-46120535-1', 'hardmath123.github.io');
ga('require', 'displayfeatures');
ga('send', 'pageview');
</script>
</footer>
</body>
</html>