Möglichkeiten für Positionswechsel bei vorgegebenen Schritten

18.06.2015, 09:34	Daniel_Physiker	Auf diesen Beitrag antworten »
Möglichkeiten für Positionswechsel bei vorgegebenen Schritten Meine Frage: Ich bin im Rahmen meiner Bachelorarbeit in Physik auf ein kombinatorisches Problem gestoßen. Eigentlich geht es um die Bestimmung von Energieniveaus für bestimmte Potentiale mit einer recht umständlichen Methode, aber ich formuliere das Problem im Folgenden einfach als rein mathematisches Problem: Es gibt eine bestimmte Anzahl N Positionen (nebeneinander, 1-dimensional). Ein Teilchen befindet sich anfangs auf einer der Positionen und bewegt sich entweder einen "Schritt" nach links oder nach rechts. Die für mich interessante Größe ist nun die Anzahl der Möglichkeiten bei einer bestimmten Anzahl von Schritten von einer Position zu einer anderen zu kommen. Diese Größe hängt von vier Variablen ab: Start- und Endpunkt, Anzahl der Positionen N und Anzahl der Schritte. Besonders wichtig sind die Folgen, die entstehen, wenn man Start- und Endpunkt festhält und die Anzahl der Schritte n variiert. Das Ziel ist es, am Ende für die Folge eine explizite Formel zu haben, die im Wesentlichen die Form $\begin{eqnarray} c_1\cdot a_1^{n}+c_2 \cdot a_2^n + \dots \end{eqnarray}$ haben sollte. Meine Ideen: Für bestimmte Spezialfälle habe ich bereits eine Antwort gefunden: - Für $\begin{eqnarray} N=3 \end{eqnarray}$ erhalten wir als Anzahl der Möglichkeiten für den Übergang von der mittleren Position (0) zur mittleren Position nach einer geraden Anzahl an Schritten n $\begin{eqnarray} M^n_{0 \rightarrow 0} = 2^{n/2} \end{eqnarray}$ . (Für ungerade n ist die Anzahl der Möglichkeiten natürlich 0). Für andere Übergänge, z.B. $\begin{eqnarray} 1 \rightarrow -1 \end{eqnarray}$ erhält man einen ähnlichen Zusammenhang. - Für $\begin{eqnarray} N=4 \end{eqnarray}$ entspricht die Anzahl der Möglichkeiten im Wesentlichen den Fibonacci-Zahlen. Z.B. ist $\begin{eqnarray} M^n_{-1/2 \rightarrow -1/2} = 1,2,5,13,34\dots \end{eqnarray}$ und $\begin{eqnarray} M^n_{-1/2 \rightarrow +1/2} = 1,3,8,21,55\dots \end{eqnarray}$ wobei wir natürlich im ersten Fall nur die geraden n und im zweiten Fall nur die ungeraden n berücksichtigt haben. Die Formel von Moivre / Binet gibt zum Glück auch eine explizite Darstellung mit der gewünschten Form an. - Für eine unendliche Anzahl von Punkten / eine periodische Situation gilt $\begin{eqnarray} M=\binom{n_r+n_l}{n_r} \end{eqnarray}$ für beliebige Anfangs- und Endpositionen. ( $\begin{eqnarray} n_l \end{eqnarray}$ : Schritte nach links; $\begin{eqnarray} n_r \end{eqnarray}$ : nach rechts) Die Diagramme, die ich zur Veranschaulichung des Problems gezeichnet habe, sind unten eingefügt. Mich würde es interessieren, ob es bereits eine mathematische Theorie gibt, mit der man für eine beliebige Anzahl von Positionen N solche Folgen ermitteln kann. Ich habe schon einiges ausprobiert, aber noch keine erfolgversprechende Idee, wie ich meine Überlegungen auf den Fall von beliegen N verallgemeinern kann.
18.06.2015, 11:27	HAL 9000	Auf diesen Beitrag antworten »
Hmm, ohne Limits links und rechts entspricht das einer zufälligen Irrfahrt ("random walk"), dafür gibt es eine exzellent ausgebaute Theorie, die alle möglichen Fragen rund um dieses Problem diskutiert. Durch die Begrenzungen bei dir kann man da leider das meiste nicht übernehmen. Ich würde das ganze mit Aufenthaltswahrscheinlichkeiten beschreiben: Beschreibt p den N-dimensionalen Vektor der Aufenthaltswahrscheinlichkeiten eines Teilchens zu einem gewissen Zeitpunkt, so gibt $\begin{align} p'=Mp \end{align}$ den entsprechenden Vektor zum Folgezeitpunkt an, wobei die Übergangsmatrix $\begin{align} M \end{align}$ dieser Markov-Kette folgende Struktur hat (am Beispiel N=5): $\begin{align} M = \begin{pmatrix} 0 & \frac{1}{2} & 0 & 0 & 0 \\ 1 & 0 & \frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & 0 & \frac{1}{2} & 0 & 1\\ 0 & 0 & 0 & \frac{1}{2} & 0\end{pmatrix} \end{align}$ Nach $\begin{align} n \end{align}$ Schritten hat man entsprechend $\begin{align} p'=M^np \end{align}$ als Verteilung, es ist also das Verhalten der Potenz $\begin{align} M^n \end{align}$ zu untersuchen, da spielen die Eigenwerte von $\begin{align} M \end{align}$ eine zentrale Rolle, das sind nämlich jene $\begin{align} a_1,a_2,\ldots \end{align}$ , von denen du am Ende deiner Frage geredet hast. EDIT: Hmm, das mit den Wahrscheinlichkeiten ist wohl nicht das, was du suchst: Bei dir zählt jede Transition einfach, ob nun 2->1 oder 1->2, egal. Bei den Wahrscheinlichkeiten oben zählt 1->2 "doppelt", da ja nur diese Transition da möglich ist, im Gegensatz zu 2->1, wo auch 2->3 gleichberechtigt möglich wäre. Also entschuldige das obige, zumindest ist es verwandt.
18.06.2015, 13:39	Daniel_Physiker	Auf diesen Beitrag antworten »
Danke, dass du dir die Mühe gemacht hast, dir mein Problem anzuschauen! Ich bin gerade dabei, deine Hinweise auf das Problem anzuwenden und gerade die Idee, einen Vektor-Matrix-Formalismus anzuwenden, ist sehr hilfreich (und ich ärgere mich ein bisschen, dass ich da nicht selbst darauf gekommen bin).
18.06.2015, 13:54	HAL 9000	Auf diesen Beitrag antworten »
Ja, stimmt - mit $\begin{align} M = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 1 & 0\end{pmatrix} \end{align}$ und entsprechender Betrachtung von $\begin{align} M^n \end{align}$ kommt man deinem Anliegen schon sehr nahe. Das ist dann keine stochastische Matrix mehr, aber gewissermaßen eine "Zählmatrix". Etwa im Fall $\begin{align} N=4 \end{align}$ kommt man dann auf die vier "Fibonacci"-Eigenwerte $\begin{align} \frac{\pm 1 \pm \sqrt{5}}{2} \end{align}$ für $\begin{align} a_1,\ldots,a_4 \end{align}$ .

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »