Στοχαστικές Διεργασίες (Νέο) (ΤΜΑ247)

Οι φάσεις της ζωής ενός πλαστικού αντικειμένου είναι οι εξής:

1 = production, 2 = use, 3 = recycling, 4 = discard, 5 = incineration.

Μελετώντας τα ιστορικά στοιχεία παραγωγής και ανακύκλωσης είναι δυνατό να καταγράψουμε τον πίνακα μετάβασης μεταξύ των 5 καταστάσεων. Ο βασικός πίνακας Ν περιέχει το μέσο πλήθος επισκέψεων στις καταστάσεις 1, 2, 3 πριν την απορρόφησή του συστήματος στις καταστάσεις 4, 5.

Ο αρθρογράφος, ξεκινώντας από την πληροφορία πως το έτος 2015 παράχθηκαν 407 Mt πλαστικού, συμπεραίνει (μεταξύ άλλων) ότι μέχρι την τελική απόρριψη ή αποτέφρωσή τους, θα ανακυκλωθούν 42.84 Mt και θα χρησιμοποιηθούν 635.49 Mt.

Αν P είναι ο πίνακας τυχαίας μετάβασης μεταξύ των ιστοσελίδων του διαδικτύου, τότε η στάσιμη κατανομή πP = P, περιγράφει την πιθανότητα τελικής μετάβασης σε κάποια ιστοσελίδα. Ωστόσο, το διαδύκτιο δεν είναι αδιαχώριστη αλυσίδα και ως εκ τούτου δεν υπάρχει πάντα στάσιμη τελική κατανομή. Οι Larry Page και  Sergey Brin έλυσαν το πρόβλημα αυτό κάνοντας τις εξής δύο παραδοχές:

1. Μία ιστοσελίδα απορρόφησης (δηλαδή μία σελίδα χωρίς κανένα σύνδεσμο προς άλλη σελίδα) στέλνει τον χρήστη με ισοπίθανο τρόπο σε όλες τις υπόλοιπες. Ισοδύναμα, στη θέση της στήλης που αντιστοιχεί στην απορροφητική κατάσταση μπαίνει η στήλη [1/n].

2. Από κάθε ιστοσελίδα, υπάρχει μία πιθανότητα ο χρήστης να επιλέξει με τυχαίο τρόπο τη μετάβαση του κάπου αλλού και να μην ακολουθήσει κάποιο σύνδεσμο της σελίδας. Ισοδύναμα στη θέση του πίνακα μετάβασης P, θεωρείται ο πίνακας P' = d*P + (1-d)*Kn, όπου Kn = [1/n].

Με τις παραπάνω παραδοχές υπάρχει πάντα στάσιμη κατανομή, η οποία δείχνει τη σημαντικότητα κάθε ενός κόμβου. Στην παραπάνω διαδικασία βασίζεται ο αλγόριθμος αναζήτησης της Google.