Υπολογισμός πιθανότητας

#1

Διαβάζοντας το ενδιαφέρον βιβλίο του Marcus De Sautoy "Τα must-ήρια των αριθμών" μου κέντρισε το ενδιαφέρον
το παρακάτω πρόβλημα:

"Ρίχνουμε ένα κέρμα δέκα φορές. Ποιά είναι η πιθανότητα να φέρω τρείς συνεχόμενες φορές κεφάλι ή γράμματα;"

Η λύση που είδα χρησιμοποιεί τους αριθμούς Φιμπονάτσι.

Μήπως υπάρχει κάτι καλύτερο και πιο κοντά στη συνδυαστική;

Ευχαριστώ εκ των προτέρων.

Λάμπρος Κατσάπας · #2

Χρήστο θα ήθελα να δω τη λύση που λες. Αν έχεις χρόνο γράψ'την. Θα επιχειρήσω εδώ μια λύση με κατασκευή αναδρομικής εξίσωσης. Προφανώς θα υπάρχει και τρόπος με θεωρία μαρκοβιανών αλυσίδων. Επίσης, θα υπολογίσω την πιθανότητα ''τουλάχιστον'' τρεις συνεχόμενες κορώνες σε δέκα ρίψεις (ίδια είναι προφανώς και για γράμματα). Φαντάζομαι αυτό ζητάς.

Έστω $A_{n,m}$ το ενδεχόμενο σε

ρίψεις να εμφανιστούν τουλάχιστον

συνεχόμενες κορώνες $(m\leq n))$ . Παρατηρούμε ότι το ενδεχόμενο αυτό μπορεί να συμβεί με δύο τρόπους:

(1)Στις πρώτες n-1

ρίψεις να εμφανιστούν τουλάχιστον

συνεχόμενες κορώνες (δηλαδή το ενδεχόμενο να έχει πραγματοποιηθεί πριν την τελευταία ρίψη). Σε αυτή την περίπτωση, έχουμε δύο περιπτώσεις για την τελευταία ρίψη, κορώνα

ή γράμματα

.

(2) Στις πρώτες n-1

ρίψεις δεν έχει εμφανιστεί η ακολουθία KKK...K (m-times)

. Τότε αναγκαστικά θα πρέπει στις τελευταίες m+1

θέσεις να προκύψει η ακολουθία GKKK...K

(ενδεχόμενο

). Οι υπόλοιπες n-m-1

αρχικές θέσεις μπορεί καταληφθούν από οποιοδήποτε γράμμα, δηλαδή έχουμε $2^{n-m-1}$ μεταθέσεις.

Αν με N(A)

συμβολίσουμε το πλήθος των ευνοϊκών περιπτώσεων του ενδεχομένου

τότε από την παραπάνω ανάλυση προκύπτει ότι:
$\displaystyle{N(A_{n,m})=2N(A_{n-1,m})+N(A_{n-1,m}^{c}\cap B) (1) }$ Όμως $\displaystyle{N(A_{n-1,m}^{c}\cap B)=N(A_{n-m-1,m}^{c}\cap B)=N( B)-N(A_{n-m-1,m})= 2^{n-m-1}-N(A_{n-m-1,m}) (2)}$ H (1)

με τη βοήθεια της (2)

γίνεται:
$\displaystyle{ N(A_{n,m})=2N(A_{n-1,m})-N(A_{n-m-1,m})+ 2^{n-m-1}. }$ Εμείς θέλουμε το $A_{10,3}$ . Έχοντας κατά νου ότι $N(A_{n,m})=1$ για n=m

και $N(A_{n,m})=0$ για n<m

, ξεκινώντας από το $N(A_{4,3})$ και προχωρώντας προς τα πάνω (με το χέρι οι πράξεις, τα νούμερα δεν είναι απαγορευτικά) βρίσκουμε τελικά ότι $N(A_{10,3})=520$ . Επίσης, το πλήθος των δυνατών περιπτώσεων είναι προφανώς $2^{10}$ και τελικά η ζητούμενη πιθανότητα είναι $\frac{520}{2^{10}}\approx 0.507813$

#3

Xρήστο, φαντάζομαι είδες την πιο κάτω λύση. Αν ναι τότε είναι συνδυαστική:

Θα μετρήσουμε πόσες ακολουθίες από

κορώνες/γράμματα δεν περιέχουν τρεις συνεχόμενες κορώνες ή τρία συνεχόμενα γράμματα. Έστω a_n

το πλήθος αυτών των ακολουθιών, τις οποίες θα ονομάζουμε καλές.

Ασφαλώς είναι a_1 = 2, a_2 = 4

. Θα βρούμε αναδρομικό τύπο για το a_n

:

Υπάρχουν $a_{n-2}$ καλές ακολουθίες από

κορώνες/γράμματα οι οποίες λήγουν σε ΚΚ ή ΓΓ. Πράγματι, κάθε τέτοια ακολουθία δίνει μια καλή ακολουθία από n-2

κορώνες/γράμματα αγνοώντας τις τελευταίες δύο ρίψεις. Αντιστρόφως, κάθε καλή ακολουθία από n-2

κορώνες/γράμματα μπορεί να επεκταθεί σε μοναδική καλή ακολουθία από

κορώνες/γράμματα η οποία λήγει σε ΚΚ ή ΓΓ. Πράγματι αν η καλή ακολουθία των n-2

ρίψεων λήγει σε Κ, πρέπει στις επόμενες δύο ρίψεις να έχουμε ΓΓ. Αν λήγει σε Γ, πρέπει να έχουμε ΚΚ.

Υπάρχουν $a_{n-1}$ καλές ακολουθίες από

κορώνες/γράμματα οι οποίες λήγουν σε ΓΚ ή ΚΓ. Πράγματι η αντιστοιχία με τις καλές ακολουθίες από n-1

κορώνες/γράμματα που παίρνουμε αν αφαιρέσουμε την τελευταία ρίψη είναι 1-1.

Άρα $a_{n} = a_{n-1} + a_{n-2}$ για $n \geqslant 3$ . Παρατηρώντας τώρα ότι a_1 = 2F_2

και

καταλήγουμε στο ότι $a_{10} = 2F_{11} = 2 \cdot 144 = 288$ . (Μπορούμε βέβαια να μην χρησιμοποιήσουμε την παρατήρηση αλλά τον αναδρομικό τύπο για να βρούμε a_3 = 2+4=6, a_4 = 6+4=10

, κ.τ.λ.)

Άρα η πιθανότητα να φέρουμε (τουλάχιστον) τρεις συνεχόμενες φορές κορώνα ή γράμματα ισούται με

$\displaystyle{ 1 - \frac{288}{1024} = \frac{23}{32} = 0.71875}$

Επεξεργασία: Είναι $F_{11} = 89$ οπότε η σωστή τελική απάντηση είναι

$\displaystyle{ 1 - \frac{178}{1024} = \frac{423}{512} = 0.826171875}$

Λάμπρος Κατσάπας · #4

Να σημειώσω ότι το δικό μου αποτέλεσμα αφορούσε την πιθανότητα ''τουλάχιστον'' τρεις συνεχόμενες κορώνες σε δέκα ρίψεις . Το αποτέλεσμα συμβαδίζει και με μια Monte Carlo προσομοίωση που έκανα στο mathematica. Ο κώδικας:

Κώδικας: Επιλογή όλων

n = 100000;(*πλήθος πειραμάτων*)
times = 0;(*πλήθος επιτυχιών στα n πειράματα*)

Do[
     
state = 0;  (*Η μεταβλητή state (κατάσταση) μετρά πόσες διαδοχικές κορώνες έχουμε φέρει μέχρι στιγμής.Αν ξεκινώντας το πείραμα έρθει κορώνα τότε η κατάσταση είναι 1,αν στην επόμενη έρθει πάλι κορώνα τότε η κατάσταση είναι 2 κ.ο.κ.*)
 i = 0;
 While[
           
state < 3 && i < 10,
            
 p = Random[];
           (*Παράγουμε έναν τυχαίο αριθμό στο (0,1)*)
  
           i++;
  
           If[p < 1/2, state++, state = 0]
           (*Με πιθανότητα 1/2 έρχεται κορώνα και αυξάνεται κατά 1 η state. Διαφορετικά πάμε σε κατάσταση 0*)

           ]
           
If[state == 3, times++]
 (*Αν στο τέλος των 10 ρίψεων ή και πιο νωρίς η κατάσταση state έχει χτυπήσει 3 τότε το ενδεχόμενο έχει εμφανιστεί και αυξάνουμε τη  μεταβλητή times κατά 1*)

, {n}]
          

Print[N[times/n]]
0.50725

Λάμπρος Κατσάπας · #5

Ως προς το δεύτερο αποτέλεσμα που παρουσιάστηκε έχω αμφιβολίες. Μια προσομοίωση δίνει περίπου 10% μεγαλύτερη πιθανότητα. Επίσης Χρήστο θα πρέπει να ξεκαθαριστεί αν θέλουμε τρεις τουλάχιστον ή τρεις ακριβώς. Ο κώδικας:

Κώδικας: Επιλογή όλων

n = 10000;(*πλήθος πειραμάτων*)
times = 0;(*πλήθος επιτυχιών στα n πειράματα*)
Do[

state1 = 0; 
state2 = 0;
 (*Η μεταβλητή state1 μετρά πόσες διαδοχικές κορώνες έχουμε φέρει μέχρι στιγμής.Αν ξεκινώντας το πείραμα έρθει κορώνα τότε η κατάσταση είναι 1,αν στην επόμενη έρθει πάλι κορώνα τότε η κατάσταση είναι 2 κ.ο.κ. .Όμοια για τη μεταβλητή state2 για τα γράμματα*)

i = 0;
 
While[

state1 < 3 && state2 < 3 && i < 10, 
p = Random[];
(*Παράγουμε έναν τυχαίο αριθμό στο (0,1)*)i++;
  
 If[p < 1/2, (state1++) && (state2 = 0), (state1 = 0) && (state2++)]
   (*Με πιθανότητα 1/2 έρχεται κορώνα και αυξάνεται κατά 1 η state1 και μηδενίζεται η state2*)
   (*Με πιθανότητα 1/2 έρχεται γράμματα και αυξάνεται κατά 1 η state2 και μηδενίζεται η state1*)] 

If[state1 == 3 || state2 == 3, times++], {n}]
(*Αν στο τέλος των 10 ρίψεων ή και πιο νωρίς κάποια από τις καταστάσεις έχει χτυπήσει 3 τότε το ενδεχόμενο έχει εμφανιστεί και αυξάνουμε τη μεταβλητή times κατά 1*)

Print[N[times/n]]
0.8272

#6

Λάμπρος Κατσάπας έγραψε:Ως προς το δεύτερο αποτέλεσμα που παρουσιάστηκε έχω αμφιβολίες.

Η αναδρομική σχέση ήταν σωστή, μόνο που βρήκα το $a_{11} = F_{12}$ αντί το $a_{10} = F_{11}$ . Η σωστή απάντηση είναι

$\displaystyle{ 1 - \frac{178}{1024} = 0.826171875}$

που είναι κοντά στο αποτέλεσμα της προσομοίωσης. Θα το διορθώσω.

Παρεμπιπτόντως, έβαλα τον κώδικά σας μέσα σε πλαίσιο κώδικα.

#7

Καλησπέρα Λάμπρο και Δημήτρη!
Τι μου επαναφέρατε στη μνήμη,,,Αυτό το βιβλίο το διάβαζα λίγο πριν πάρω μετάθεση από τη Χάλκη.
Τότε είχα κάνει ένα βήμα στη συνδυαστική. Αυτό όμως με το πέρασμα του καιρού...σκούριασε!
Θα το ψάξω και θα γράψω ότι ζητήσατε. Αρκεί να το βρω!
Ευχαριστώ για την ένασχόληση
(για να είμαι ειλικρινής είχα ξεχάσει πως είχε μείνει αναπάντητο)

Υπολογισμός πιθανότητας

Υπολογισμός πιθανότητας

Re: Υπολογισμός πιθανότητας

Re: Υπολογισμός πιθανότητας

Re: Υπολογισμός πιθανότητας

Re: Υπολογισμός πιθανότητας

Re: Υπολογισμός πιθανότητας

Re: Υπολογισμός πιθανότητας

Μέλη σε σύνδεση