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