el en el el en el el el en el uk es en es tr en en ru el el el el el en el el el el el el el el el el el el en it en el el el en el el el el el el el el el el el el en el el el en el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el en el el el el el el el el el el el el el el el el el en el el el el en el el el en el el el el el el el el el el el es en es el es es tr en es ru en el el en el el el en el el en en el el el el el el el en el el el el el el el el el el el el el el el el el el el el el el el fr el el el en el el el el el el el el el el el el el el en de de el zh el el el el el el el el el en en de az el en el el en en el en el el en en el el el el el el en en el en el en el el el el el
Βλέπετε, ένας υπολογιστής είναι μία αιτιοκρατική μηχανή – μιλάμε πάντα για τους συνήθεις υπολογιστές που χρησιμοποιούμε εδώ και χρόνια. Δηλαδή, ένας υπολογιστής, αν καθορίσουμε πλήρως το πρωτόκολλο λειτουργίας του – έναν αλγόριθμο – καθώς και τα δεδομένα εισόδου του, τότε μπορούμε να προβλέψουμε το τι θα μας δώσει. Ακόμα, με ίδια είσοδο και χωρίς να έχει υπάρξει κάποια μεταβολή στον τρόπο λειτουργίας του υπολογιστή, θα παίρνουμε διαρκώς το ίδιο αποτέλεσμα. Συνεπώς, αν μπορούμε, δεδομένης της εισόδου και ενός αλγορίθμου, να καθορίσουμε πλήρως και εκ των προτέρων τη συμπεριφορά ενός υπολογιστή, πώς γίνεται να παράγουμε τυχαίους αριθμούς μέσα από έναν υπολογιστή;
import random if __name__ == '__main__': numbers = [] for i in range(100): numbers.append(random.random()) print(numbers)
Τρέχοντας το παραπάνω script – αν δεν έχετε εγκατεστημένη την pyhton, μπορείτε να το τρέξετε σε κάποιον online python interpreter, όπως αυτόν εδώ – παίρνουμε μία έξοδο σαν την παρακάτω:
Εμένα τυχαίοι μου φαίνονται αυτοί οι αριθμοί, πάντως…
Πώς κατάφερε αυτό το πλήρως αιτιοκρατικό μηχάνημα να βγάλει εκατό αριθμούς οι οποίοι φαίνονται τόσο πειστικά τυχαίοι;
Θα δοκιμάσουμε να φτιάξουμε τη δική μας γεννήτρια τυχαίων αριθμών με μία αρκετά απλή ιδέα – για αρχή, τουλάχιστον. Πριν όμως περιγράψουμε την ιδέα μας, να ξεκαθαρίσουμε κάποια πράγματα:
Επειδή αυτό που θα σχεδιάσουμε είναι ένας αλγόριθμος, θα χρειαστεί να του δώσουμε τουλάχιστον ένα δεδομένο ως είσοδο. Αυτό το δεδομένο θα το ονομάζουμε seed και θα εξηγήσουμε στην πορεία τι ρόλο παίζει στη διαδικασία μας.
Ακριβώς επειδή αυτό που θα σχεδιάσουμε θα είναι ένας αλγόριθμος, η συμπεριφορά του θα είναι πλήρως αιτιοκρατική. Δηλαδή, αν του δώσουμε στο μέλλον ξανά το ίδιο seed, θα μας δώσει ξανά τον ίδιο ακριβώς αριθμό – όπως είπαμε, δεν υπάρχει ανταιτιοκρατία σε αυτήν την περίπτωση.
Λοιπόν, σηκώνουμε μανίκια και ξεκινάμε!
Χμμμ, πειστικό θα έλεγε κανείς. Πράγματι, ποιος θα σκεφτόταν να βάλει αυτούς τους τρεις αριθμούς τον έναν μετά τον άλλο; Μάλλον τυχαία θα είναι αυτή η ακολουθία, δεν εξηγείται αλλιώς…
Χρησιμοποιώντας αυτόν τον κώδικα παίρνουμε το εξής αποτέλεσμα:
Εχμ, κάτι δεν πήγε και τόσο στην… τύχη.
Εδώ βλέπουμε μία άκρως ανεπιθύμητη συμπεριφορά. Για την ακρίβεια, βλέπουμε μία συμπεριφορά που μόνο τυχαιότητα δεν αναδεικνύει. Από ένα σημείο και μετά, και μάλιστα αρκετά νωρίς, οι αριθμοί παύουν να μοιάζουν τυχαίοι και η γεννήτριά μας μάς δίνει συνεχώς τον ίδιο αριθμό (100).
Ας δοκιμάσουμε ένα άλλο seed, ας πούμε το 10698 – αλλάζουμε την πέμπτη γραμμή αναλόγως. Σε αυτήν την περίπτωση έχουμε το εξής αποτέλεσμα:
Ώπα, κάτι γίνεται εδώ πέρα!
Εδώ τα πήγαμε πολύ καλύτερα, είναι η αλήθεια. Για την ακρίβεια, αν δείχναμε σε κάποιον αυτή τη λίστα με αριθμούς, δύσκολα θα παρατηρούσε πώς προκύπτει ο κάθε όρος από τον προηγούμενό του χωρίς να έχει κάποια ιδέα για τις αλχημείες μας. Ακολουθώντας τον θυμόσοφο λαό μας, τώρα που βρήκαμε αλάτι, ας βάλουμε και στα λάχανα – ή κάπως έτσι. Ας δοκιμάσουμε, με το ίδιο seed, να παραγάγουμε λίγους παραπάνω τυχαίους αριθμούς, ας πούμε 110:
Εδώ επιστρέψαμε στις παλιές κακές μας συνήθειες. Εκεί που λέγαμε ότι πιάσαμε την καλή κι απλά έφταιγε μία ατυχής επιλογή του seed, ξαφνικά όλα πάλι καταστράφηκαν. Κι εδώ, μετά από ένα σημείο – νωρίς και πάλι, απλά όχι τόσο – όλοι οι αριθμοί που μας δίνει η γεννήτριά μας εκφυλίζονται σε έναν σταθερό αριθμό (62500). Αυτό που αλλάζει είναι:
ο αριθμός στον οποίο σταθεροποιείται η ακολουθία των αριθμών που παίρνουμε,
το μήκος της ακολουθίας που παίρνουμε.
Θα είχε ενδιαφέρον να εξετάσουμε τα μήκη των ακολουθιών για διάφορες τιμές του αρχικού seed. Για την ακρίβεια, με το παρακάτω script μπορούμε να βρούμε το μήκος κάθε ακολουθίας που μπορεί να παραχθεί για όλες τις δυνατές τιμές του seed – από 0 μέχρι 99999:
Στο παραπάνω τμήμα κώδικα επί της ουσίας σταματάμε να μετράμε το μήκος μίας ακολουθίας όταν συναντήσουμε ξανά κάποιον αριθμό, διότι, μόλις καταφέρουμε να παραγάγουμε δύο φορές τον ίδιο αριθμό από εκεί και μετά πέφτουμε σε ατέρμονα βρόχο – διότι, αναγκαστικά, θα επαναλαμβάνονται διαρκώς τα ίδια ψηφία ανάμεσα στις δύο αυτές εμφανίσεις του . Το γράφημα που παίρνουμε από τα παραπάνω είναι το εξής:
Τα μήκη των ακολουθιών διαφορετικών ψευδοτυχαίων αριθμών που μας δίνει η γεννήτρια του von Neumann.
Αυτό που παρατηρούμε παραπάνω είναι ότι στις περισσότερες περιπτώσεις τα μήκη των ακολουθιών είναι ιδιαίτερα μικρά ενώ, γενικά, κυμαίνονται το πολύ μέχρι περίπου 250 – μήκος σχετικά μικρό σε σχέση με τους 100.000 πενταψήφιους αριθμούς που έχουμε στη διάθεσή μας. Επειδή το παραπάνω διάγραμμα είναι ίσως λίγο φτωχό σε πληροφορίες, ας δοκιμάσουμε να ομαδοποιήσουμε τα δεδομένα μας σε ομάδες των 100 παρατηρήσεων και να δούμε το μέσο μήκος κάθε ομάδας. Αυτό το πετυχαίνουμε με το ακόλουθο script – μικρή παραλλαγή του προηγούμενου:
import matplotlib.pyplot as plt def rng(seed): return ((seed ** 2) % 10 ** 7) // (10 ** 2) def random_lengths(): lengths = [0]*(10**3) for i in range(10**5): seed = i next_seed = rng(seed) seen = [i] while not (next_seed in seen): seen.append(next_seed) lengths[i//100] += 1 seed = next_seed next_seed = rng(seed) return [x/100 for x in lengths] if __name__ == '__main__': lengths = random_lengths() plt.plot(lengths, 'bo') plt.show()
Εδώ βλέπουμε αρκετά πιο ξεκάθαρα ότι η γεννήτρια του von Neumann μας δίνει ακολουθίες αριθμών που μπορούν να μας πείσουν ότι είναι κάπως… τυχαίες, με μέσο μήκος κάπου μεταξύ 60 και 70. Αν σκεφτείτε ότι έχουμε στη διάθεσή μας 100.000 αριθμούς βλέπετε ότι το να μπορούμε να πάρουμε πειστικά μία ακολουθία περίπου τυχαίων αριθμών μήκους μόλις 70 είναι, θα έλεγε κανείς, μία μικρή πανωλεθρία.
Εντάξει, πολύ πειραματιστήκαμε, είναι ώρα να περάσουμε σε λίγο πιο αυστηρά χωράφια. Μπορεί η πρώτη μας απόπειρα να φτιάξουμε μία γεννήτρια τυχαίων αριθμών να απέτυχε, σε γενικές γραμμές, αλλά ακριβώς αυτή η αποτυχία μας δίνει αρκετό υλικό για να μπορέσουμε να περιγράψουμε σε πιο αυστηρό επίπεδο κάποιες από τις ιδιότητες που θα θέλαμε να έχει ένα όν που γεννά αριθμούς με φαινομενικά τυχαίο πρώτο.
Αρχικά, μπορούμε να δούμε ότι στα παραπάνω, κάθε όρος προέκυπτε αιτιοκρατικά- ντετερμινιστικά – από τον προηγούμενό του, πάντοτε με τον ίδιο τρόπο. Με άλλα λόγια, όπως είχαμε αναφέρει και στην αρχή, αρκεί να γνωρίζουμε τον αρχικό όρο της ακολουθίας των αριθμών μας – το seed – και τον τρόπο με τον οποίο μεταβαίνουμε από έναν όρο στον επόμενό του, για να περιγράψουμε κάθε όρο της ακολουθίας μας. Έτσι, αν ονομάσουμε αυτόν τον «τρόπο» και το seed μας, μπορούμε να περιγράψουμε την ακολουθία των ψευδοτυχαίων αριθμών μας με τον εξής αναδρομικό ορισμό:
Με βάση τον παραπάνω ορισμό, μπορούμε να περιγράψουμε λίγο πιο κλειστά την ακολουθία μας ως:
όπου με συμβολίζουμε τη σύνθεση της φορές με τον εαυτό της, υπολογισμένη στο . Δηλαδή:
Επίσης, αυστηρά μιλώντας, το μήκος που αναφέραμε παραπάνω είναι, ουσιαστικά, ο παρακάτω φυσικός αριθμός, :
Προσέξετε ότι ο είναι πάντοτε καλά ορισμένος, δεδομένου ότι όπως και να έχει, αφού επιλέγουμε μεταξύ πεπερασμένων στο πλήθος ακεραίων κάθε φορά – ένας υπολογιστής έχει πεπερασμένη μνήμη, άλλωστε – σε κάποια στιγμή θα τους έχουμε εξαντλήσει όλους και θα πάρουμε ξανά κάποιον αριθμό που έχουμε ήδη συναντήσει.
Όπως καταλαβαίνετε, από τα παραπάνω φαίνεται μία σημαντική ιδιότητα που θα θέλαμε να είναι κάθε γεννήτρια ψευδοτυχαίων αριθμών που έχει το μορφή και τη δομή της γεννήτριας του von neumann: να έχει αρκετά μεγάλο . Είναι σαφές γιατί αυτό είναι επιθυμητό – για όσο περισσότερη ώρα δεν επαναλαμβανόμαστε, τόσο αποφεύγουμε το να καταλάβει κανείς ότι δεν παράγουμε αριθμούς στην τύχη.
Η παραπάνω ιδιότητα, όπως είδαμε, εξαρτάται από το seed, καθώς για κάποιες τιμές του seed έχουμε ιδιαίτερα μικρές ακολουθίες ενώ για άλλες έχουμε λιγότερο μικρές. Προσέξτε, επίσης, ότι τα παραπάνω αφορούν μόνο την γεννήτρια του von Neumann που μελετάμε. Πράγματι, μία πιο πειστική γεννήτρια τυχαίων αριθμών ενδέχεται να παράγει δύο και τρεις φορές τον ίδιο αριθμό χωρίς όμως να επαναλάβει και τις επόμενες τιμές που είχε υπολογίσει στο παρελθόν – θα ασχοληθούμε με τέτοιες γεννήτριες στη συνέχεια της σειράς.
Ένα άλλο, επίσης σημαντικό, χαρακτηριστικό που θα θέλαμε να έχει μία γεννήτρια ψευδοτυχαίων αριθμών είναι η κατανομή των αποτελεσμάτων που μας δίνει να είναι όσο το δυνατόν περισσότερο ομοιόμορφη. Με άλλα λόγια, διαισθητικά, θα θέλαμε η συχνότητα με την οποία εμφανίζεται κάθε αριθμός να είναι περίπου η ίδια – θα το εκφράσουμε και τυπικά αυτό στη συνέχεια. Αυτό είναι σαφές ότι συνδέεται άμεσα με τα παραπάνω, καθώς στην περίπτωσή μας, για όποια τιμή του seed κι αν επιλέξουμε, η γεννήτρια του von Neumann δίνει το πολύ 250 διαφορετικούς αριθμούς, επαναλαμβάνοντας ένα τμήμα αυτών τελικά, επ’ άπειρον. Αυτό οδηγεί, σαφώς, κάποιοι αριθμοί να εμφανίζονται από ένα σημείο κι έπειτα με πολύ μεγάλη συχνότητα ενώ κάποιοι άλλοι να μην εμφανίζονται ποτέ.
Διορθώνοντας τα λάθη μας
Με όλα τα παραπάνω να έχουν λεχθεί για τη γεννήτρια του von Neumann μπορεί κάποιοι να έχετε εγκαταλείψει το όνειρο μίας σχετικά απλής και αξιόπιστης γεννήτριας τυχαίων αριθμών. Ωστόσο, μία κακή ιδέα, με τις κατάλληλες τροποποιήσεις, μπορεί να γίνει αρκετά καλή – το έχουμε ξαναδεί αυτό. Αυτό θα προσπαθήσουμε να κάνουμε και σε αυτήν την περίπτωση!
Ένα εργαλείο το οποίο θα βελτιώσει σημαντικά την απόδοση της παραπάνω γεννήτριας είναι οι ακολουθίες Weyl. Οι ακολουθίες Weyl είναι ακολουθίες αριθμών που έχουν μία ιδιαίτερα σημαντική ιδιότητα, άμεσα σχετική με όσα θέλουμε να κάνουμε: είναι ισοκατανεμημένες. Με τον όρο ισοκατανεμημένες εννοούμε το εξής:
Μία ακολουθία πραγματικών αριθμών θα λέγεται ισοκατανεμημένη σε ένα διάστημα αν για κάθε υποδιάστημα ισχύει ότι:
Ο παραπάνω ορισμός αποτυπώνει με ιδιαίτερα άμεσο και κομψό τρόπο μία σημαντική ιδιότητα μίας ακολουθίας αριθμών που μοιάζει τυχαία. Πρέπει το κλάσμα των όρων της ακολουθίας που βρίσκονται σε ένα υποδιάστημα του να είναι ανάλογο του μήκους του. Για παράδειγμα, αν θέλουμε να εξετάσουμε αν μία ακολουθία είναι ισοκατανεμημένη στο τότε θα θέλαμε, τελικά, περίπου οι μισοί της όροι να βρίσκονται στο , περίπου το ένα τρίτο των όρων της να βρίσκεται στο , περίπου το ένα δέκατο των όρων της να βρίσκεται στο κ.ο.κ.
Ωραίος ο ορισμός μας, αλλά τώρα πρέπει να εξετάσουμε αν υπάρχουν όντως τέτοιες ακολουθίες – αλλιώς, ο ορισμός μας είναι κενός νοήματος. Εδώ έρχεται στο παιχνίδι ο Hermann Weyl. Ένα πολύ γνωστό αποτέλεσμα που έχει αποδείξει ο κύριος Weyl είναι το θεώρημα της ισοκατανομής το οποίο μας λέει το εξής:
Αν τότε η ακολουθία , όπου είναι το ακέραιο μέρος του είναι ισοκατανεμημένη στο αν και μόνο αν το είναι άρρητος.
Αρχικά να πούμε ότι, επί της ουσίας, για έναν πραγματικό αριθμό , η ποσότητα είναι το κλασματικό μέρος του – το μέρος δηλαδή που βρίσκεται δεξιά από την υποδιαστολή στο δεκαδικό του ανάπτυγμα. Επομένως, αυτό που μας λέει το παραπάνω θεώρημα είναι ότι τα κλασματικά μέρη των όρων της ακολουθίας είναι ισοκατανεμημένα στο ακριβώς όταν ο είναι άρρητος – πολλές φορές αντί για τον όρο «κλασματικό μέρος του » χρησιμοποιούμε τον όρο ή modulo 1.
Το παραπάνω αποτελεί, πέρα από κάτι άμεσα χρήσιμο για εμάς, κι έναν ιδιαίτερα κομψό χαρακτηρισμό των άρρητων αριθμών: ένας αριθμός είναι άρρητος ακριβώς όταν τα κλασματικά μέρη των ακέραιων πολλαπλασίων του modulo 1 είναι ισοκατανεμημένα στο .
Η αλήθεια είναι ότι η απόδειξη του παραπάνω είναι εν γένει περίπλοκη και, προς το παρόν, δε θα τη συζητήσουμε. Αυτό όμως που μπορούμε εύκολα να δούμε είναι η μία από τις δύο κατευθύνσεις του θεωρήματος και, για να είμαστε και ακριβείς, θα δούμε γιατί το συμπέρασμα δεν ισχύει αν το είναι ρητός. Έστω, λοιπόν, ένας ρητός , με σχετικά πρώτους. Τότε, παρατηρούμε ότι η υποψήφια ακολουθία Weyl, έστω , , έχει μία περιοδικότητα, αφού:
Το παραπάνω, αν και φαίνεται λίγο περίπλοκο μας λέει κάτι απλό. Ας δούμε, ειδικότερα, τον όρο της παραπάνω ακολουθίας. Αυτός είναι:
Με άλλα λόγια, μόλις φτάσουμε στον οστό όρο της ακολουθίας, βλέπουμε έναν ακέραιο, δηλαδή έναν αριθμό με μηδενικό κλασματικό μέρος. Επομένως, ο οστός όρος της ακολουθίας μας είναι μηδενικός. Επειδή, τώρα, κάθε όρος της ακολουθίας μας προκύπτει από τον προηγούμενό του με τον ίδιο ακριβώς τρόπο – προσθέτοντας και κρατώντας μόνο το κλασματικό μέρος – άπαξ και συναντήσουμε έναν όρο δεύτερη φορά, όπως και με την ακολουθία της γεννήτριας του von Neumann, παραπάνω, μπαίνουμε σε έναν ατέρμονα βρόχο, στον οποίο επαναλαμβάνουμε συνεχώς τους ίδιους αριθμούς. Όμως, αυτό σημαίνει, ειδικότερα, ότι οι όροι της ακολουθίας μας παίρνουν κάποιες πεπερασμένες στο πλήθος – το πολύ – διαφορετικές τιμές, άρα η ακολουθία μας δεν είναι ισοκατανεμημένη.
Ε, για την αντίθετη συνεπαγωγή, αυτή που αφορά τους άρρητους, σκεφτείτε ότι οι άρρητοι δεν έχουν αυτή την κακή ιδιότητα των ρητών και, επιπλέον, τα κλασματικά μέρη των πολλαπλασίων τους είναι ομοιόμορφα μοιρασμένα.
Ναι, αλλά άρρητοι σε υπολογιστή;
Τώρα, ίσως κάποιοι αναρωτηθείτε: «Και πώς αναπαριστούμε έναν άρρητο σε ένα ηλεκτρονικό υπολογιστή». Η απάντηση είναι πάρα πολύ απλή: Δεν μπορούμε να αναπαραστήσουμε έναν άρρητο σε ένα υπολογιστή, διότι όλοι οι άρρητοι έχουν άπειρο δεκαδικό – και δυαδικό, σαφώς – ανάπτυγμα και άρα δεν μπορούν να περιγραφούν από τα πεπερασμένα στο πλήθος στοιχεία μνήμης ενός υπολογιστή. Ε, άρα γιατί συζητάμε για αυτές τις ακολουθίες Weyl, αφού δε μπορούν να μας φανούν χρήσιμες στην περίπτωσή μας;
Αν και άμεσα, πράγματι, δεν μπορούμε να υπολογίσουμε μία ακολουθία Weyl σε έναν υπολογιστή, μπορούμε να βρούμε ένα διακριτό ανάλογο μίας τέτοιας ακολουθίας. Πρώτα, όμως, θα βοηθούσε να δώσουμε κι έναν ανάλογο διακριτό ορισμό μίας ισοκατανεμημένης ακολουθίας φυσικών αριθμών:
Αν είναι μία ακολουθία φυσικών αριθμών, τότε αυτή θα λέγεται ισοκατανεμημένη σε ένα αρχικό σύνολο φυσικών αριθμών, , αν για κάθε σύνολο ισχύει:
Επί της ουσίας, απλώς πήραμε τον γενικό ορισμό που είδαμε παραπάνω και τον περιορίσαμε κατάλληλα σε διαστήματα φυσικών αριθμών. Τώρα, θα κάνουμε κάτι ανάλογο και με το θεώρημα της ισοκατανομής του Weyl. Για την ακρίβεια, έχουμε το παρακάτω αποτέλεσμα:
Αν είναι δύο σχετικά πρώτοι φυσικοί αριθμοί, τότε η ακολουθία είναι ισοκατανεμημένη στο .
Το παραπάνω θεώρημα είναι, πράγματι, ένα ανάλογο του γενικού θεωρήματος ισοκατανομής του Weyl, το οποίο όμως είναι ιδιαίτερα εξυπηρετικό, καθώς αναφέρεται σε ακεραίους αριθμούς, δηλαδή πράγματα που ένας υπολογιστής, σε γενικές γραμμές, είναι καλός στο να διαχειρίζεται. Πριν προχωρήσουμε, ας δούμε γιατί το παραπάνω θεώρημα ισχύει. Παίρνουμε δύο σχετικά πρώτους φυσικούς αριθμούς , και θεωρούμε την ακολουθία που αναφέρει το θεώρημα:
Με άλλα λόγια, παίρνουμε πολλαπλάσια του , τα διαιρούμε με το και κρατάμε τα υπόλοιπα αυτών των διαιρέσεων. Τώρα, ας παρατηρήσουμε ότι η παραπάνω ακολουθία είναι περιοδική και μάλιστα:
άρα για . Μένει τώρα να αξιοποιήσουμε το γεγονός ότι οι είναι σχετικά, πρώτοι, δηλαδή ότι έχουν μέγιστο κοινό διαιρέτη ίσο με τη μονάδα. Γι’ αυτόν τον σκοπό θα αξιοποιήσουμε μία χρήσιμη ταυτότητα ακεραίων αριθμών:
όπου με συμβολίζουμε τον μέγιστο κοινό διαιρέτη δύο αριθμών και με το ελάχιστο κοινό τους πολλαπλάσιο. Με δεδομένο ότι οι δύο αριθμοί είναι σχετικά πρώτοι, παίρνουμε ότι , δηλαδή ότι δεν υπάρχει κανένα άλλο κοινό πολλαπλάσιο των μικρότερο το . Τώρα, αν με παρατηρούμε ότι:
Με άλλα λόγια, δύο όροι της είναι ίσοι αν και μόνο αν το είναι πολλαπλάσιο του . Άρα, θα πρέπει το να είναι κοινό πολλαπλάσιο του και του και άρα ή . Επειδή, τώρα, , έπεται ότι , άρα , συνεπώς, . Δηλαδή, όλοι οι όροι της για δείκτες από μέχρι είναι διαφορετικοί, συνεπώς η , αν περιοριστεί στο είναι ένα «ανακάτεμα» των αριθμών του – μία μετάθεση, όπως λέμε. Αυτό μας δίνει άμεσα και την πολυπόθητη ιδιότητα της ισοκατανομής. Πράγματι, αν πάρουμε ένα αρχικό τμήμα φυσικών αριθμών, έστω , για , τότε παρατηρούμε ότι το πλήθος των όρων της που βρίσκονται στο έχει την εξής ενδιαφέρουσα ιδιότητα: Αν για κάποιο τότε:
Το παραπάνω είναι, πράγματι προφανές. Είπαμε ότι η , αν περιοριστεί στο αποτελεί μία μετάθεση των στοιχείων του, δηλαδή, τελικά, οι όροι είναι ακριβώς οι αριθμοί , απλώς με άλλη σειρά. Έτσι, καθώς προχωράμε, από τον προς τον , θα έχουμε κάθε στιγμή στα χέρια μας από 0 μέχρι και από τα στοιχεία του – τελικά, σαφώς, θα τα έχουμε πάρει όλα. Έπειτα, από την περιοδικότητα της , το ίδιο έχουμε και για το . Δηλαδή, θα έχουμε ήδη πάρει τους όρους του από μία φορά – με τους όρους – και τώρα θα τους ξαναπαίρνουμε για δεύτερη φορά – μέσα στους όρους – άρα έχουμε από μέχρι και όρους. Συνεχίζουμε αναλόγως.
Τώρα, θέτουμε για ευκολία – το πλήθος, δηλαδή, των όρων που έχουμε συναντήσει ως το και ανήκουν στο . Η είναι σαφώς αύξουσα και, αν τότε έχουμε άμεσα ότι . Από τα παραπάνω, όμως, έχουμε άμεσα ότι:
Συνεπώς, για έπεται ότι:
Τώρα, επειδή , έπεται ότι:
Αν τώρα αφήσουμε , οπότε και , έπεται άμεσα ότι:
άρα η ακολουθία μας είναι, πράγματι, ισοκατανεμημένη στο .
Τώρα που βρήκαμε μία αρκετά υποσχόμενη ακολουθία, ας δούμε και λίγο πώς μοιάζει. Ας επιλέξουμε για και για – θα εξηγήσουμε αργότερα γιατί επιλέξαμε δύναμη του 2 – και ας σχεδιάσουμε τις πρώτες 3000 τιμές της ακολουθίας. Για να το πετύχουμε αυτό θα χρησιμοποιήσουμε το ακόλουθο script:
import matplotlib.pyplot as plt def weyl(seed, a, n): return (seed + a) % n if __name__ == '__main__': numbers = [] seed = 0 a = 101 n = 2 ** 10 for i in range(3000): seed = weyl(seed, a, n) numbers.append(seed) plt.plot(numbers, 'bo') plt.show()
Αυτό μας δίνει το ακόλουθο γράφημα, όπου οι κουκκίδες αναπαριστούν τους όρους της ακολουθίας μας:
Ό,τι είναι ισοκατανεμημένη, είναι…
Σαφώς, η παραπάνω ακολουθία είναι ισοκατανεμημένη – είναι αρκετά οφθαλμοφανές. Εστιάζοντας λίγο στους πρώτους 1000 όρους, έχουμε το ακόλουθο γράφημα – έχουμε συνδέσει τους διαδιοχικούς όρους της ακολουθίας με μία γραμμή για να φαίνεται με ποια σειρά αυτοί εμφανίζονται:
Ωστόσο, η παραπάνω συμπεριφορά, όπως φαντάζεστε, δε μοιάζει τόσο τυχαία – αν και, μην εξαπατάστε, οι κορυφές που φαίνονται δεν είναι ισοϋψείς στο παραπάνω σχήμα.
Για την ακρίβεια, αν εκτυπώσουμε τους 200 πρώτους όρους της ακολουθίας μας, έχουμε:
Εεεε, είναι λίγο προβλέψιμο το αποτέλεσμα…
Κοιτάζοντας λίγο 2-3 διαδοχικούς όρους καταλαβαίνουμε διαισθητικά πώς προκύπτει ο επόμενος – προσθέτοντας 101 και, όποτε χρειάζεται, κρατώντας το υπόλοιπο της διαίρεσης με το . Δεν είναι, λοιπόν, χρήσιμη ούτε η ακολουθία Weyl για να πείσουμε κάποιον τρίτο ότι παράγουμε αριθμούς στην τύχη.
Ανακατεύοντας τις ιδέες μας
Είδαμε δύο ιδέες, τελικά αναποτελεσματικές και οι δύο, ωστόσο με την καθεμιά να έχει ιδιαίτερα θετικά και αρνητικά γνωρίσματα. Τώρα θα κάνουμε που θα έχει είτε πολύ καλά έιτε πολύ κακά αποτελέσματα: θα μπλέξουμε και τις δύο ιδέες μας.
Για την ακρίβεια, αυτό που θα κάνουμε θα είναι το εξής:
Ξεκινώντας με ένα seed, έστω , θα το υψώνουμε στο τετράγωνο, παίρνοντας το .
Εδώ, αντί να ακολουθήσουμε τη λογική του von Neumann και να κρατήσουμε τα πέντε μεσαία ψηφία του, θα μπλέξουμε μέσα την ιδέα του Weyl. Δηλαδή, επιλέγοντας κι ένα δεύτερο seed, έστω , προσθέτουμε στο τον πρώτο όρο της ακολουθίας του Weyl που παράγεται από αυτό το seed, – επιλέγουμε , για λόγους που θα εξηγήσουμε ευθύς αμέσως.
Από τον νέο αριθμό που έχουμε, κρατάμε τα μεσαία πέντε ψηφία του.
Επαναλαμβάνουμε με τον νέο μας αριθμό.
Πριν εξηγήσουμε το σκεπτικό μας, να πούμε ότι επιλέξαμε το γιατί αυτό είναι το σύνηθες όριο εντός του οποίου οι περισσότεροι υπολογιστές μπορούν να αποθηκεύσουν ακεραίους στη μνήμη τους. Με άλλα λόγια, ένας τυπικός ηλεκτρονικός υπολογιστής αναγνωρίζει ακεραίους στο διάστημα . Έτσι, πρακτικά, γλυτώνουμε τη διαίρεση με το – ούτως ή άλλως, όλοι οι αριθμοί σε έναν ηλεκτρονικό υπολογιστή θα είναι μικρότεροι από .
Τώρα, με το παραπάνω αποσκοπούμε στο να πετύχουμε, από τη μία, την κάπως πιο ανομοιόμορφη κατανομή τιμών που μας δίνει η γεννήτρια του von Neumann, ανακατεύοντας και την ιδιότητα της ισοκατανομής που έχει η αρκετά προβλέψιμη γεννήτρια του Weyl. Το παραπάνω υλοποιείται με το ακόλουθο script:
import matplotlib.pyplot as plt def rng(seed, weyl_seed): return ((seed ** 2 + weyl_seed) % 10 ** 7) // (10 ** 2) def weyl(seed, a): return seed + a if __name__ == '__main__': numbers = [] weyl_seed = 0 a = 101 seed = 56231 for i in range(200): weyl_seed = weyl(weyl_seed, a) seed = rng(seed, weyl_seed) numbers.append(seed) print(numbers)
Το παραπάνω μας δίνει το εξής αποτέλεσμα:
Η αλήθεια είναι ότι μοιάζει αρκετά τυχαίο με μια πρώτη ματιά. Δηλαδή, με μια ματιά, κάποιος θα μας πίστευε σχετικά εύκολα ότι αυτοί οι αριθμοί έχουν επιλεγεί στην τύχη.
Ας σχεδιάσουμε τώρα και τις συχνότητες εμφάνισης των διαφόρων αριθμών που μας δίνει η παραπάνω μέθοδος. Για αυτόν τον σκοπό θα χρειαστούμε το εξής script:
import matplotlib.pyplot as plt def rng(seed, weyl_seed): return ((seed ** 2 + weyl_seed) % 10 ** 7) // (10 ** 2) def weyl(seed, a): return seed + a if __name__ == '__main__': numbers = [] frequencies = [0]*(10**5) weyl_seed = 0 a = 101 seed = 56231 for i in range(10**8): weyl_seed = weyl(weyl_seed, a) seed = rng(seed, weyl_seed) numbers.append(seed) frequencies[seed] += 1 plt.plot(frequencies, 'bo') plt.show()
Στην ουσία, δεν κάναμε τίποτα άλλο από το να παραγάγουμε ψευδοτυχαίους αριθμούς κι έπειτα να μετρήσουμε πόσες φορές βλέπουμε τον καθέναν. Τα αποτελέσματά μας αποτυπώνονται στο παρακάτω σχήμα:
Δεν είναι διόλου κακό!
Εντάξει, είναι ενθαρρυντικό το πρώτο μας σχήμα, θα ήταν όμως χρήσιμο να κάνουμε ό,τι κάναμε και πριν, ομαδοποιώντας τα δεδομένα μας σε κλάσεις των 100 κι έπειτα να μετρήσουμε τη μέση συχνότητα εμφάνισης των μελών της κλάσης. Γι’ αυτόν τον σκοπό παραλλάσσουμε λίγο το παραπάνω script, ως εξής:
import matplotlib.pyplot as plt def rng(seed, weyl_seed): return ((seed ** 2 + weyl_seed) % 10 ** 7) // (10 ** 2) def weyl(seed, a): return seed + a if __name__ == '__main__': numbers = [] frequencies = [0]*(10**3) weyl_seed = 0 a = 101 seed = 56231 for i in range(10**8): weyl_seed = weyl(weyl_seed, a) seed = rng(seed, weyl_seed) numbers.append(seed) frequencies[seed//100] += 1 frequencies = [x/100 for x in frequencies] plt.plot(frequencies, 'bo') plt.show()
Τώρα, τρέχοντας αυτό το script έχουμε – αν τρέξατε το προηγούμενο θα είδατε ότι παίρνει λίγη ώρα, αλλά αξίζει τον κόπο:
Μη σοκάρεστε, το αποτέλεσμα που έχουμε παραπάνω είναι εξαιρετικό! Παρατηρήστε τον κατακόρυφο άξονα και τις τιμές του. Είναι από 970 μέχρι 1030, που σημαίνει ότι όλες αυτές οι κλάσεις έχουν πολύ κοντινές μέσες συχνότητες εμφάνισης. Άρα, μπορούμε να πούμε ότι πετύχαμε, σε γενικές γραμμές, τον στόχο μας.
Ξεκινώντας από πολύ απλές ιδέες – πάρα πολύ απλές, θα λέγαμε – καταφέραμε και κατασκευάσαμε μία πειστική γεννήτρια ψευδοτυχαίων αριθμών. Στα επόμενα μέρη της σειράς θα κινηθούμε προς δύο άξονες:
θα εξερευνήσουμε κι άλλες μεθόδους να παράγουμε τυχαίους αριθμούς,
θα συζητήσουμε κι άλλα κριτήρια που θα θέλαμε να ικανοποιεί μία γεννήτρια ψευδοτυχαίων αριθμών, πέρα από την ιδιότητα της ισοκατανομής.
Η κεντρική εικόνα είναι ο πίνακας Γυναίκα με Phlox του Albert Gleizes.
Διαβάστε επίσης: Τι λέει το Θεώρημα του Bolzano;
Ακολουθήστε το aftermathsgr στα social media:
Μαθηματικός, μάλλον... Προβολή όλων των δημοσιεύσεων από Aftermaths
Previous Τεστάκι της ημέρας LXIII – Λύσεις
Next Τεστάκι της ημέρας LXIV (Α’ Λυκείου)
Ο/Η Τους μπεκρήδες κι αν δικάσουνε… – Aftermaths λέει:
30 Μαρτίου 2021 στο 14:40
[…] και τη δική μας γεννήτρια τυχαίων αριθμών που είδαμε εδώ. Στη συνέχεια ορίζουμε μία συνάρτηση η οποία δέχεται […]
Ο/Η Η στρατηγική δε μετράει πάντα… – Aftermaths λέει:
13 Απριλίου 2021 στο 01:20
[…] αριθμούς – θα μπορούσαμε να χρησιμοποιήσουμε και τη δική μας γεννήτρια ψευδοτυχαίων αριθμών, αλλά απλά θα γράφαμε περισσότερο κώδικα. Έπειτα, […]
Γράψτε το σχόλιο σας εδώ....
Εισάγετε τα παρακάτω στοιχεία ή επιλέξτε ένα εικονίδιο για να συνδεθείτε:
Ηλ. διεύθυνση (απαιτείται) Δεν θα εμφανιστεί δημόσια.
Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. ( Αποσύνδεση /  Αλλαγή )
Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. ( Αποσύνδεση /  Αλλαγή )
Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. ( Αποσύνδεση /  Αλλαγή )
Ειδοποίηση μέσω mail για νέα σχόλια.
Να ειδοποιούμαι μέσω mail για νέα άρθρα.
Ακολούθησε το ιστολόγιο μέσω email
Μαζί με 513 ακόμα followers
Η καλή πράξη της ημέρας
Τεστάκι της Ημέρας #001 - Τι θυμόμαστε από το Γυμνάσιο;
Ασκήσεις στις Συναρτήσεις (Β' Λυκείου)
Ασκήσεις στα Σύνολα - Α' Λυκείου
Ασκήσεις στους κανόνες παραγώγισης
Τι λέει το Θεώρημα του Bolzano;
10 Επαναληπτικά Θέματα - Γ' ΕΠΑΛ
Επανάληψη σε παραγοντοποίηση και ταυτότητες
Η υπερβατικότητα του π
5 Επαναληπτικά διαγωνίσματα (Γ' ΕΠΑΛ)
Ασκήσεις στη Σύνθεση (Λύσεις)
Αξίωμα της πληρότητας (6)
Τίποτα στην τύχη (1)
Τεστάκι της ημέρας (176)
The Wumpus Project (1)
1-1 After-maths Collatz featured Fermat Horner Tikz Workshop Α' Γυμνασίου Α' Λυκείου ΑΕΠΠ Απόψεις Β' Λυκείου Γ' λυκείου Διδακτικό υλικό ΕΟΚ ΕΠΑΛ ΘΜΤ Μαθηματικά Φυσική άλγεβρα ακρότατα αλγόριθμοι αμπελοφιλοσοφία ανισότητες ανισώσεις αποδείξεις απόλυτη τιμή ασκήσεις γραφική παράσταση δευτεροβάθμιες διάμεσος διαγώνισμα διακύμανση διασπορά διαφάνειες δομή επανάληψης δομή επιλογής δυνάμεις εισαγωγή εκθετική εξισώσεις επανάληψη θεωρία λογαριθμική λυμένα παραδείγματα λύσεις μέση τιμή μαθηματικά μονοτονία ολοκλήρωμα πίνακες πανελλήνιες παράγωγος παραμετρικές παραστάσεις πιθανότητες πολυώνυμα πράξεις πραγματικοί αριθμοί προβλήματα πρωτοβάθμιες πρόοδοι ρίζες σημειώσεις στατιστική συνέχεια συναρτήσεις συστήματα συχνοτήτων σύνολα τεστ τριγωνομετρία φύλλο εργασίας όρια
Buy me a tea!
Οι οπλές του αγριόγιδου είναι τα τέσσερα δάκτυλα του βιολιστή. Πάνε στα τυφλά και δε λαθεύουν ούτε χιλιοστό. Χυμούν σε γκρεμούς, παιχνιδιάρες στην ανηφοριά, ακροβάτες στην κατηφοριά, είναι καλλιτέχνες τσίρκου για το θεωρείο των βουνών. Οι οπλές του αγριόγιδου γαντζώνονται στον αέρα. Ο ρόζος τους, μικρό μαξιλαράκι, όποτε θέλει λειτουργεί σαν σιγαστήρας, διαφορετικά το χωρισμένο στα δυο νύχι είναι καστανιέτα για φλαμένκο. Οι οπλές του αγριόγιδου είναι τέσσερις άσσοι σε τσέπες χαρτοκλέφτη. Μ' εκείνες η βαρύτητα είναι μια παραλλαγή σ' ένα θέμα, όχι ένας νόμος.