-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathequally_many_heads_and_tails.html
290 lines (284 loc) · 14 KB
/
equally_many_heads_and_tails.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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
<html><head><title>niplav</title>
<link href="./favicon.png" rel="shortcut icon" type="image/png"/>
<link href="main.css" rel="stylesheet" type="text/css"/>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type"/>
<!DOCTYPE HTML>
<style type="text/css">
code.has-jax {font: inherit; font-size: 100%; background: inherit; border: inherit;}
</style>
<script async="" src="./mathjax/latest.js?config=TeX-MML-AM_CHTML" type="text/javascript">
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
extensions: ["tex2jax.js"],
jax: ["input/TeX", "output/HTML-CSS"],
tex2jax: {
inlineMath: [ ['$','$'], ["\\(","\\)"] ],
displayMath: [ ['$$','$$'], ["\\[","\\]"] ],
processEscapes: true,
skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
},
"HTML-CSS": { availableFonts: ["TeX"] }
});
</script>
<script>
document.addEventListener('DOMContentLoaded', function () {
// Change the title to the h1 header
var title = document.querySelector('h1')
if(title) {
var title_elem = document.querySelector('title')
title_elem.textContent=title.textContent + " – niplav"
}
});
</script>
</head><body><h2 id="home"><a href="./index.html">home</a></h2>
<p><em>author: niplav, created: 2019-02-08, modified: 2024-06-27, language: english, status: maintenance, importance: 4, confidence: highly likely</em></p>
<blockquote>
<p><strong>Imagine getting up every morning and throwing a coin so often that
heads and tails have come up an equal amount of times. How often
would you throw the coin on average? Infinitely often, it turns out.
Code in <a href="http://t3x.org/klong/index.html">Klong</a>.</strong></p>
</blockquote><div class="toc"><div class="toc-title">Contents</div><ul><li><a href="#None">Finding $x_{i}$</a><ul></ul></li><li><a href="#None_1">Finding $p_{i}$</a><ul><li><a href="#Observing_Coin_Flips">Observing Coin Flips</a><ul></ul></li><li><a href="#Considerations_on_Coin_Flips">Considerations on Coin Flips</a><ul><li><a href="#None_2">Proof that $o_{n}=2 \cdot n \cdot f_{n}$</a><ul></ul></li></ul></li><li><a href="#None_3">Probability of Finishing at $2 \cdot n$ Steps</a><ul></ul></li></ul></li><li><a href="#Final_Formula_and_Final_Code">Final Formula and Final Code</a><ul></ul></li><li><a href="#Proof_of_Divergence">Proof of Divergence</a><ul><li><a href="#None_4">Proof that $r_n \ge \frac{1}{n}$</a><ul></ul></li></ul></li><li><a href="#Further_Considerations">Further Considerations</a><ul></ul></li><li><a href="#External_Links">External Links</a><ul></ul></li></ul></div>
<h1 id="Equally_Many_Heads_and_Tails"><a class="hanchor" href="#Equally_Many_Heads_and_Tails">Equally Many Heads and Tails</a></h1>
<p>This thought experiment can be modeled as a simple
<a href="https://en.wikipedia.org/wiki/Expected_value">expected value</a>
calculation in a countably infinite case:</p>
<div>
$$\mathbb{E}=\sum_{i=1}^{\infty} p_{i} \cdot x_{i}$$
</div>
<h2 id="None"><a class="hanchor" href="#None">Finding <code>$x_{i}$</code></a></h2>
<p>We know that flipping the coin definitely ends when for <code>$2 \cdot n$</code> coin flips,
we have gotten heads n times and tails n times as well. This gives us
<code>$x_{i}=2 \cdot i$</code>.</p>
<h2 id="None_1"><a class="hanchor" href="#None_1">Finding <code>$p_{i}$</code></a></h2>
<p>Finding out <code>$p_{i}$</code> is a bit harder. In order to find it, it is best to look
at the first iterations of the process.</p>
<h3 id="Observing_Coin_Flips"><a class="hanchor" href="#Observing_Coin_Flips">Observing Coin Flips</a></h3>
<p>After starting, we have flipped the coin 2 times, so the possible solutions are:</p>
<pre><code>H;H
H;T
T;H
T;T
</code></pre>
<p>We are done in two cases, H;T and T;H. p₁ therefore is
<code>$\frac{2}{4}=0.5$</code>. We then continue flipping the coin 2 more times,
starting with either H;H or T;T, with the following possible results:</p>
<pre><code>H;H;H;H
H;H;H;T
H;H;T;H
H;H;T;T
T;T;H;H
T;T;T;H
T;T;H;T
T;T;T;T
</code></pre>
<p>Of these, only two finish: H;H;T;T and T;T;H;H. So the chance of finishing
given 4 coin flips is <code>$\frac{2}{8}=0.25$</code>.</p>
<p>We continue flipping the coin with the non-finishing sequences, and our possible
results look like this:</p>
<pre><code>H;H;H;H;H;H
H;H;H;H;H;T
H;H;H;H;T;H
H;H;H;H;T;T
H;H;H;T;H;H
H;H;H;T;H;T
H;H;H;T;T;H
H;H;H;T;T;T
H;H;T;H;H;H
H;H;T;H;H;T
H;H;T;H;T;H
H;H;T;H;T;T
T;T;T;H;H;H
T;T;T;H;T;H
T;T;T;H;H;T
T;T;T;H;T;T
T;T;H;T;H;H
T;T;H;T;T;H
T;T;H;T;H;T
T;T;H;T;T;T
T;T;T;T;H;H
T;T;T;T;H;T
T;T;T;T;T;H
T;T;T;T;T;T
</code></pre>
<p>Here, the sequences <code>H;H;H;T;T;T, H;H;T;H;T;T, T;T;T;H;H;H,T;T;H;T;H;H</code>
finish, so given six coin flips, the chance of finishing is
<code>$\frac{4}{24}=0.1666666\dots$</code>.</p>
<p>Writing down the next step gets messy, but we have already observed
enough iterations to find a pattern in the sequences.</p>
<h3 id="Considerations_on_Coin_Flips"><a class="hanchor" href="#Considerations_on_Coin_Flips">Considerations on Coin Flips</a></h3>
<p>First of all, the number of finishing sequences given <code>$2 \cdot n$</code> coin flips
is the <a href="https://en.wikipedia.org/wiki/Catalan_number">Catalan number</a>
Cₙ. In this case, it describes the number of <a href="https://en.wikipedia.org/wiki/Dyck_word">Dyck
words</a> of the length <code>$2 \cdot n$</code>. To
quote Wikipedia:</p>
<blockquote>
<p>A Dyck word is a string consisting of n X's and n Y's such that no
initial segment of the string has more Y's than X's.</p>
</blockquote>
<p><em>— <a href="https://en.wikipedia.org/wiki/Wikipedia">Wikipedia</a>, <a href="https://en.wikipedia.org/wiki/Dyck_word">“Dyck word”</a>, 2019</em></p>
<p>This applies exactly to the given problem. A finishing sequence has
equally many heads and tails, but doesn't begin with a sequence of
equally many heads and tails. Cₙ is defined as <code>$\frac{1}{n+1} \cdot {2 \cdot n \choose n}$</code>.</p>
<p>Catalan numbers can be easily implemented using the <a href="https://en.wikipedia.org/wiki/Binomial_coefficient">binomial
coefficient</a>:</p>
<pre><code>fact::{:[0=x;1;*/1+!x]}
bincoeff::{[n k];n::x;k::y;fact(n)%(fact(k)*fact(n-k))}
catalan::{bincoeff(2*x;x)%x+1}
f::{2*catalan(x)}
</code></pre>
<p>We call the number of finishing steps given <code>$2\cdot n$</code> coin flips fₙ.</p>
<p>One can also see that the total number of possible sequences of coin flips
oₙ after <code>$2 \cdot n$</code> coin flips is <code>$4 \cdot (o_{n-1}-f_{n-1})$</code>, because
one appends <code>H;H</code> or <code>H;T</code> or <code>T;H</code> or <code>T;T</code> to the remaining number of
sequences. So let oₙ be</p>
<div>
$$o_{1}=4\\
o_{n}=4 \cdot (o_{n-1}-f_{n-1})$$
</div>
<p>One can implement <code>$o_{n}$</code> simply:</p>
<pre><code>o::{:[x=1;4;4*o(x-1)-f(x-1)]}
</code></pre>
<p>When one executes <code>o</code> and <code>f</code>, one notices something peculiar: it seems
that <code>$o_{n}=2 \cdot n \cdot f_{n}$</code>.</p>
<h4 id="None_2"><a class="hanchor" href="#None_2">Proof that <code>$o_{n}=2 \cdot n \cdot f_{n}$</code></a></h4>
<p>Induction basis:</p>
<div>
$$o_{1}=2 \cdot 1 \cdot f_{1}\\
4=2 \cdot 1 \cdot 2$$
</div>
<p>Induction assumption:</p>
<div>
$$o_{n}=2 \cdot n \cdot f_{n}$$
</div>
<p>Induction step:</p>
<div>
$$o_{n+1}=2 \cdot (n+1) \cdot f_{n+1}\\
2 \cdot (o_{n}-f_{n})=(n+1) \cdot f_{n+1}\\
2 \cdot (2 \cdot n \cdot f_{n}-f_{n})=(n+1) \cdot f_{n+1}\\
8 \cdot n \cdot C_{n}-4 \cdot C_{n}=(n+1) \cdot 2 \cdot C_{n+1}\\
C_{n} \cdot \frac{4 \cdot n-2}{n+1}=C_{n+1}$$
</div>
<p>This is equivalent to <a href="https://oeis.org/A000108">a recursive definition</a>
of the Catalan numbers in the OEIS (sixth formula).</p>
<!--TODO: This seems a tiny bit fishy: There is probably an offset here
(first value of the catalan numbers is not used, so the whole sequence
is shifted). Look at this.-->
<h3 id="None_3"><a class="hanchor" href="#None_3">Probability of Finishing at <code>$2 \cdot n$</code> Steps</a></h3>
<p>So, what's the probability of finishing given <code>2*n</code> steps now? Simple:
it's <code>$\frac{f_{n}}{o_{n}}=\frac{f_n}{2 \cdot n \cdot f_{n}}=\frac{1}{2 \cdot n}$</code>.</p>
<pre><code>pgn::{1%2*x}
</code></pre>
<p>Note that this probability is different from finishing at <code>2*n</code> steps:
<code>pgn</code> simply tells us how likely it is for us to finish in the next 2
flips if we have flipped the coin <code>2*(n-1)</code> times steps already. But we
are looking for the probability of finishing at <code>2*n</code> steps.</p>
<p>For this, we can now define <code>$r_{n}$</code> that tells us the probability
of arriving at a sequence with <code>2*n</code> coin flips. This can only have
happened if we arrived at the last step and did not finish there. We
define <code>$r_{n}$</code> recursively:</p>
<div>
$$r_{0}=1\\
r_{n}=r_{n-1}-\frac{1}{2 \cdot (n-1)} \cdot r_{n-1}$$
</div>
<p>Now, defining <code>$p_{n}$</code> is simple: <code>$p_{n}=\frac{1}{2 \cdot n} \cdot r_{n}$</code>.</p>
<h2 id="Final_Formula_and_Final_Code"><a class="hanchor" href="#Final_Formula_and_Final_Code">Final Formula and Final Code</a></h2>
<p>Our final formula for the expected value is thus</p>
<div>
$$\mathbb{E}=\sum_{i=1}^{\infty} \frac{1}{2 \cdot i} \cdot r_{i} \cdot 2 \cdot i$$
</div>
<p>We could implement <code>$r_{n}$</code> very easily:</p>
<pre><code>r::{r(x-1)-pgn(x-1)*r(x-1)}
</code></pre>
<p>But since we don't want to compute <code>$r_{n}$</code> every time we execute
a new iteration, we simply embed it into the final evaluation function:</p>
<pre><code>ev::{[px];px::pgn(x);.p(($x),",",($px*y),",",$z);.f(x+1;y-(y*px);z+2*x*y*px)}
</code></pre>
<p><code>x</code> is the number of flips, <code>y</code> is the probability of not finishing after
<code>x</code> steps, and <code>z</code> is the expected value. The function calculates the
probability of finishing at the current step, prints the current expected
value, and passes its updated arguments forward, subtracting <code>y*px</code> from
<code>y</code>.</p>
<p>We now call ev:</p>
<pre><code>ev(1;1;0)
</code></pre>
<p>Here is a sample output, piped through <code>tr , '\t'</code> to make it easier to read:</p>
<pre><code>1 0.5 0
2 0.125 1.0
3 0.0625000000000000001 1.5
4 0.0390624999999999998 1.875
...
99998 0.00000000892092166024425108 356.819024780555414
99999 0.00000000892078784508119576 356.820808929203776
100000 0.0000000089206540332635195 356.822593068931216
100001 0.00000000892052022479110523 356.824377199737868
</code></pre>
<p>The first field is the number of iterations, the second field is the
probability of finishing at the given iteration, and the third field
is the expected value at the given step.</p>
<h2 id="Proof_of_Divergence"><a class="hanchor" href="#Proof_of_Divergence">Proof of Divergence</a></h2>
<p>After watching the output of the code above for a while, one gets the
suspicion that the expected value diverges to infinity.</p>
<p>To prove this, let the <code>$\mathbb{E}_n$</code> for <code>$n \in \mathbb{N}$</code> be the
expected value if we finish throwing the coin after <code>2*n</code> steps:</p>
<div>
$$\mathbb{E}_n=\sum_{i=1}^{n} \frac{1}{2 \cdot i} \cdot r_{i} \cdot 2 \cdot i$$
</div>
<p>We now want to show that</p>
<div>
$$\lim_{n \to \infty} \mathbb{E_{n}}=\lim_{n \to \infty} \sum_{i=1}^{n} r_{i}=\infty$$
</div>
<p>We will show that <code>$r_{n} \ge \frac{1}{n}$</code>, and since we know the
<a href="https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)">harmonic series</a>
diverges, we can make a
<a href="https://en.wikipedia.org/wiki/Direct_comparison_test">direct comparison test</a>
and show that <code>$\sum_{i=1}^{n} r_{i}$</code> diverges as well.</p>
<p>Let <code>$r_{n}$</code> be</p>
<p><code>$r_{0}=1$</code><br/>
<code>$r_{n}=r_{n-1}-\frac{1}{2 \cdot (n-1)} \cdot r_{n-1}$</code></p>
<h4 id="None_4"><a class="hanchor" href="#None_4">Proof that <code>$r_n \ge \frac{1}{n}$</code></a></h4>
<p>Proof by induction.</p>
<p>Induction Basis:</p>
<div>
$$r_{0}=1 \ge 1=\frac{1}{1}$$
</div>
<p>Induction Assumption:</p>
<div>
$$r_n \ge \frac{1}{n}$$
</div>
<p>Induction Step:</p>
<div>
$$r_{n+1} \ge \frac{1}{n+1}\\
r_{n}-\frac{1}{2 \cdot n} \cdot r_{n} \ge \frac{1}{n+1}\\
r_{n} \cdot (1-\frac{1}{2 \cdot n}) \ge \frac{1}{n+1}\\
r_{n} \ge \frac{1}{(n+1) \cdot (1-\frac{1}{2 \cdot n})}\\
r_{n} \ge \frac{1}{n+\frac{1}{2}-\frac{1}{2 \cdot n}}$$
</div>
<p>Inserting the assumption:</p>
<div>
$$r_{n} \ge \frac{1}{n} \ge \frac{1}{n+\frac{1}{2}-\frac{1}{2 \cdot n}}\\
n+\frac{1}{2}-\frac{1}{2 \cdot n} \ge n\\
\frac{1}{2} \ge \frac{1}{2 \cdot n}\\
n \ge 1$$
</div>
<p>Since <code>$n \in \mathbb{N}$</code>, we have therefore proven that</p>
<div>
$$\lim_{n \to \infty} \sum_{i=1}^{n} \frac{1}{i}=\infty \le \lim_{n \to \infty} \sum_{i=1}^{n} r_{i}=\infty$$
</div>
<h2 id="Further_Considerations"><a class="hanchor" href="#Further_Considerations">Further Considerations</a></h2>
<p>This model can be generalized to the average length of a random walk
with steps with length 1 in <code>$\mathbb{Z}$</code> starting at 0 and ending at 0.</p>
<p>The question poses itself whether the found length would still hold in
<code>$\mathbb{Z}^n$</code> (<code>$n \ge 2$</code>) for steps of size 1. It <em>seems</em> obvious
that this should be the case, but one shouldn't be too sure of it.</p>
<h2 id="External_Links"><a class="hanchor" href="#External_Links">External Links</a></h2>
<ul>
<li><a href="https://www.askamathematician.com/2014/01/q-if-you-flip-a-coin-forever-are-you-guaranteed-to-eventually-flip-an-equal-number-of-heads-and-tails/">“Q: If you flip a coin forever, are you guaranteed to eventually flip an equal number of heads and tails?”</a></li>
<li>By Neil Webber:
<ul>
<li><a href="http://neilwebber.com/notes/2018/10/29/flipping-a-coin-until-reaching-equal-heads-and-tails/">“Flipping a coin until reaching equal heads and tails”</a></li>
<li><a href="http://neilwebber.com/notes/2018/11/18/coin-flips-and-catalan-numbers/">“Coin flips and Catalan Numbers”</a></li>
<li><a href="http://neilwebber.com/notes/2018/12/26/coin-flip-simulation-still-running-62-days/">“Coin flip simulation still running – 62 days!”</a><!--TODO: is the en dash in the original title?--></li>
</ul></li>
</ul>
</body></html>