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