Wahrscheinlichkeit, dass Random Walk auf Schritt nnn zum ersten Mal den Zustand kkk erreicht

Nach einigen Nachforschungen scheint es so zu sein, dass es solche gibt

$$f(k,\ell)=\frac{k+1}{k+1+\ell}{k+2\ell\choose\ell}$$ Wege zum Staat$k\geq0$In$k+2\ell$Schritte, die niemals passieren$k$Zustand. Dies entspricht der Anzahl der Möglichkeiten, in den Zustand zu wechseln$k+1$zum ersten mal danach$k+1+2\ell$Schritte. Durch Substitution und einfache Wahrscheinlichkeit erhalten wir a $$\frac{k}{k+\ell}{k-1+2\ell\choose\ell}p^{k+\ell}q^{\ell}$$ Wahrscheinlichkeit, den Zustand zu erreichen$k$zum ersten mal danach$k+2\ell$Schritte.

Wir können unsere Formel für beweisen$f$durch Induktion. Für$\ell=0$Die Antwort ist offensichtlich$1$, was mit der gegebenen Formel übereinstimmt. Für$k=-1$Die Antwort ist offensichtlich$0$, was auch mit der gegebenen Formel übereinstimmt. Für$\ell>0$Und$k\geq0$Wir haben zwei Optionen für den ersten Zug: rechts oder links. Wenn wir nach links gehen, gibt es$f(k+1,\ell-1)$Optionen, und wenn wir richtig gehen, gibt es$f(k-1,\ell)$Optionen. Insgesamt haben wir also

$$\begin{align} f(k+1,\ell-1)+f(k-1,\ell) &=\frac{k+2}{k+2+\ell-1}{k+1+2(\ell-1)\choose\ell-1}+\frac{k}{k+\ell}{k-1+2\ell\choose\ell} \\&=\frac{(k+2)(k+2\ell-1)!}{(k+\ell+1)(\ell-1)!(k+\ell)!}+\frac{k(k+2\ell-1)!}{(k+\ell)\ell!(k+\ell-1)!} \\&=\frac{(k+2)(k+2\ell-1)!}{(\ell-1)!(k+\ell+1)!}+\frac{k(k+2\ell-1)!}{\ell!(k+\ell)!} \\&=\frac{\ell(k+2)(k+2\ell-1)!}{\ell!(k+\ell+1)!}+\frac{(k+\ell+1)k(k+2\ell-1)!}{\ell!(k+\ell+1)!} \\&=\frac{(\ell(k+2)+(k+\ell+1)k)(k+2\ell-1)!}{\ell!(k+\ell+1)!} \\&=\frac{(2\ell k+2\ell+k^2+k)(k+2\ell-1)!}{\ell!(k+\ell+1)!} \\&=\frac{(2\ell+k)(k+1)(k+2\ell-1)!}{\ell!(k+\ell+1)!} \\&=\frac{(k+1)(k+2\ell)!}{\ell!(k+\ell+1)!} \\&=f(k,\ell) \end{align}$$ Optionen. Nach Induktionsprinzip beweist dies die Richtigkeit der Formel für$f$.

Nun zugegeben, das löst zwar das Problem, ist aber keine schöne Lösung. Ich habe die Formel durch einfaches Experimentieren für eine halbe Stunde gefunden, und der Beweis ist sehr algebraisch und nicht sehr schön anzusehen. Wenn jemand einen kombinatorischen Beweis hat, wäre das viel besser! Ich werde jetzt auf jeden Fall darüber nachdenken.

Eine erzeugende Funktion

Lassen Sie die Anzahl der Möglichkeiten, um zur Position zu gelangen$s$zum ersten Mal auf Schritt$n$Sei$a_{s,n}$. Die Anzahl einseitiger Längenschritte$2k$Ist$\frac1{k+1}\binom{2k}{k}$, mit erzeugender Funktion$\frac{1-\sqrt{1-4x}}{2x}$. Um erstmal in Position zu kommen$s$auf Schritt$n$, können wir die Anzahl der Wege zählen, um zuerst an die Position zu gelangen$s-1$In$n-2k-1$Schritte multipliziert mit der Anzahl einseitiger Längenschritte$2k$und Summe für alle$k$. Das ist,

$$a_{s,n}=\sum_{k=0}^\infty\frac1{k+1}\binom{2k}{k}\,a_{s-1,n-2k-1}\tag1$$ Wenn wir die erzeugende Funktion einstellen $$f_s(x)=\sum_{n=0}^\infty a_{s,n}x^n\tag2$$ dann mit$\frac{1-\sqrt{1-4x^2}}{2x}=\sum\limits_{k=0}^\infty\frac1{k+1}\binom{2k}{k}x^{2k+1}$, die Cauchy-Produktformel und$(1)$implizieren $$f_s(x)=f_{s-1}(x)\left(\frac{1-\sqrt{1-4x^2}}{2x}\right)\tag3$$ und da$f_0(x)=1$, Induktion ergibt $$\bbox[5px,border:2px solid #C0A000]{f_s(x)=\left(\frac{1-\sqrt{1-4x^2}}{2x}\right)^{\large s}}\tag4$$ Wenn also die Wahrscheinlichkeit eines '$+1$' Schritt ist$p$und von einem '$-1$' Schritt ist$1-p$, dann die Wahrscheinlichkeit von$\frac{n+s}2$'$+1$'Schritte und$\frac{n-s}2$'$-1$'Schritte ist$a_{s,n}p^{\frac{n+s}2}(1-p)^{\frac{n-s}2}=\left(\frac{p}{1-p}\right)^{s/2}a_{s,n}(p(1-p))^{n/2}$. Summieren vorbei$n$gibt die Wahrscheinlichkeit an, die Position zu erreichen$s$überhaupt zu sein $$\begin{align} \left(\frac{p}{1-p}\right)^{s/2}f_s\!\left(\sqrt{p(1-p)}\right) &=\left(\frac{1-|1-2p|}{2(1-p)}\right)^{\large s}\\[3pt] &=\left\{\begin{array}{}\left(\frac{p}{1-p}\right)^s&\text{if }p\lt\frac12\\1&\text{if }p\ge\frac12\end{array}\right.\tag5 \end{align}$$

---

Eine geschlossene Form

Um eine geschlossene Form abzuleiten für$a_{s,n}$, betrachten wir zunächst die Reihe

$$\sum_{n=0}^\infty b_{s,n}x^n=\left(\frac{1-\sqrt{1-4x}}{2x}\right)^{\large s}\tag6$$ wo, vergleichen$(4)$Und$(6)$, wir bekommen $$\begin{align} a_{s,s+2n}&=b_{s,n}\\ a_{s,s+2n+1}&=0 \end{align}\tag7$$ Mit der Tatsache, dass $$\left(\frac{1-\sqrt{1-4x}}{2x}\right)^2=\frac1x\frac{1-\sqrt{1-4x}}{2x}-\frac1x\tag8$$ wir bekommen die Relation $$b_{s,n}=b_{s-1,n+1}-b_{s-2,n+1}\tag9$$ Wir wissen das $$\begin{align} b_{0,n}&=[n=0]\\[3pt] b_{1,n}&=\frac1{n+1}\binom{2n}{n}=\binom{2n}{n}-\binom{2n}{n-1} \end{align}\tag{10}$$ was das impliziert $$\begin{align} b_{2,n}&=\frac1{n+2}\binom{2n+2}{n+1}=\binom{2n+1}{n}-\binom{2n+1}{n-1}\tag{11}\\[6pt] b_{3,n}&=\frac1{n+3}\binom{2n+4}{n+2}-\frac1{n+2}\binom{2n+2}{n+1} =\binom{2n+2}{n}-\binom{2n+2}{n-1}\tag{12} \end{align}$$ Ein Muster erscheint; das ist, $$\begin{align} b_{s,n} &=\binom{2n+s-1}{n}-\binom{2n+s-1}{n-1}\\[3pt] &=\frac{s}{2n+s}\binom{2n+s}{n}\tag{13} \end{align}$$ was befriedigt$(9)$mit der Formel von Pascal . Daher Bewerbung$(7)$Erträge $$\bbox[5px,border:2px solid #C0A000]{a_{s,n}=\left\{\begin{array}{} \frac sn\binom{n}{(n-s)/2}=\binom{n-1}{(n-s)/2}-\binom{n-1}{(n-s-2)/2}&\text{if }2\mid n-s\\ 0&\text{if }2\nmid n-s \end{array}\right.}\tag{14}$$

Diese Antwort ist eine Erweiterung der Antwort von @SmileyCraft. Wie er in seiner Antwort sagt, wäre es schön, einen kombinatorischen Beweis zu haben. Ich habe vielleicht einen gefunden. Das Problem scheint im Geiste dem zu ähneln, bei dem Sie ein quadratisches Gitter haben, in der unteren linken Ecke beginnen und zur oberen rechten Ecke gelangen müssen, um die Anzahl der Pfade zu finden, bei denen Sie die Hauptdiagonale des Gitters nicht überqueren (OK, um es zu berühren). In diesem Fall ist die Anzahl solcher Pfade die katalanische Nummer.

$$C_n = \frac{2n \choose n}{n+1} = {2n \choose n} - {2n \choose n-1}$$

In Anlehnung daran kann die obige Formel von @SmileyCraft auch wie folgt geschrieben werden:

$$f(k,l) = \frac{k+1}{k+1+l} {k+2l \choose l} = {k+2l \choose l} - {k+2l \choose l-1} \tag{1}$$

Nun, das Problem hier für den Random Walk nicht überqueren$k$kann in ein Netzproblem umgewandelt werden. Wir haben im Grunde (gemäß der Konvention von @SmileyCraft)$l$Schwänze und$l+k$Köpfe und müssen sie so anordnen, dass sie die nie überqueren$k$. Dies ist völlig gleichbedeutend mit der Aussage, dass wir nach rechts gehen, wenn wir ein Zahl bekommen, und nach oben, wenn wir ein Kopf auf einem Gitter haben, das hat$l+k$Reihen und$l$Säulen.

Eine andere Möglichkeit, dies zu sehen, besteht darin, auf der x-Achse die Wurfzahl und auf der y-Achse die Punktzahl des Random Walks darzustellen. Stellen Sie sich nun einen Weg vor, der von dort ausgeht$(0,0)$Zu$(k+2l,k)$. Drehen Sie jetzt einfach das ganze Bild um 45 Grad und Sie erhalten das Raster.

Also die Formel für$f(k,l)$Oben ist einfach die Anzahl der Wege, um in einem Raster von links unten nach rechts oben zu gehen$l$Reihen und$l+k$Spalten so, dass der Pfad niemals die Linie kreuzt$y=x+k$.

Aber wie zeigen wir, dass dies der obigen Gleichung (1) entspricht? Ich habe geschummelt und die gleiche Argumentation wie die Antwort von @Marcus M hier verwendet . Es geht so:

Wir kennen die Gesamtpfade in unserem Gitter$k+2l \choose l$. Die guten Pfade sind diejenigen, die niemals die Linie überqueren$y=x+k$. Dann,

# gute Pfade = # Pfade - # schlechte Pfade

Jetzt kreuzt jeder schlechte Pfad die Linie$y=x+k$. Also muss es die Linie berühren$y=x+k+1$(die Diagonale direkt darüber).

Teilen Sie einen solchen Pfad in zwei Teile. Der Teil vom Ursprung bis zur Berührung des$y=x+k+1$Linie und den Teil danach. Der erste Anteil kann darüber reflektiert werden$y=x+k+1$. Und dies führt zu einer Bijektion zu einem Weg von$(-(k+1),(k+1))$Zu$(l,k+l)$. Die schlechten Pfade können also Pfaden von unten links nach oben rechts eines anderen Gitters zugeordnet werden, dessen Höhe ist$(k+l)-(k+1)=l-1$. Aber wir haben die Gesamtpfadlänge nicht geändert, also bleibt die Gesamtlänge der schlechten Pfade bestehen$k+2l$. Daher ist die Anzahl der schlechten Pfade$k+2l \choose l-1$.

Wenn wir all dies zusammenfassen, erhalten wir obige Gleichung (1). Das Bild unten zeigt dies z$k=3$Und$t=2$.

Ich denke, ich kann dieses Problem auf eine weniger kombinatorische Weise lösen.

Zum leichteren Verständnis gebe ich nur eine Beweisskizze.

Einige Abkürzungen:

• SRW = Einfacher Random Walk
• [L/R]HS = [linke/rechte] Seite
• iid = unabhängig und identisch verteilt
• # = Zahl

---

Zuerst muss ich das Reflexionsprinzip für SRW vorstellen .

Betrachten Sie SRW:$S_n=X_1 + \cdots + X_n$Und$S_0=0$.$\{X_i\}_{i=1}^{n}$sind iid Zufallsvariablen.

Bezeichnen$M_n$ist die weiteste Position, die wir erreichen können$n$Schritte (formeller,$M_n=\max_{i\in[0,n]} S_i$). Dann

$$\#(M_n\geqslant x, S_n=y) = \#(S_n=2x-y), \quad \text{if}~~x\geqslant y \tag{Reflection Principle}$$

Das ist intuitiv:

1. $x$vor oder um besucht wird$n$(existiert$t\leqslant n$, so dass$S_t=x$);
2. Für jeden Pfad in LHS können Sie alle Verhalten danach "reflektieren" oder "spiegeln".$t$um einen Pfad in RHS zu erhalten und umgekehrt.

---

Dann können wir dieses Problem ganz einfach lösen.

Da geht es nur wann$n$Und$k$haben die gleiche Kuriosität, und$n\geqslant k$, können wir bezeichnen$n=k+2l$.

$$\begin{split} & \#(\text{first visit $k$ at $n$th step}) \\ =& \#(M_{n-1}\leqslant k-1, S_{n-1}=k-1) \\ =& \#(S_{n-1}=k-1) - \#(M_{n-1}\geqslant k, S_{n-1}=k-1) \\ =& \#(S_{n-1}=k-1) - \#(S_{n-1}=k+1) \\ =& \binom{n-1}{k+l-1} - \binom{n-1}{k+l} \\ \end{split}$$

---

Wir können 2 einfache Fälle verwenden, um dieses Ergebnis zu testen:

1. $\#=1$Wenn$n=k$oder$l=0$: $$\binom{k-1}{k-1} - \binom{k-1}{k} = 1 - 0 = 1$$
2. $\#=k$Wenn$n=k+2$oder$l=1$: $$\binom{k+1}{k} - \binom{k+1}{k+1} = (k+1) - 1 = k$$