Author

Tim Adler

Publishing date

April 21, 2022

Language

German

💡

English abstract

During my time as a mentor of the math working group for gifted middle and high school students, one of the participants asked me for input on a problem they had been working on. He had heard of 1D random walks and had thought bout extending it. Instead of working with a fixed step size, he was wondering what would happen if for each step, the step size was drawn from a uniform distribution from 0 to 1. In particular, they were wondering for any given threshold t > 0, what‘s the expected number of steps n to pass the threshold and does that expectation even exist?

At home, I spent some time thinking about the problem and found a closed formula. I wrote the blog post such that the student could check my reasoning asynchronously between working group meetings and as a basis for further discussion. That‘s also the reason why the blog post is in German.

Einleitung

Ich war bis ca. 2022 einer der Mentoren der Mathe-AG des Life Science Lab des DKFZ in Heidelberg. In der Mathe-AG wird jedes Schuljahr ein (hochschul-)mathematisches Thema mit motivierten Schülerinnen und Schülern behandelt.

Hin und wieder kommen die Teilnehmenden mit eigenen Fragen auf uns zu und die letzte Frage hat mich sehr generdsnipt. Die Problemstellung war die folgende: Wir starten auf dem reellen Zahlenstrahl bei 0 und ziehen eine Zufallszahl $x_1$ gleichverteilt aus dem Intervall $[0, 1]$ und addieren sie zu unseren momentanen Position. Dann ziehen wir eine weitere Zufallszahl $x_2$ wie zuvor und addieren diese zu unserer Position. Diesen Vorgang wiederholen wir beliebig oft. Die Frage: Zu einer gegebenen Schranke $t > 0$ , was ist die mittlere Anzahl an “Schritten” (also gezogenen Zufallszahlen) bis wir $t$ erreichen? Wie ist das asymptotische Verhalten des Mittelwerts für $t \to \infty$ ?

Wie sich zeigen wird, können wir eine geschlossene Formel für den Mittelwert herleiten und uns damit den beiden Fragen nähern. Zunächst formalisieren wir das Problem, d.h. wir definieren alle Größen als Zufallsvariablen. Danach zeigen wir, dass der gesuchte Mittelwert existiert und leiten eine Formel her. Diese vergleichen wir mit dem simulierten Prozess und, motiviert durch die empirischen Resultate, vereinfachen wir die Formel weiter.

Formalisierung

Wir fixieren eine Schranke $t > 0$ . Des weiteren definieren wir für alle $i \in \mathbb{N}$ die Zufallsvariablen $X_i \stackrel{\text{i.i.d}}{\sim} \mathcal{U}[0, 1]$ , wobei wir mit $\mathcal{U}[0,1]$ die Gleichverteilung auf dem Interval $[0, 1]$ bezeichnen und i.i.d. für ‘independent and identically distributed’, also unabhängig und aus der gleichen Verteilung stammend, steht. Dann erhalten wir unsere Position nach Schritt $k \in \mathbb{N}$ als

S_k \coloneqq \sum_{i=1}^k X_i = X_1 + \dots + X_k.

$S_k$ ist auch eine Zufallsvariable und sie folgt einer bekannten Verteilung, nämlich der Irwin-Hall-Verteilung. Das wird später noch wichtig werden.

Als letztes brauchen wir noch den Schritt $N$ , nach dem wir $t$ überschreiten, dieses ist gegeben durch

\begin{aligned}N & \coloneqq \min \{k \in \mathbb{N} \mid S_k \geq t\}\\& = n, \quad \text{so dass } S_n \geq t \text{ und } S_{n-1} < t.\end{aligned}

Zunächst könnte es passieren, dass $S_k < t$ für alle $k \in \mathbb{N}$ . Dann würde unsere Definition von $N$ nicht funktionieren. Damit wir uns nicht um diesen Fall kümmern müssen, können wir zeigen, dass die Wahrscheinlichkeit, dass alle $S_k < t$ sind gleich 0 is. In Formeln bedeutet das

\mathbb{P}[S_1 < t\ \wedge\ S_2 < t\ \wedge \dots ] \stackrel{!}{=} 0.

Das Komplement von diesem Ereignis ist, wenn ein $k \in \mathbb{N}$ existiert, so dass $S_k \geq t$ . Wenn wir zeigen können, dass dieses Ereignis Wahrscheinlichkeit 1 hat, muss das ursprüngliche Ereignis Wahrscheinlichkeit 0 haben.

Dazu können wir das schwache Gesetz der großen Zahlen verwenden (das im Fall von i.i.d. $X_i \sim \mathcal{U}[0,1]$ erfüllt ist). Dazu definieren wir

\bar X_k \coloneqq \frac1k \sum_{i=1}^k (X_i - \mathbb{E}[X_i]) = \frac1k S_k - \frac12.

Dann existiert für beliebiges $\varepsilon > 0$ und beliebiges $\delta > 0$ ein $k_0 \in \mathbb{N}$ , so dass

\mathbb{P}[-\varepsilon < \bar X_k < \varepsilon] > 1 - \delta

für alle $k \geq k_0$ . Der Ausdruck $-\varepsilon < \bar X_k < \varepsilon$ kann umgeformt werden zu $k \left ( \frac12 - \varepsilon \right ) < S_k < k \left ( \frac12 + \varepsilon \right )$ . Wählen wir nun $\varepsilon \coloneqq \frac14$ und $k_1 \coloneqq \max(2\lceil t \rceil, k_0)$ , dann gilt für alle $k \geq k_1$

\begin{aligned}k \left ( \frac12 - \varepsilon \right ) & = k \left ( \frac12 - \frac14 \right )= \frac{k}{4} \geq \frac{4\lceil t \rceil}{4} \geq t.\end{aligned}

Zusammen mit dem schwachen Gesetz der großen Zahlen erhalten wir

\begin{aligned}\mathbb{P}[S_k \geq t] & \stackrel{(1)}{=} \mathbb{P}[S_k > t]\\ & \geq \mathbb{P}\left[S_k > k \left ( \frac12 - \varepsilon \right )\right]\\ & \geq \mathbb{P}\left[k\left(\frac12 - \varepsilon \right) < S_k < k \left (\frac12 + \varepsilon \right)\right]\\ & = \mathbb{P}[- \varepsilon < \bar X_ k < \varepsilon]\\ & > 1 - \delta\end{aligned}

für alle $k \geq k_1$ , wobei wir bei (1) verwendet haben, dass $S_k$ einer stetigen Verteilung folgt (mit etwas mehr Arbeit sollten wir auch ohne diese Annahme auskommen). Nun war $\delta > 0$ beliebig gewählt, d.h. wir finden zu jedem $\delta$ ein $k \in \mathbb{N}$ , so dass $\mathbb{P}[S_k \geq t] > 1 - \delta$ . Zusammen erhalten wir

\begin{aligned}\mathbb{P}[S_1 < t \wedge S_2 < t \wedge \dots] = 1 - \mathbb{P}[S_1 \geq t \vee S_2 \geq t \vee \dots] \leq 1 - \mathbb{P}[S_k \geq t] < 1 - 1- \delta = \delta\end{aligned}

für beliebiges $\delta > 0$ , was nur für $\mathbb{P}[S_1 < t \wedge S_2 < t \wedge \dots] = 0$ erfüllt sein kann.

Zähldichte für $N$

Jetzt, wo wir wissen, dass $N$ wohldefiniert ist, können wir versuchen die Verteilung von $N$ besser zu verstehen. Nach Defnition kann $N$ nur Werte in den natürlichen Zahlen annehmen, deswegen können wir hoffen eine Zähldichte für $N$ zu finden, diese ist (in unserem Fall) gegeben durch

p\colon \mathbb{N} \to [0, 1], n \mapsto \mathbb{P}[N = n].

Nun, verwenden wir die Definition von $p$ und $N$ und erhalten

\begin{aligned}p(n) & = \mathbb{P}[N = n] = \mathbb{P}[S_n \geq t \wedge S_{n-1} < t].\end{aligned}

Um die Wahrscheinlichkeit auf der rechten Seite zu berechnen, verwenden wir, dass sich die Wahrscheinlichkeit von komplementären Ereignissen zu 1 addieren muss:

$\begin{aligned}1 & = \mathbb{P}[S_n \geq t \wedge S_{n-1} < t] + \mathbb{P}[S_n \geq t \wedge S_{n-1} \geq t] + \mathbb{P}[S_n < t \wedge S_{n-1} < t] + \mathbb{P}[S_n < t \wedge S_{n-1} \geq t]\\& = \mathbb{P}[S_n \geq t \wedge S_{n-1} < t] + \mathbb{P}[S_{n-1} \geq t] + \mathbb{P}[S_n < t] + 0\end{aligned}$ Aufgelöst, erhalten wir

\begin{aligned}p(n) & = \mathbb{P}[N = n]\\ & = \mathbb{P}[S_n \geq t \wedge S_{n-1} < t]\\& = 1 - \mathbb{P}[S_{n-1} \geq t] - \mathbb{P}[S_n < t]\\& = \mathbb{P}[S_{n-1} < t] - \mathbb{P}[S_n < t].\end{aligned}

Als Probe können wir uns überzeugen, dass sich die Zähldichte tatsächlich zu 1 addiert, allerdings ergibt sich das direkt aus der Wohldefiniertheit von $N$ , die wir oben gezeigt haben (dadurch erhalten wir $\mathbb{P}[S_n < t] \to 0$ für $n \to \infty$ ), und in dem wir $S_0 = 0$ interpretieren, was zu $\mathbb{P}[S_0 < t] = 1$ führt. Alle anderen Terme fallen weg, da wir eine Teleskopsumme erhalten.

Beachte, dass wir bisher nur das Gesetz der großen Zahlen verwendet haben und dass der Mittelwert der $X_i$ gleich $\frac12$ ist. Unsere gesamte Betrachtung gilt damit bisher für beliebige i.i.d. $X_i$ , die einer Verteilung folgen, für die das schwache Gesetz der großen Zahlen gilt und deren Mittelwert positiv (wir müssen nur unser gewähltes $\varepsilon$ anpassen) ist. Im nächsten Abschnitt werden wir allerdings Eigenschaften verwenden, die speziell für gleichverteilte $X_i$ gelten.

Der Erwartungswert von $N$

Für eine diskrete Zufallsvariable über $\mathbb{N}$ wie $N$ ist der Erwartungswert gegeben durch den Ausdruck

\mathbb{E}[N] = \sum_{n=1}^\infty n \cdot p(n).

Allerdings könnte es sein, dass diese Reihe divergiert (also unendlich wird). Als nächstes überzeugen wir uns davon, dass dies nicht der Fall ist.

\begin{aligned}\mathbb{E}[N] & = \sum_{n=1}^\infty n \cdot p(n)\\& = \lim_{k \to \infty} \sum_{n=1}^k n \cdot p(n)\\& = \lim_{k \to \infty} \sum_{n=1}^k n \cdot (\mathbb{P}[S_{n-1} < t] - \mathbb{P}[S_n < t])\\ & = \lim_{k \to \infty} \left ( \sum_{n=0}^{k-1} (n+1)\mathbb{P}[S_n < t] - \sum_{n=1}^k n\mathbb{P}[S_n < t] \right ) \\ & = \lim_{k \to \infty} \left (\sum_{n=1}^{k-1} \mathbb{P}[S_n < t] - k\mathbb{P}[S_k < t] \right ) \\& = \sum_{n=1}^\infty \mathbb{P}[S_n < t] - \lim_{k \to \infty} (k \mathbb{P}[S_k < t]) \end{aligned}

Um zu zeigen, dass der Erwartungswert endlich ist, müssen wir zeigen, dass die Reihe und der rechte “Fehlerterm” konvergieren.

Dazu schauen wir uns $\mathbb{P}[S_k < t]$ im Detail an. Wie oben bereits erwähnt, folgt $S_k$ der Irwin-Hall-Verteilung. Weiterhin wird die Funktion

F\colon \mathbb{R} \to [0, 1],\ t \mapsto \mathbb{P}[S_k < t]

als kumulative Verteilungsfunktion bezeichnet und für die Irwin-Hall-Vertilung existiert eine geschlossene Formel! Diese ist gegeben durch

\mathbb{P}[S_k < t] = \frac{1}{k!} \sum_{i=0}^{\lfloor t \rfloor}(-1)^i \binom{k}{i}(t - i)^k = \sum_{i=0}^{\lfloor t \rfloor}\frac{(-1)^i}{(k-i)!\cdot i!}(t - i)^k.

Um die Konvergenz zu zeigen, betrachten wir den Absolutbetrag und schätzen ihn nach oben ab:

\begin{aligned}|\mathbb{P}[S_k < t]| & \leq \sum_{i=0}^{\lfloor t \rfloor} \frac{(t - i)^k}{(k-i)! \cdot i!}\\ & \leq \sum_{i=0}^{\lfloor t \rfloor} \frac{t^k}{(k -i)! \cdot i!}\\ & \leq \sum_{i=0}^{\lfloor t \rfloor} \frac{t^k}{(k - \lfloor k/2 \rfloor)! \cdot \lfloor k/2 \rfloor!}\\ & = \sum_{i=0}^{\lfloor t \rfloor} \frac{t^k}{\lceil k/2 \rceil! \cdot \lfloor k/2 \rfloor!}\\ & \leq (t+1) \frac{t^k}{\lceil k/2 \rceil! \cdot \lfloor k/2 \rfloor!}\\ & \eqqcolon a_k.\end{aligned}

Wir wollen nun das Quotientenkriterium verwenden, um zu zeigen, dass die Reihe $\sum_{k=1}^\infty a_k$ konvergiert. Dazu müssen wir den Bruch $\frac{a_{k+1}}{a_k}$ abschätzen. Betrachten wir die folgende Fallunterscheidung:

Fall 1: Wir nehmen an $k$ ist gerade, d.h. es existiert ein $l \in \mathbb{N}$ , so dass $k = 2l$ . Dann können wir die Rundungsterme wie folgt ausdrücken

\begin{aligned}\lceil k/2 \rceil & = l,\\ \lceil (k+1)/2 \rceil & = l+1,\\\lfloor k/2 \rfloor & = l\quad\text{und}\\\lfloor (k+1)/2 \rfloor & = l.\end{aligned}

Für den Quotienten ergibt das

\begin{aligned}\frac{a_{k+1}}{a_k} & = \frac{(t+1) t^{k+1}\lceil k/2 \rceil! \cdot \lfloor k/2 \rfloor!}{(t+1)t^k \lceil (k+1)/2 \rceil! \cdot \lfloor (k+1)/2 \rfloor!}\\ & = t \frac{l! \cdot l!}{(l+1)!\cdot l!}\\ & = \frac{t}{l+1}\\ & = \frac{2t}{k+2}.\end{aligned}

Fall 2: Wir betrachten den Fall, dass $k$ ungerade ist, d.h. es existiert ein $l \in \mathbb{N}$ , so dass $k = 2l +1$ . Dann können wir die Rundungsterme folgendermaßen ausdrücken

\begin{aligned}\lceil k/2 \rceil & = l+1,\\ \lceil (k+1)/2 \rceil & = l+1,\\\lfloor k/2 \rfloor & = l\quad\text{und}\\\lfloor (k+1)/2 \rfloor & = l+1.\end{aligned}

Für den Quotienten ergibt das

\begin{aligned}\frac{a_{k+1}}{a_k} & = \frac{(t+1) t^{k+1}\lceil k/2 \rceil! \cdot \lfloor k/2 \rfloor!}{(t+1)t^k \lceil (k+1)/2 \rceil! \cdot \lfloor (k+1)/2 \rfloor!}\\ & = t \frac{(l+1)! \cdot l!}{(l+1)!\cdot (l+1)!}\\ & = \frac{t}{l+1}\\ & = \frac{2t}{k+2}.\end{aligned}

Das bedeutet in beiden Fällen gilt $\frac{a_{k+1}}{a_k} = \frac{2t}{k+2} \xrightarrow{k \to \infty} 0$ und mit dem Quotientenkriterium ergibt sich, dass die Reihe $\sum_{k=1}^\infty a_k$ (absolut) konvergiert. Damit können wir das Majorantenkriterium verwenden und erhalten, dass $\sum_{k=1}^\infty \mathbb{P}[S_k < t]$ absolut konvergiert.

Als letztes gilt noch

\begin{aligned}|k \cdot \mathbb{P}[S_k < t]| & \leq k \cdot a_k\\ & = k \cdot \frac{2t}{k+1} a_{k-1}\\ & = \dots\\ & = k \frac{(2t)^k}{(k+1)!}a_0\\ & = \frac{k}{k+1}\frac{(2t)^k}{k!} a_0\\ & = \underbrace{\frac{k}{k+1}}_{\leq 1} \cdot\underbrace{a_0\cdot \frac{2t}{1}\cdot \frac{2t}{2} \dots \frac{2t}{\lceil2t\rceil}}_{\eqqcolon c} \cdot\underbrace{\frac{2t}{\lceil2t\rceil +1}}_{\eqqcolon q < 1} \dots \underbrace{\frac{2t}{k}}_{< q}\\ & \leq c \cdot q^{k - \lceil 2t \rceil} \xrightarrow{k \to \infty} 0.\end{aligned}

Für den Erwartungswert haben wir damit gezeigt, dass

\mathbb{E}[N] = \sum_{k=1}^\infty \mathbb{P}[S_k < t] = \sum_{k=1}^\infty \frac{1}{k!} \sum_{i=0}^{\lfloor t \rfloor} (-1)^i \binom{k}{i} (t - i)^k < \infty

gilt. Also haben wir eine geschlossene Formel für den Erwartungswert gefunden. Allerdings haben wir das Problem, dass sie immer noch durch eine Reihe gegeben ist, was sich schlecht exakt ausrechnen lässt.

Trotzdem fand ich dies eine gute Stelle, um unsere Formel empirisch zu überprüfen.

Vergleich Simulation vs. Formel

Der Random Walk lässt sich leicht in einer Programmiersprache (z.B. Python) implementieren, so dass wir viele Walks simulieren können, um $\mathbb{E}[N]$ zu approximieren. Außerdem können wir die Reihe nach endlich vielen Termen abbrechen (sobald sich der Wert nur noch wenig ändert) und die beiden Werte vergleichen.

Das Ergebnis befindet sich im obigen Plot und wir sehen eine gute Übereinstimmung zwischen Simulation und unserer Formel. Das ist sehr ermutigend. Außerdem sehen wir, dass der Zusammenhang linear (bzw. affin) zu sein scheint mit Steigung ca 2.

Das überzeugte mich, dass es möglich sein sollte die Formel für $\mathbb{E}[N]$ weiter zuvereinfachen.

Vereinfachung von $\mathbb{E}[N]$

Wir wissen bereits, dass die Reihe konvergiert und wir sehen, dass die Formel aus zwei Summen besteht. Aufgrund der absoluten Konvergenz dürfen wir die Reihenfolge der Summierung vertauschen. Damit kommen wir tatsächlich zu einer etwas schöneren Formel, nämlich

\begin{aligned}\mathbb{E}[N] & = \sum_{k=1}^\infty \frac{1}{k!} \sum_{i=0}^{\lfloor t \rfloor} (-1)^i \binom{k}{i} (t -i)^k\\& = \sum_{i=0}^{\lfloor t \rfloor}(-1)^i \sum_{k=1}^\infty \frac{1}{k!} \binom{k}{i} (t-i)^k\\ & \stackrel{(1)}{=} \sum_{i=0}^{\lfloor t \rfloor}(-1)^i \sum_{k=i}^\infty \frac{1}{k!} \binom{k}{i} (t-i)^k\\& = \sum_{i=0}^{\lfloor t \rfloor}(-1)^i \sum_{k=i}^\infty \frac{1}{i!\cdot (k-i)!} (t-i)^k\\ & = \sum_{i=0}^{\lfloor t \rfloor}\frac{(-1)^i}{i!} \sum_{k=i}^\infty \frac{(t-i)^k}{(k-i)!}\\ & \stackrel{l\coloneqq k-i}{=} \sum_{i=0}^{\lfloor t \rfloor}\frac{(-1)^i}{i!} \sum_{l=0}^\infty \frac{(t-i)^{l+i}}{l!}\\ & = \sum_{i=0}^{\lfloor t \rfloor}\frac{(-1)^i(t-i)^i}{i!} \sum_{l=0}^\infty \frac{(t-i)^{l}}{l!}\\& \stackrel{(2)}{=} \sum_{i=0}^{\lfloor t \rfloor}\frac{(-1)^i(t-i)^i}{i!} \exp(t - i)\\& = \sum_{i=0}^{\lfloor t \rfloor}\frac{(i - t)^i}{i!} \exp(t - i). \end{aligned}

Für (1) verwenden wir die Konvention dass $\binom{k}{i} = 0$ für $i > k$ und bei (2) verwenden wir die Reihendefinition der Exponentialfunktion.

Fazit

Damit haben wir eine Formel für den Erwartungswert $\mathbb{E}[N]$ , die tatsächlich nur noch aus einer endlichen Summe besteht. Leider lässt sich daraus immer noch nicht der ziemlich lineare Zusammenhang ablesen, den der obige Plot suggeriert.

Trotzdem, als ich die Fragestellung das erste Mal gelesen habe, hätte ich nicht erwartet, dass sich überhaupt eine exakte Formel herleiten lässt. Es war ein spannendes kleines Abenteuer für mich und ich bin sehr happy, das sich so weit gekommen bin 🙂

Als nächstes könnten wir versuchen die Formel weiter zu approximieren, um das asymptotische Verhalten zu untersuchen. Eine erste Möglichkeite könnte sein $i!$ durch die Stirlingformel zu approximieren. Allerdings bin ich damit noch nicht weitergekommen. Falls jemand eine Idee hat, würde ich mich freuen davon zu hören.

Weiterhin ist es natürlich sehr gut möglich, dass ich in einer der Argumentationen einen Fehler gemacht habe. Auch über gefundene Fehler würde ich mich sehr freuen 😉

Privacy notice

Random Walk mit gleichverteilter Schrittweite