EisatoponAI: 🎲 Vibonacci Numbers: όταν η τυχαιότητα συναντά την ακολουθία Fibonacci

$Φωτεινή κινητική μηχανή σε μουσείο επιστημών με διακλαδώσεις πρόσθεσης και αφαίρεσης, σφαίρες από $V_1$ έως $V_7$, τον τύπο $V_n=V_{n-1}\pm V_{n-2}$, τη σταθερά $1{,}1319882487943$ και κόκκινο κυκλικό λογότυπο με λευκό $e$.$

Στην κλασική ακολουθία Fibonacci κάθε νέος όρος είναι το άθροισμα των δύο προηγουμένων:

\[ F_n=F_{n-1}+F_{n-2}, \qquad 1,1,2,3,5,8,13,\ldots \]

Τι θα συνέβαινε όμως αν, αντί να προσθέτουμε πάντοτε, ρίχναμε ένα αμερόληπτο νόμισμα σε κάθε βήμα; Με τη μία όψη προσθέτουμε και με την άλλη αφαιρούμε. Έτσι δημιουργείται μια τυχαία ακολουθία Fibonacci, γνωστή εκλαϊκευτικά και ως ακολουθία Vibonacci:

\[ V_n=V_{n-1}+\varepsilon_nV_{n-2}, \qquad \Pr(\varepsilon_n=1)=\Pr(\varepsilon_n=-1)=\frac12. \]

Με άλλα λόγια, σε κάθε στάδιο επιλέγουμε ανεξάρτητα έναν από τους δύο κανόνες

\[ V_n=V_{n-1}+V_{n-2} \]

\[ V_n=V_{n-1}-V_{n-2}. \]

Μία πιθανή διαδρομή

Ξεκινώντας από $V_1=V_2=1$, μια σειρά επιλογών $+,-,+,-,-,+$ παράγει:

\[ \begin{aligned} V_3&=1+1=2,\\ V_4&=2-1=1,\\ V_5&=1+2=3,\\ V_6&=3-1=2,\\ V_7&=2-3=-1,\\ V_8&=-1+2=1. \end{aligned} \]

Μια άλλη ακολουθία ρίψεων θα έδινε διαφορετικούς όρους. Δεν υπάρχει λοιπόν μία μοναδική ακολουθία Vibonacci, αλλά ένα ολόκληρο σύνολο τυχαίων διαδρομών.

Το απρόσμενο αποτέλεσμα του Viswanath

Θα περίμενε κανείς ότι τόσο διαφορετικές διαδρομές δεν θα έχουν κοινή μακροχρόνια συμπεριφορά. Ο Divakar Viswanath απέδειξε όμως ότι, για σχεδόν κάθε άπειρη ακολουθία ανεξάρτητων επιλογών $+$ και $-$, ισχύει

\[ \lim_{n\to\infty}|V_n|^{1/n} =1{,}1319882487943\ldots \]

Ο αριθμός αυτός ονομάζεται σταθερά του Viswanath. Δηλώνει ότι, σε λογαριθμική κλίμακα, το μέγεθος των όρων αυξάνεται εκθετικά:

\[ |V_n|=(1{,}1319882487943\ldots)^{\,n+o(n)}. \]

Η γραφή αυτή περιγράφει τον εκθετικό ρυθμό και όχι μια ακριβή προσέγγιση κάθε μεμονωμένου όρου. Η φράση «σχεδόν βέβαια» δεν σημαίνει ότι κάθε δυνατή διαδρομή συμπεριφέρεται έτσι. Σημαίνει ότι οι εξαιρέσεις έχουν πιθανότητα $0$.

Σύγκριση με την κλασική Fibonacci

Για την κλασική ακολουθία έχουμε

\[ \lim_{n\to\infty}F_n^{1/n} =\varphi =\frac{1+\sqrt5}{2} \approx1{,}6180339887. \]

Οι τυχαίες αφαιρέσεις μειώνουν αισθητά τον ρυθμό: από περίπου $1{,}618$ σε περίπου $1{,}132$. Δεν σταματούν όμως την εκθετική αύξηση για μια τυπική διαδρομή.

Πώς μπορεί να εμφανίζεται τάξη μέσα από τυχαίες επιλογές;

Κάθε βήμα μπορεί να περιγραφεί με έναν από δύο πίνακες που πολλαπλασιάζουν το διάνυσμα $(V_{n-1},V_{n-2})$. Έτσι η εξέλιξη γίνεται ένα τυχαίο γινόμενο πινάκων. Σε πολύ μεγάλες διαδρομές, ο μέσος λογαριθμικός ρυθμός αυτών των γινομένων σταθεροποιείται. Ο αντίστοιχος εκθέτης Lyapunov οδηγεί στη σταθερά του Viswanath.

Η πλήρης απόδειξη είναι βαθιά και χρησιμοποιεί εργαλεία από τη θεωρία πιθανοτήτων, τα τυχαία γινόμενα πινάκων και τη δυναμική συστημάτων.

Οι επιμέρους όροι είναι απρόβλεπτοι· ο μακροχρόνιος ρυθμός τους, όμως, είναι σχεδόν βέβαιος.