43-Solution.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- A bar is broken at two random places\n",
    "- *Find the average size of the smallest, middle, and largest piece*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "___\n",
    "\n",
    "# Smallest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- We can think of our bar as a line from 0 to 1\n",
    "- There will be two break points on the bar\n",
    "    - Let $X_{1}$ be the smaller break point i.e. closest to 0\n",
    "    - Let $X_{2}$ be the larger break point"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/43-1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Let's work through some possible values of $X_{1}$ and see how the smallest piece is affected by $X_{2}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "___\n",
    "\n",
    "**Example 1: $X_{1} = 0.1$**\n",
    "\n",
    "- Then, we know that $X_{2}$ must be greater than 0.1\n",
    "- Let's say $X_{2} = 0.15$\n",
    "    - Then, the first piece has length 0.1, the second piece has length 0.15 - 0.1 = 0.05, and the third piece has length 1 - 0.15 = 0.85\n",
    "        - This means that the second piece is the smallest\n",
    "        \n",
    "- Now, let's try $X_{2} = 0.25$\n",
    "    - First piece: 0.1\n",
    "    - Second piece: 0.25 - 0.1 = 0.15\n",
    "    - Third piece: 1 - 0.25 = 0.75\n",
    "        - This means the second piece is the smallest\n",
    "        \n",
    "- Finally, let's try $X_{2} = 0.95$\n",
    "    - First piece = 0.1\n",
    "    - Second piece = 0.95 - 0.1 = 0.85\n",
    "    - Third piece = 1 - 0.95 = 0.05\n",
    "        - This means the third piece is the smallest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- As we can see from this test case, we can split the possible $X_{2}$ values into three zones\n",
    "    1. If $X_{2} < 0.2 \\implies$ the second piece is the smallest with length $X_{2} - X_{1}$\n",
    "    2. If $0.2 \\leq X_{2} \\leq 0.9 \\implies$ the first piece is the smallest with length $X_{1}$\n",
    "    3. If $0.9 < X_{2} \\implies $ the third piece is the smallest with length $1-X_{2}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- If we define $S$ to be the length of the smallest piece, then:\n",
    "\n",
    "$$\n",
    "S = \\left\\{\\begin{matrix}X_{2}-X_{1} & \\text{if }X_{1}\\leq X_{2}\\leq 2X_{1}\\\\ X_{1} & 2X_{1} < X_{2} < 1-X_{1}\\\\ 1-X_{2} & 1-X_{1}\\leq X_{2}\\end{matrix}\\right.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "___\n",
    "\n",
    "**Example 2: $X_{1} = 0.45$**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Let's try splitting this into zones again\n",
    "    1. If $X_{2} < 0.725 \\implies$ the second piece is the smallest with length $X_{2} - X_{1}$\n",
    "    2. If $0.725 < X_{2} \\implies $ the third piece is the smallest with length $1-X_{2}$\n",
    "    \n",
    "- **We can see that in this case, it's not possible that the first piece is the smallest since on of the third piece or the second piece will be smaller than 0.45**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- So, in this case:\n",
    "\n",
    "$$\n",
    "S = \\left\\{\\begin{matrix}X_{2}-X_{1} & \\text{if }X_{2}\\leq \\frac{1+X_{1}}{2}\\\\ 1-X_{2} & \\frac{1+X_{1}}{2}\\leq X_{2}\\end{matrix}\\right.\n",
    "$$\n",
    "\n",
    "___"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- So now, if we think about it, if $X_{1}>1/3$, it's impossible for the smallest piece to be the first piece\n",
    "    - If $X_{1}$ is equal to say 0.35, then there's 0.65 remaining to be split between the other two pieces\n",
    "        - The smaller of the two pieces will always be less than 0.35"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "____\n",
    "\n",
    "**Quick aside about the density function**\n",
    "\n",
    "- In the standard case, we know that for the uniform distribution over the region [0,1], the cdf is given by:\n",
    "\n",
    "$$\n",
    "P(X \\leq x) = \\frac{x}{1} = x\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- This implies that the pdf is given by:\n",
    "\n",
    "$$\n",
    "f(x) = \\frac{d}{dx}x = 1\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- But since $X_{1}$ is the minimum of the two break points, it's not so simple\n",
    "    - If we label our break points as $B_{1}$ and $B_{2}$, then $X_{1} = min(B_{1},B_{2})$\n",
    "        - Therefore, $X_{1} \\leq x \\implies B_{1} \\leq x \\cup B_{2}\\leq x$\n",
    "\n",
    "- This means:\n",
    "\n",
    "$$\n",
    "P(X_{1} \\leq x) = P(B_{1} \\leq x \\cup B_{2} \\leq x) = 1 - P(B_{1} > x \\cap B_{2} > x)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "= 1 - P(X > x)^{2} = 1 - (1-x)^{2} = 1 - (1 - 2x + x^{2}) = 2x - x^{2}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- So, for $X_{1}$, the pdf is given by:\n",
    "\n",
    "$$\n",
    "f(x) = \\frac{d}{dx} 2x - x^{2} = 2 - 2x\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Now onto $X_{2}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- The probability that $X_{2}$ is less than $x$ depends on the value of $X_{1}$\n",
    "    - If $X_{1} > x$, then $P(X_{2} \\leq x) = 0$\n",
    "    - If $X_{1} = 0$, then $P(X_{2} \\leq x) = x$\n",
    "    \n",
    "- Therefore we can think of our cdf as:\n",
    "\n",
    "$$\n",
    "P(X_{2} \\leq x | X_{1} = x_{1}) = \\frac{x-x_{1}}{1-x_{1}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- So the pdf for $X_{2}$ is equal to:\n",
    "\n",
    "$$\n",
    "f(x) = \\frac{d}{dx}\\frac{x-x_{1}}{1-x_{1}} = \\frac{1}{1-x_{1}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- We can integrate these functions over the possible values of $X_{1}$ and $X_{2}$ to solve for $E(S)$:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "E(S | X_{1} = x_{1} \\leq 0.33) = \\int_{x_{1}}^{2x_{1}}\\frac{1}{1 - x_{1}}(x-x_{1})dx + \\int_{2x_{1}}^{1-x_{1}}\\frac{1}{1 - x_{1}}x_{1}dx + \\int_{1-x_{1}}^{1}\\frac{1}{1 - x_{1}}(1-x)dx\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Since this looks a bit tricky to integrate, we can simplify it\n",
    "\n",
    "**First Integral**\n",
    "\n",
    "- Evaluating the expected length of the second piece when $X_{2}$ falls between $X_{1}$ and $2X_{1}$ is the same as evaluating the expected length of a piece between $0$ and $X_{1}$\n",
    "    - So:\n",
    "\n",
    "$$\n",
    "\\int_{x_{1}}^{2x_{1}}\\frac{x-x_{1}}{1-x_{1}}dx = \\int_{0}^{x_{1}}\\frac{x}{1-x_{1}}dx = \\frac{1}{1-x_{1}} \\left (\\frac{1}{2} x_{1}^{2} \\right ) = \\frac{x_{1}^{2}}{2(1-x_{1})}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Second Integral**\n",
    "\n",
    "- Integrating a constant value $\\frac{x_{1}}{1-x_{1}}$ from $2x_{1}$ to $1-x_{1}$ is just equal to $\\frac{x_{1}}{1-x_{1}}\\left [ (1-x_{1}) - 2x_{1} \\right ] = \\frac{x_{1} \\left (1-3x_{1} \\right )}{1-x_{1}}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Third Integral**\n",
    "\n",
    "- Solving for the expected length of the last piece when $X_{2}$ is between $1-X_{1}$ and 1 is the same as finding the expected value of the first piece when the length is between 0 and $X_{1}$, which is the same as the first integral so:\n",
    "\n",
    "$$\n",
    "\\int_{1-x_{1}}^{1}\\frac{1-x}{1-x_{1}}dx = \\frac{x_{1}^{2}}{2(1-x_{1})}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Combining all three, we get:\n",
    "\n",
    "$$\n",
    "\\int_{x_{1}}^{2x_{1}}\\frac{1}{1 - x_{1}}(x-x_{1})dx + \\int_{2x_{1}}^{1-x_{1}}\\frac{1}{1 - x_{1}}x_{1}dx + \\int_{1-x_{1}}^{1}\\frac{1}{1 - x_{1}}(1-x)dx = \\frac{x_{1}^{2}}{2(1-x_{1})} + \\frac{x_{1} \\left (1-3x_{1} \\right )}{1-x_{1}} + \\frac{x_{1}^{2}}{2(1-x_{1})}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "= \\frac{x_{1}^{2}}{1-x_{1}} + x_{1}\\frac{1-3x_{1}}{1-x_{1}} = x_{1} \\left (\\frac{1-2x_{1}}{1-x_{1}} \\right )\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "____\n",
    "\n",
    "- So, for the scenario where $X_{1}>1/3$, the integral is simpler"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "E(S | X_{1} = x_{1} > 0.33) = \\int_{x_{1}}^{\\frac{1+x_{1}}{2}}\\frac{x-x_{1}}{1-x_{1}}dx + \\int_{\\frac{1+x_{1}}{2}}^{1}\\frac{1-x}{1-x_{1}}dx\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Let's simplify these integrals:\n",
    "\n",
    "**First Integral**\n",
    "\n",
    "$$\n",
    "\\int_{x_{1}}^{\\frac{1+x_{1}}{2}}\\frac{x-x_{1}}{1-x_{1}}dx = \\int_{0}^{\\frac{1-x_{1}}{2}}\\frac{x}{1-x_{1}}dx = \\frac{1}{1-x_{1}}\\frac{1}{2}\\left (\\frac{1-x_{1}}{2} \\right )^{2} = \\frac{1-x_{1}}{8}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Second Integral**\n",
    "\n",
    "$$\n",
    "\\int_{\\frac{1+x_{1}}{2}}^{1}\\frac{1-x}{1-x_{1}}dx = \\int_{0}^{\\frac{1-x_{1}}{2}}\\frac{x}{1-x_{1}}dx = \\frac{1-x_{1}}{8}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Combining these two we get:\n",
    "\n",
    "$$\n",
    "\\int_{x_{1}}^{\\frac{1+x_{1}}{2}}\\frac{x-x_{1}}{1-x_{1}}dx + \\int_{\\frac{1+x_{1}}{2}}^{1}\\frac{1-x}{1-x_{1}}dx = 2\\left (\\frac{1-x_{1}}{8} \\right ) = \\frac{1-x_{1}}{4}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "= \\frac{1-x_{1}}{4}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- So, we now need to integrate these functions over the possible $X_{1}$ values"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\implies E(S) = \\int_{0}^{1/3} (2-2x) \\cdot x \\cdot\\left (\\frac{1-2x}{1-x} \\right ) dx + \\int_{1/3}^{1}(2-2x) \\cdot\\frac{1-x}{4}dx\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "= 5/81 + 4/81 = 9/81 = 1/9 \\approx 0.1111\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "____\n",
    "\n",
    "# Largest\n",
    "\n",
    "- We'll use the logic above, except reversed\n",
    "    - If $X_{1} \\leq 1/3$, then it cannot be the largest piece\n",
    "    - If $X_{1} \\geq 1/2$, then the first piece must be the largest\n",
    "    - If $1/3 < X_{1} < 1/2$, then it can be any of the three"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**First integral**\n",
    "\n",
    "$$\n",
    "E(L|X_{1} \\leq 1/3) = \\int_{x_{1}}^{\\frac{1+x_{1}}{2}}\\frac{1 - x}{1-x_{1}}dx + \\int^{1}_{\\frac{1+x_{1}}{2}}\\frac{x - x_{1}}{1-x_{1}}dx\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "= (3/8)(1-x_{1}) + (3/8)(1-x_{1}) = \\frac{3}{4}(1-x_{1})\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Second integral**\n",
    "\n",
    "$$\n",
    "E(L|X_{1} \\geq 1/2) = \\int_{x_{1}}^{1}\\frac{x_{1}}{1-x_{1}}dx = x_{1}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Third integral**\n",
    "\n",
    "$$\n",
    "E(L|1/3 < X_{1} < 1/2) = \\int_{x_{1}}^{1-x_{1}}\\frac{1-x}{1-x_{1}}dx + \\int_{1-x_{1}}^{2x_{1}}\\frac{x_{1}}{1-x_{1}}dx + \\int_{2x_{1}}^{1}\\frac{x-x_{1}}{1-x_{1}}dx\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "= \\frac{1-2x_{1}}{2-2x_{1}} + \\frac{3x_{1}^{2} - x_{1}}{1-x_{1}} + \\frac{1-2x_{1}}{2-2x_{1}} = \\frac{1}{1-x_{1}}\\left (3x_{1}^{2} - x_{1} + 1 - 2x_{1} \\right ) = \\frac{1 + 3(x_{1}^{2} - x_{1})}{1-x_{1}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Putting it all together\n",
    "\n",
    "$$\n",
    "E(S) = \\\\\n",
    "\\int_{0}^{1/3}(2-2x)\\frac{3}{4}(1-x)dx + \\int_{1/3}^{1/2}(2-2x)\\cdot\\frac{1 + 3(x^{2} - x)}{1-x}dx + \\int_{1/2}^{1}(2-2x)\\cdot x dx\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "= 19/54 + 5/54 + 1/6 = 11/18 \\approx 0.611111\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_____\n",
    "\n",
    "# Middle\n",
    "\n",
    "- Since we know the expected length of both the shortest and longest piece, we can calculate the expected middle piece as:\n",
    "\n",
    "$$\n",
    "E(M) = 1 - E(L) - E(S) = 1 - \\frac{11}{18} - \\frac{1}{9} = \\frac{5}{18}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_____\n",
    "\n",
    "- Let's simulate a bunch of pieces to tie out with our derived values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "N_TRIALS = 10000000\n",
    "array_breakpoints = np.sort(np.random.random(size=(N_TRIALS, 2)), axis=1)\n",
    "piece_1 = array_breakpoints[:,0]\n",
    "piece_2 = array_breakpoints[:,1] - array_breakpoints[:,0]\n",
    "piece_3 = 1-array_breakpoints[:,1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "small_piece, middle_piece, big_piece = np.sort(np.array([piece_1, piece_2, piece_3]), axis=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.1111368802079602, 0.1111111111111111)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.mean(small_piece), 1/9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.6111551050355912, 0.6111111111111112)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.mean(big_piece), 11/18"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.2777080147564485, 0.2777777777777778)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.mean(middle_piece), 5/18"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Eyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}