<?xml version="1.0" encoding="UTF-8"?>
<rss version="2.0" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" xmlns:media="http://search.yahoo.com/mrss/">
<channel>
<title><![CDATA[Lindy Effect - Rafael Quintanilha]]></title>
<description><![CDATA[Essays about software engineering, web development, artificial intelligence, quantitative analysis, financial markets, books and tradition.]]></description>
<link>https://rafaelquintanilha.com/topic/lindy-effect/</link>
<image><url>https://rafaelquintanilha.com/content/images/2022/12/Logo-Design--2-.png</url><title>Lindy Effect - Rafael Quintanilha</title><link>https://rafaelquintanilha.com/topic/lindy-effect/</link></image>
<lastBuildDate>Mon, 14 Oct 2024 22:42:44 GMT</lastBuildDate>
<atom:link href="https://rafaelquintanilha.com/topic/lindy-effect/rss/" rel="self" type="application/rss+xml"/>
<ttl>60</ttl>
<item>
<title><![CDATA[The Drunken Sailor and The Lindy Effect]]></title>
<description><![CDATA[Understand the Lindy Effect mathematically by applying it to the well-known Drunken Sailor problem.]]></description>
<link>https://rafaelquintanilha.com/ensaios/the-drunken-sailor-and-the-lindy-effect/</link>
<guid isPermaLink="false">638bcd8f24336d003d59fc0d</guid>
<category><![CDATA[Lindy Effect]]></category><category><![CDATA[Math]]></category>
<dc:creator><![CDATA[Rafael Quintanilha]]></dc:creator>
<pubDate>Wed, 27 Mar 2019 03:00:00 GMT</pubDate>

<content:encoded><![CDATA[<p>I was scrolling through my Twitter feed on a boring Saturday afternoon when I stumbled upon this tweet:</p>
<figure class="embed embed-twitter" data-url="https://twitter.com/bilayerguy/status/1098926919402311680">
<blockquote class="twitter-tweet"><p lang="en" dir="ltr">Dear <a href="https://twitter.com/nntaleb" rel="noopener noreferrer" target="_blank">@nntaleb</a> , will you post this puzzle in memory of <a href="https://twitter.com/CutTheKnotMath" rel="noopener noreferrer" target="_blank">@CutTheKnotMath</a>? I had it in an exam 21 years ago and still do not know the solution. I am sure your followers or you will do it and I will learn something useful. Thank you! <a href="https://t.co/e9HXQZwo9K" rel="noopener noreferrer" target="_blank">pic.twitter.com/e9HXQZwo9K</a></p>— Adrian Mureșan (@bilayerguy) <a href="https://twitter.com/bilayerguy/status/1098926919402311680" rel="noopener noreferrer" target="_blank">February 22, 2019</a></blockquote>
</figure>
<p>I was immediately thrilled - finally something interesting to do!</p>
<p>Here’s the problem in full:</p>
<blockquote>
<p>A drunken sailor stands near the edge of an abyss and takes random steps either towards or away from the edge. A step towards the edge has a probability of p<em>p</em> and a step away from the edge has a probability of (1 - p)(1−<em>p</em>). If the sailor starts n<em>n</em> steps from the edge, what is his chance of survival? What is the minimum value of p<em>p</em> for which there is no chance of survival?</p>
</blockquote>
<p>Turns out the solution for this problem is not beautiful only mathematically, but also provides great insights into our daily life.</p>
<p>Let’s solve it first.</p>
<h2 id="solving-computationally"><strong>Solving Computationally</strong></h2>
<p>Before jumping into the maths, let’s try to get some intuition from code. Here’s a simple simulator for our problem:</p>
<iframe src="https://codesandbox.io/embed/angry-jerry-q3w4l9?fontsize=14&#x26;hidenavigation=1&#x26;theme=dark" style="width:100%; height:500px; border:0; border-radius: 4px; overflow:hidden;" title="drunken-sailor" allow="accelerometer; ambient-light-sensor; camera; encrypted-media; geolocation; gyroscope; hid; microphone; midi; payment; usb; vr; xr-spatial-tracking" sandbox="allow-forms allow-modals allow-popups allow-presentation allow-same-origin allow-scripts" loading="lazy"></iframe>
<p>The complete code is on <a href="https://codesandbox.io/s/drunken-sailor-q3w4l9" rel="noopener noreferrer" target="_blank">CodeSandbox</a> but the algorithm is pretty straightforward.</p>
<figure class="code"><figcaption>jsx</figcaption><pre class="astro-code linha" style="background-color:#1b1814;color:#ecebe8; overflow-x: auto;" tabindex="0" data-language="jsx"><code><span class="line"><span style="color:#A1C1E4">const</span><span style="color:#ECEBE8"> MAX_ITERATIONS </span><span style="color:#A1C1E4">=</span><span style="color:#97CCAE"> 10000</span><span style="color:#ECEBE8">;</span></span>
<span class="line"></span>
<span class="line"><span style="color:#A1C1E4">const</span><span style="color:#EDCC95"> updatePosition</span><span style="color:#A1C1E4"> =</span><span style="color:#ECEBE8"> (currentPosition, p) </span><span style="color:#A1C1E4">=></span><span style="color:#ECEBE8"> {</span></span>
<span class="line"><span style="color:#A1C1E4">  const</span><span style="color:#ECEBE8"> randomVariable </span><span style="color:#A1C1E4">=</span><span style="color:#EDCC95"> Math.random</span><span style="color:#ECEBE8">();</span></span>
<span class="line"><span style="color:#A1C1E4">  if</span><span style="color:#ECEBE8"> ( randomVariable </span><span style="color:#A1C1E4">&#x3C;</span><span style="color:#ECEBE8"> p ) </span><span style="color:#A1C1E4">return</span><span style="color:#ECEBE8"> currentPosition </span><span style="color:#A1C1E4">-</span><span style="color:#97CCAE"> 1</span><span style="color:#ECEBE8">;</span></span>
<span class="line"><span style="color:#A1C1E4">  else</span><span style="color:#A1C1E4"> return</span><span style="color:#ECEBE8"> currentPosition </span><span style="color:#A1C1E4">+</span><span style="color:#97CCAE"> 1</span><span style="color:#ECEBE8">;</span></span>
<span class="line"><span style="color:#ECEBE8">}</span></span>
<span class="line"></span>
<span class="line"><span style="color:#A1C1E4">const</span><span style="color:#EDCC95"> simulation</span><span style="color:#A1C1E4"> =</span><span style="color:#ECEBE8"> (initialPosition, p) </span><span style="color:#A1C1E4">=></span><span style="color:#ECEBE8"> {</span></span>
<span class="line"><span style="color:#A1C1E4">  let</span><span style="color:#ECEBE8"> iterations </span><span style="color:#A1C1E4">=</span><span style="color:#97CCAE"> 0</span><span style="color:#ECEBE8">;</span></span>
<span class="line"><span style="color:#A1C1E4">  let</span><span style="color:#ECEBE8"> currentPosition </span><span style="color:#A1C1E4">=</span><span style="color:#ECEBE8"> initialPosition;</span></span>
<span class="line"><span style="color:#A1C1E4">  while</span><span style="color:#ECEBE8"> ( currentPosition </span><span style="color:#A1C1E4">></span><span style="color:#97CCAE"> 0</span><span style="color:#A1C1E4"> &#x26;&#x26;</span><span style="color:#ECEBE8"> iterations </span><span style="color:#A1C1E4">&#x3C;=</span><span style="color:#ECEBE8"> MAX_ITERATIONS ) {</span></span>
<span class="line"><span style="color:#ECEBE8">    currentPosition </span><span style="color:#A1C1E4">=</span><span style="color:#EDCC95"> updatePosition</span><span style="color:#ECEBE8">(currentPosition, p);</span></span>
<span class="line"><span style="color:#ECEBE8">    iterations</span><span style="color:#A1C1E4">++</span><span style="color:#ECEBE8">;</span></span>
<span class="line"><span style="color:#ECEBE8">  }</span></span>
<span class="line"><span style="color:#A1C1E4">  return</span><span style="color:#ECEBE8"> [currentPosition, iterations];</span></span>
<span class="line"><span style="color:#ECEBE8">}</span></span></code></pre></figure>
<p>The trick is to think of the sailor’s position as a point in the x-axis. We update the position until he dies (<code>currentPosition === 0</code>) or the maximum number of iterations is reached. In every round, we compare a random variable between 0 and 1 (yielded by <code>Math.random</code>) with p<em>p</em> and move the sailor left or right accordingly.</p>
<p>I encourage you to play a little bit with the simulator and check how’s your intuition going. In any case, here’s a table with the % of deaths for some combinations of <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span></span> and <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>p</mi></mrow><annotation encoding="application/x-tex">p</annotation></semantics></math></span></span>:</p>
<table>
<thead>
<tr>
<th>p</th>
<th>Deaths (n = 5n=5) (%)</th>
<th>Deaths (n = 15n=15) (%)</th>
<th>Deaths (n = 50n=50) (%)</th>
</tr>
</thead>
<tbody>
<tr>
<td>0.1</td>
<td>0</td>
<td>0</td>
<td>0</td>
</tr>
<tr>
<td>0.2</td>
<td>0</td>
<td>0</td>
<td>0</td>
</tr>
<tr>
<td>0.3</td>
<td>1.7</td>
<td>0</td>
<td>0</td>
</tr>
<tr>
<td>0.4</td>
<td>13.2</td>
<td>0.3</td>
<td>0</td>
</tr>
<tr>
<td>0.5</td>
<td>96.1</td>
<td>86.8</td>
<td>61.8</td>
</tr>
<tr>
<td>0.6</td>
<td>100</td>
<td>100</td>
<td>100</td>
</tr>
<tr>
<td>0.7</td>
<td>100</td>
<td>100</td>
<td>100</td>
</tr>
<tr>
<td>0.8</td>
<td>100</td>
<td>100</td>
<td>100</td>
</tr>
<tr>
<td>0.9</td>
<td>100</td>
<td>100</td>
<td>100</td>
</tr>
</tbody>
</table>
<p>As one could imagine, the % of deaths increases with <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>p</mi></mrow><annotation encoding="application/x-tex">p</annotation></semantics></math></span></span> and somehow decreases with <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span></span>… but only for values around <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>0.50</mn></mrow><annotation encoding="application/x-tex">0.50</annotation></semantics></math></span></span>. It seems that the fate of our beloved sailor is settled for <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>p</mi><mo>></mo><mn>0.5</mn></mrow><annotation encoding="application/x-tex">p > 0.5</annotation></semantics></math></span></span> and therefore this should be the answer to the second question of the problem.</p>
<p>Let us now find the exact probability of survival.</p>
<h2 id="solving-mathematically"><strong>Solving Mathematically</strong></h2>
<p>There are many solutions for this problem but the one I liked most was written in <a href="https://medium.com/i-math/the-drunkards-walk-explained-48a0205d304" rel="noopener noreferrer" target="_blank">this post by Brett Berry</a>. Here’s a summary:</p>
<p>Recall that in order to solve through code we abstracted the sailor’s position into a point in the x-axis. Let <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>P</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">P(n)</annotation></semantics></math></span></span> be the probability that the sailor dies when <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span></span> steps away from the edge.</p>
<figure class="image"><img alt="Credits: Brett Berry" loading="lazy" decoding="async" width="609" height="219" src="https://rafaelquintanilha.com/_astro/drunken-sailor.CNWIupFz_1ENKr0.webp"><figcaption>Credits: Brett Berry</figcaption></figure>
<p>Then:</p>
<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>P</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo><mo>=</mo><mi>p</mi><mo>+</mo><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mi>p</mi><mo stretchy="false">)</mo><mi>P</mi><mo stretchy="false">(</mo><mn>2</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">P(1)=p+(1−p)P(2)</annotation></semantics></math></span></span></span>
<p>The sailor surely dies if he goes to the left (with probability <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>p</mi></mrow><annotation encoding="application/x-tex">p</annotation></semantics></math></span></span>). But if he manages to move right, we now have him in <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mo>=</mo><mn>2</mn></mrow><annotation encoding="application/x-tex">n = 2</annotation></semantics></math></span></span> and therefore the probability that he dies is what we call <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>P</mi><mo stretchy="false">(</mo><mn>2</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">P(2)</annotation></semantics></math></span></span>.</p>
<p>Well, in order to die he <strong>necessarily</strong> needs to move to the left (i.e. go from <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mo>=</mo><mn>2</mn></mrow><annotation encoding="application/x-tex">n = 2</annotation></semantics></math></span></span> to <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">n = 1</annotation></semantics></math></span></span>). But what is <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>P</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">P(1)</annotation></semantics></math></span></span> if not the probability that the sailor moves one unit left? Therefore, <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>P</mi><mo stretchy="false">(</mo><mn>2</mn><mo stretchy="false">)</mo><mo>=</mo><mi>P</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">P(2) = P(1)</annotation></semantics></math></span></span> <em>times the probability of going from</em> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">n = 1</annotation></semantics></math></span></span> to <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><annotation encoding="application/x-tex">n = 0</annotation></semantics></math></span></span>, or, <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>P</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">P(1)</annotation></semantics></math></span></span>.</p>
<p>Hence:</p>
<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>P</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo><mo>=</mo><mi>p</mi><mo>+</mo><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mi>p</mi><mo stretchy="false">)</mo><mi>P</mi><mo stretchy="false">(</mo><mn>1</mn><msup><mo stretchy="false">)</mo><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">P(1) = p + (1−p)P(1)^2</annotation></semantics></math></span></span></span>
<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mi>p</mi><mo stretchy="false">)</mo><mi>P</mi><mo stretchy="false">(</mo><mn>1</mn><msup><mo stretchy="false">)</mo><mn>2</mn></msup><mo>−</mo><mi>P</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo><mo>+</mo><mi>p</mi><mo>=</mo><mn>0</mn></mrow><annotation encoding="application/x-tex">(1 - p) P(1)^2 - P(1) + p = 0</annotation></semantics></math></span></span></span>
<p>Which yields <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>P</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo><mo>=</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">P(1) = 1</annotation></semantics></math></span></span> or <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>P</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo><mo>=</mo><mfrac><mi>p</mi><mrow><mn>1</mn><mo>−</mo><mi>p</mi></mrow></mfrac></mrow><annotation encoding="application/x-tex">P(1) = \frac{p}{1 - p}</annotation></semantics></math></span></span>.
Now, notice that <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>P</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">P(1)</annotation></semantics></math></span></span> is a probability and therefore must be in the <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">[</mo><mn>0</mn><mo separator="true">,</mo><mn>1</mn><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">[0, 1]</annotation></semantics></math></span></span> range. Follows that <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mfrac><mi>p</mi><mrow><mn>1</mn><mo>−</mo><mi>p</mi></mrow></mfrac><mo>≤</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">\frac{p}{1 - p} \leq 1</annotation></semantics></math></span></span> and then <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>p</mi><mo>≤</mo><mfrac><mn>1</mn><mn>2</mn></mfrac></mrow><annotation encoding="application/x-tex">p \leq \frac{1}{2}</annotation></semantics></math></span></span>.</p>
<p>Finally, we can write:</p>
<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>P</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo><mo>=</mo><mrow><mo fence="true">{</mo><mtable rowspacing="0.36em" columnalign="left left" columnspacing="1em"><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>1</mn></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mtext>if </mtext><mi>p</mi><mo>></mo><mfrac><mn>1</mn><mn>2</mn></mfrac></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mfrac><mi>p</mi><mrow><mn>1</mn><mo>−</mo><mi>p</mi></mrow></mfrac></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mtext>if </mtext><mi>p</mi><mo>≤</mo><mfrac><mn>1</mn><mn>2</mn></mfrac></mrow></mstyle></mtd></mtr></mtable></mrow></mrow><annotation encoding="application/x-tex">P(1) = \begin{cases} 1 &#x26;\text{if } p \gt \frac{1}{2} \\ \frac{p}{1 - p} &#x26;\text{if } p \leq \frac{1}{2} \end{cases}</annotation></semantics></math></span></span></span>
<p>Once <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>P</mi><mo stretchy="false">(</mo><mn>2</mn><mo stretchy="false">)</mo><mo>=</mo><mi>P</mi><mo stretchy="false">(</mo><mn>1</mn><msup><mo stretchy="false">)</mo><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">P(2) = P(1)^2</annotation></semantics></math></span></span>, it follows that:</p>
<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>P</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>=</mo><mrow><mo fence="true">{</mo><mtable rowspacing="0.36em" columnalign="left left" columnspacing="1em"><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>1</mn></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mtext>if </mtext><mi>p</mi><mo>></mo><mfrac><mn>1</mn><mn>2</mn></mfrac></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mo stretchy="false">(</mo><mfrac><mi>p</mi><mrow><mn>1</mn><mo>−</mo><mi>p</mi></mrow></mfrac><msup><mo stretchy="false">)</mo><mi>n</mi></msup></mrow></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mtext>if </mtext><mi>p</mi><mo>≤</mo><mfrac><mn>1</mn><mn>2</mn></mfrac></mrow></mstyle></mtd></mtr></mtable></mrow></mrow><annotation encoding="application/x-tex">P(n) = \begin{cases} 1 &#x26;\text{if } p \gt \frac{1}{2} \\ (\frac{p}{1 - p})^n &#x26;\text{if } p \leq \frac{1}{2} \end{cases}</annotation></semantics></math></span></span></span>
<p>By the same reasoning presented above, <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>P</mi><mo stretchy="false">(</mo><mn>3</mn><mo stretchy="false">)</mo><mo>=</mo><mi>P</mi><mo stretchy="false">(</mo><mn>1</mn><msup><mo stretchy="false">)</mo><mn>3</mn></msup></mrow><annotation encoding="application/x-tex">P(3) = P(1)^3</annotation></semantics></math></span></span>. It follows that, for a given <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span></span>:</p>
<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>P</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>=</mo><mrow><mo fence="true">{</mo><mtable rowspacing="0.36em" columnalign="left left" columnspacing="1em"><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>1</mn></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mtext>if </mtext><mi>p</mi><mo>></mo><mfrac><mn>1</mn><mn>2</mn></mfrac></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mo stretchy="false">(</mo><mfrac><mi>p</mi><mrow><mn>1</mn><mo>−</mo><mi>p</mi></mrow></mfrac><msup><mo stretchy="false">)</mo><mi>n</mi></msup></mrow></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mtext>if </mtext><mi>p</mi><mo>≤</mo><mfrac><mn>1</mn><mn>2</mn></mfrac></mrow></mstyle></mtd></mtr></mtable></mrow></mrow><annotation encoding="application/x-tex">P(n) = \begin{cases} 1 &#x26;\text{if } p \gt \frac{1}{2} \\ (\frac{p}{1 - p})^n &#x26;\text{if } p \leq \frac{1}{2} \end{cases}</annotation></semantics></math></span></span></span>
<p>Which completes our answer and matches the results found in the simulations.</p>
<h2 id="intepreting-the-result"><strong>Intepreting the Result</strong></h2>
<p>The answer to this problem is quite interesting because it reveals a big asymmetry: for any value <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>p</mi><mo>></mo><mfrac><mn>1</mn><mn>2</mn></mfrac></mrow><annotation encoding="application/x-tex">p > \frac{1}{2}</annotation></semantics></math></span></span>, the sailor will eventually die. Certainly, for any number sufficiently big of iterations (we are using a relatively small number of 10000 iterations per simulation), the sailor dies anyway. <em>But real life often has an upper limit</em> and therefore I'm not interested in <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mo>→</mo><mi mathvariant="normal">∞</mi></mrow><annotation encoding="application/x-tex">n \to \infty</annotation></semantics></math></span></span>.</p>
<p>But once life is finite and the sailor can't take random steps forever, how resilient he is? In other words, <strong>what's the probability of survival given that the sailor has been surviving for a while?</strong></p>
<h2 id="the-lindy-effect"><strong>The Lindy Effect</strong></h2>
<p>The Lindy Effect is a theory for our very intuition. From <a href="https://en.wikipedia.org/wiki/Lindy_effect" rel="noopener noreferrer" target="_blank">Wikipedia</a>:</p>
<blockquote>
<p>The Lindy effect is a theory that the future life expectancy of some non-perishable things like a technology or an idea is proportional to their current age, so that every additional period of survival implies a longer remaining life expectancy.</p>
</blockquote>
<p>In simple words, the longer <em>something</em> lives, the longer it is expected to live. We are used to perceive this as the “test of time”. If you give enough time for an idea to be tested and it survives (i.e. people keep adopting it), chances are it will survive for a while.</p>
<p>How does this apply to the Drunken Sailor problem?</p>
<p>Let us try to observe the outcome of his random walk after an arbitrary number of rounds (iterations). For example, given that the sailor survived 100 rounds, how many times does he end up alive? And for 1000? 5000?</p>
<p>Consider the following table for <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>p</mi><mo>=</mo><mn>0.5</mn></mrow><annotation encoding="application/x-tex">p = 0.5</annotation></semantics></math></span></span>, <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mo>=</mo><mn>10</mn></mrow><annotation encoding="application/x-tex">n = 10</annotation></semantics></math></span></span> and <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>10</mn><mo separator="true">,</mo><mn>000</mn></mrow><annotation encoding="application/x-tex">10,000</annotation></semantics></math></span></span> simulations, where <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math></span></span> is the min number of iterations for a surviving sailor:</p>
<table>
<thead>
<tr>
<th>ii</th>
<th>Survived at this point</th>
<th>Died in the end</th>
<th>Survival rate (%)</th>
</tr>
</thead>
<tbody>
<tr>
<td>10</td>
<td>10,000</td>
<td>9,230</td>
<td>7.70</td>
</tr>
<tr>
<td>100</td>
<td>6,793</td>
<td>6,023</td>
<td>11.34</td>
</tr>
<tr>
<td>1000</td>
<td>2,527</td>
<td>1,757</td>
<td>30.47</td>
</tr>
<tr>
<td>5000</td>
<td>1,129</td>
<td>359</td>
<td>68.20</td>
</tr>
</tbody>
</table>
<p>The table is very informative -- if a sailor manages to survive until the 1000th iteration (which is only <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mfrac><mn>1</mn><mn>10</mn></mfrac></mrow><annotation encoding="application/x-tex">\frac{1}{10}</annotation></semantics></math></span></span> of the number of rounds), <em>he increases his chance of survival by a factor of 4</em>. If he survives until half of the iterations, <em>his survival rate increases 800%!</em></p>
<p>The sailor is, therefore, Lindy. The longer he lives, the longer he is expected to live.</p>
<h2 id="wrapping-up"><strong>Wrapping Up</strong></h2>
<p>The Drunken Sailor Problem and the Lindy Effect help us understand the <em>test of time.</em></p>
<p>Lindy enhances <em>evolution</em>. What survives tend to have offsprings that are alike. Things that change very quickly don’t allow evolution to do its job.</p>
<p><strong>That doesn't mean that we should wait forever</strong> -- recall that even dying <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mfrac><mn>1</mn><mn>3</mn></mfrac></mrow><annotation encoding="application/x-tex">\frac{1}{3}</annotation></semantics></math></span></span> less when they hit the 5,000 mark compared to when they start to walk, <em>31% of the sailors still die</em>. But we should be respectful of things that have survived for a considerable amount of time.</p>
<p>For what is new might be fragile for events that are hard to anticipate. And drunken sailors might avoid falling off a cliff.</p>]]></content:encoded>
</item>
</channel>
</rss>
