{
"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"
}
}
}