{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\def\\CC{\\bf C}\n",
    "\\def\\QQ{\\bf Q}\n",
    "\\def\\RR{\\bf R}\n",
    "\\def\\ZZ{\\bf Z}\n",
    "\\def\\NN{\\bf N}\n",
    "$$\n",
    "# Random walk on the discrete line\n",
    "\n",
    "## Average jump\n",
    "\n",
    "The thirst street is made of a juxtaposition of bars labelled\n",
    "$0,1,2,\\dots$, starting from downtown (bar number $0$). A bunch of\n",
    "drunkards is drinking in bar $0$. At midnight, all of them are kicked\n",
    "out of the bar. Every minute, each drunkard either stays at its position\n",
    "with probability $1/2$, or jumps in the next bar with probability $1/2$,\n",
    "they are so drunk that the jumps are independent, and the drunkards do\n",
    "not interact with each other. We want to understand how the drunkards\n",
    "get distributed when $n$ is large.\n",
    "\n",
    "**Write** a function `drunkard_jumps(n)` which samples a list of `n`\n",
    "jumps (with values `0` or `1`).\n",
    "\n",
    "*Hint:* you can have a look at the `randint` function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Write** a function `drunkard_positions(n)` which returns a list of `n`\n",
    "consecutive positions of such a drunkard, starting at position `0`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Write** a function `plot_drunkard_positions(n)` which plots the\n",
    "sequence of positions as a function $\\{0,\\dots,n-1\\}\\to \\mathbb{N}$.\n",
    "\n",
    "*Hint:* you can have a look at the `enumerate`, `point2d` and `line2d`\n",
    "functions. Starting from an empty `Graphics()` object and adding of\n",
    "several graphics objects to it results in the superposition of those\n",
    "graphics."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Extend** this to a function `plot_drunkard_positions(n,d)` which\n",
    "samples the sequences of `d` drunkards on the same graphic and observe\n",
    "the result.\n",
    "\n",
    "*Hint:* You can have a look at the `rainbow` function to get a sequence\n",
    "of different colors, and use the `color` option in the graphics objects."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Write** a function `drunkard_average_speeds(n)` which returns a list\n",
    "of `n` consecutive average speeds, that is, for each `i <= n-1`, the\n",
    "average number of bars visited from `0` to `i` per minute."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Write** a function `plot_drunkard_average_speeds(n,d)` that plots the\n",
    "the consecutive average speeds of `d` drunkards up to `n` minutes.\n",
    "\n",
    "*Hint:* if you think that this function is very close to\n",
    "`plot_drunkard_positions(n,d)`, you can try to refactor your code by\n",
    "writing a single `plot_samples(function,n,d)`, to be applied to the\n",
    "`drunkard_positions` and `drunkard_average_speeds` functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Formulate a conjecture** on the long-term behaviour of the average\n",
    "speed of the drunkards.\n",
    "\n",
    "## Scattering\n",
    "\n",
    "To avoid accidents caused by dangerous cars, an enlightener lifeguard is\n",
    "following the group of drunkards at constant speed $1/2$ bar per minute\n",
    "with a light.\n",
    "\n",
    "**Write** a function `plot_enlightener_view(n,d)` that plots the\n",
    "trajectories of `d` drunkards from the point of view of the enlightener\n",
    "lifeguard."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to save energy, the enlightener lifeguard wants to know how far\n",
    "should her light illuminate in order to enlighten most drunkards. Of\n",
    "course, after $n$ minutes, a distance of $n/2$ bars is enough to ensure\n",
    "that all drunkards are illuminated, whatever the probabilities. But she\n",
    "wants to save more energy, while still illuminating most drunkards.\n",
    "\n",
    "**Write** a function `guess_scattering(n,d)` to help you guess the best\n",
    "$\\alpha$ in $[0,1]$ such that a light illuminating $n^\\alpha$ after $n$\n",
    "minutes illuminates most drunkards.\n",
    "\n",
    "*Hint:* the logarithm helps to discover polynomial and exponential\n",
    "rates."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Write** a function `plot_scattered_enlightener_view(n,d)` that adds to\n",
    "the enlightener lifeguard's view, some constant (positive and negative)\n",
    "multiples of $n^\\alpha$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Formulate a conjecture** on the second order long-term behaviour of\n",
    "the trajectories of the drunkards.\n",
    "\n",
    "## Distribution\n",
    "\n",
    "After $n$ minutes, the drunkards fall asleep, and the lamp illuminates\n",
    "them. The enlightener lifeguard takes a picture of the \"heap\" of\n",
    "sleeping drunkards. The zoom is such that the picture boundaries\n",
    "corresponds to the enlightened part of the street.\n",
    "\n",
    "**Write** a function `asleep_drunkard_distribution(n,d)` that plots the\n",
    "distribution of `d` asleep drunkards on the picture after `n` steps."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Formulate a conjecture** on the limit shape of the heap of asleep\n",
    "drunkards (`d` might depend on `n`, do not forget the zoom).\n",
    "\n",
    "**Write** an animation that shows the convergence to some limit curve\n",
    "when $n$ tends to infinity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## An exhaustive search\n",
    "\n",
    "To find the exact limit distribution, an army of docile soldiers is\n",
    "hired, so that each possible drunkard walk is simulated by one soldier.\n",
    "\n",
    "**How many** soldiers do we need to simulate each possible trajectory\n",
    "with $n$ steps ? After $n$ steps, **how many** soldiers are located in\n",
    "front of the bar $k$ ?\n",
    "\n",
    "**Write** a function `exact_soldier_distribution(n)` that plots the\n",
    "distribution of the soldiers at time $n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Universality\n",
    "\n",
    "The day after, the drunkards got sick of alcohol and decide to take some\n",
    "ecstasy. Now, at each second, they are jumping by a step $s_i$ with\n",
    "probability $p_i$, where:\n",
    "\n",
    "> -   $s_i \\in \\mathbb{R}$ ($0\\leq i < k$)\n",
    "> -   $p_i \\in [0,1]$ ($0\\leq i < k$)\n",
    "> -   $\\sum_{i=0}^{k-1} p_i = 1$\n",
    "\n",
    "**Try** to extend and illustrate the previous laws to this setting.\n",
    "\n",
    "*Hint:* you can have a look at the `random` function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edit here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "Drunkards let us discover the folloging laws of probabilities:\n",
    "\n",
    "> -   the [law of large\n",
    ">     numbers](https://en.wikipedia.org/wiki/Law_of_large_numbers)\n",
    "> -   the [central limit\n",
    ">     theorem](https://en.wikipedia.org/wiki/Central_limit_theorem) and\n",
    ">     the [normal\n",
    ">     distribution](https://en.wikipedia.org/wiki/Normal_distribution)\n",
    "> -   its relation with the [binomial\n",
    ">     coefficients](https://en.wikipedia.org/wiki/Binomial_coefficient)\n",
    "\n",
    "------------------------------------------------------------------------\n",
    "\n",
    "Authors  \n",
    "-   Thierry Monteil\n",
    "-   Vincent Delecroix\n",
    "\n",
    "License  \n",
    "CC BY-SA 3.0"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "sagemath",
   "name": "sagemath"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}