Φύσα τα κεράκια

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

Γίνεσαι

και γιορτάζεις τα γενέθλιά σου με μια τούρτα που έχει πάνω της

κεριά.

Κάνεις μια ευχή και προσπαθείς να τα σβήσεις. Κάθε φορά που φυσάς όμως σβήνει μόνο ένας τυχαίος αριθμός κεριών, μεταξύ

του

και του αριθμού των κεριών που παραμένουν αναμμένα. Πόσες φορές, κατά μέσο όρο,

φυσάει την τούρτα γενεθλίων ο τριαντάρης;

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

Επαναφορά.

#3

Αν γράψουμε a_n

για τις αναμενόμενες φορές που χρειάζεται να φυσήξει, παίρνουμε την αναδρομική σχέση $a_n = 1 + \frac{1}{n}(a_1 + a_2 + \cdots + a_{n-1})$ με την αρχική συνθήκη a_1 = 1

. Επαγωγικά μπορεί να αποδειχθεί ότι $a_n = H_n = 1 + \frac{1}{2} + \cdots + \frac{1}{n}$ .

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

Demetres έγραψε: ↑
Τρί Ιουν 04, 2019 9:16 am
Αν γράψουμε για τις αναμενόμενες φορές που χρειάζεται να φυσήξει, παίρνουμε την αναδρομική σχέση $a_n = 1 + \frac{1}{n}(a_1 + a_2 + \cdots + a_{n-1})$ με την αρχική συνθήκη . Επαγωγικά μπορεί να αποδειχθεί ότι $a_n = H_n = 1 + \frac{1}{2} + \cdots + \frac{1}{n}$ .

Ωραία! Ας την γράψω λίγο πιο αναλυτικά. Την αναδρομική την έλυσα χωρίς επαγωγή.

Έστω T_i

(τυχαία μεταβλητή) ο χρόνος (αριθμός φυσημάτων) που υπολείπεται για να τερματιστεί η διαδικασία

όταν έχουν απομείνει στην τούρτα

κεράκια (

). Εμείς αναζητούμε την αναμενόμενη τιμή $E(T_{30})$ .

Από τη διατύπωση του προβλήματος εύκολα συνάγουμε τη σχέση

$E(T_{30})=1+\dfrac{1}{30}E(T_{1})+...+\dfrac{1}{30}E(T_{29}),E(T_1)=1,$
αφού οπωσδήποτε μία φορά χρειάζεται να φυσήξουμε και από εκεί και πέρα με πιθανότητα $\dfrac{1}{30}$

απομένει

κερί και χρόνος T_1

, με πιθανότητα $\dfrac{1}{30}$ απομένουν

κεριά

και χρόνος T_2

κ.ο.κ. .

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

$E(T_{n+1})-\dfrac{n}{n+1}E(T_{n})=\left (1+\dfrac{1}{n+1}\sum_{i=1}^{n}E(T_i) \right )-\dfrac{n}{n+1}\left (1+\dfrac{1}{n}\sum_{i=1}^{n-1}E(T_i) \right )$ $=1-\dfrac{n}{n+1}+\dfrac{1}{n+1}\left (\sum_{i=1}^{n}E(T_i)-\sum_{i=1}^{n-1}E(T_i) \right )=\dfrac{1}{n+1}+\dfrac{1}{n+1}E(T_n).$
Άρα $E(T_{n+1})-E(T_n)=\dfrac{1}{n+1}.$ Αθροίζοντας τις τελευταίες για k=1,2,...,n-1

παίρνουμε

$E(T_n)-E(T_1)=\dfrac{1}{2}+\dfrac{1}{3}+...+\dfrac{1}{n}$ και συνεπώς $E(T_n)=1+\dfrac{1}{2}+\dfrac{1}{3}+...+\dfrac{1}{n}$ .

Για n=30

βρίσκουμε $E(T_{30})\approx 3.99.$

Υ.Γ. Μπορούμε λοιπόν φυσώντας κεράκια να εκτιμήσουμε το $\ln n$ λαμβάνοντας υπόψη και τη σταθερά $\gamma .$

minageus · #5

Υ.Γ. Μπορούμε λοιπόν φυσώντας κεράκια να εκτιμήσουμε το \ln n λαμβάνοντας υπόψη και τη σταθερά \gamma .

Αναφέρεστε στην σταθερά Euler-Masceroni; Θα μπορούσατε να παραθέσετε κάποια ενδεικτική λύση;

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

minageus έγραψε: ↑
Τρί Ιουν 04, 2019 6:44 pm
Αναφέρεστε στην σταθερά Euler-Masceroni;

Ναι.

minageus έγραψε: ↑
Τρί Ιουν 04, 2019 6:44 pm
Θα μπορούσατε να παραθέσετε κάποια ενδεικτική λύση;

Χαριτολογώντας ισχυρίστηκα ότι μπορούμε να προσεγγίσουμε το $\ln n$ φυσώντας κεράκια.

Είναι γνωστό ότι $\displaystyle \lim_{n\rightarrow \infty }\left (\left ( 1+\frac{1}{2}+...+\frac{1}{n} \right )-\ln n-\gamma \right ) =0$

ή καλύτερα $\displaystyle\frac{1}{2(n+1)} <\left ( 1+\frac{1}{2}+...+\frac{1}{n} \right )-\ln n-\gamma<\frac{1}{2n}$

από την οποία παίρνουμε

$\displaystyle \left (1+\frac{1}{2}+...+\frac{1}{n} \right )-\frac{1}{2n}-\gamma <\ln n<\left (1+\frac{1}{2}+...+\frac{1}{n} \right )-\frac{1}{2(n+1)}-\gamma(\bigstar)$

Αν λοιπόν έχουμε ''πολλά'' κεράκια και θέλουμε να εκτιμήσουμε π.χ. το $\ln 30$ μπορούμε να φυσάμε

άδες και κάθε φορά να μετράμε πόσες φορές χρειάστηκε να φυσήξουμε. Μετά από ''πολλές'' κατεστραμμένες

άδες, παίρνοντας τον μέσο όρο των απαιτούμενων φυσιμάτων, αναμένουμε από τον Νόμο των Μεγάλων

Αριθμών να βρούμε αριθμό ''κοντά'' στην μέση τιμή που είναι $1+\dfrac{1}{2}+...+\dfrac{1}{n}.$ Συνυπολογίζοντας

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

εκτιμούμε το $\ln 30.$

Υ.Γ. Εντάξει δεν είναι και η καλύτερη προσέγγιση που μπορούμε να κάνουμε αφού μπορούμε να κάνουμε εκτίμηση

κατευθείαν από την $(\bigstar)$ αλλά σαν ιδέα καλή ακούγεται νομίζω.

Θυμίζει την προσέγγιση του $\pi$ πετώντας βελάκια σε στόχο ή την προσέγγιση του

από τον ελάχιστο

αριθμό ομοιόμορφων τ.μ. που πρέπει να αθροίσουμε μέχρι να ξεπεράσουμε το

Ούτως ή άλλως πολλά προβλήματα στα οποία η αναλυτική ή αριθμητική λύση είναι ανέφικτη η προσέγγιση μέσω

στοχαστικών πειραμάτων μας δίνει τη λύση.

minageus · #7

Λάμπρος Κατσάπας έγραψε: ↑
Τρί Ιουν 04, 2019 10:52 pm

minageus έγραψε: ↑
Τρί Ιουν 04, 2019 6:44 pm
Αναφέρεστε στην σταθερά Euler-Masceroni;
Ναι.

minageus έγραψε: ↑
Τρί Ιουν 04, 2019 6:44 pm
Θα μπορούσατε να παραθέσετε κάποια ενδεικτική λύση;
Χαριτολογώντας ισχυρίστηκα ότι μπορούμε να προσεγγίσουμε το $\ln n$ φυσώντας κεράκια.

Είναι γνωστό ότι $\displaystyle \lim_{n\rightarrow \infty }\left (\left ( 1+\frac{1}{2}+...+\frac{1}{n} \right )-\ln n-\gamma \right ) =0$

ή καλύτερα $\displaystyle\frac{1}{2(n+1)} <\left ( 1+\frac{1}{2}+...+\frac{1}{n} \right )-\ln n-\gamma<\frac{1}{2n}$

από την οποία παίρνουμε

$\displaystyle \left (1+\frac{1}{2}+...+\frac{1}{n} \right )-\frac{1}{2n}-\gamma <\ln n<\left (1+\frac{1}{2}+...+\frac{1}{n} \right )-\frac{1}{2(n+1)}-\gamma(\bigstar)$

Αν λοιπόν έχουμε ''πολλά'' κεράκια και θέλουμε να εκτιμήσουμε π.χ. το $\ln 30$ μπορούμε να φυσάμε

άδες και κάθε φορά να μετράμε πόσες φορές χρειάστηκε να φυσήξουμε. Μετά από ''πολλές'' κατεστραμμένες

άδες, παίρνοντας τον μέσο όρο των απαιτούμενων φυσιμάτων, αναμένουμε από τον Νόμο των Μεγάλων

Αριθμών να βρούμε αριθμό ''κοντά'' στην μέση τιμή που είναι $1+\dfrac{1}{2}+...+\dfrac{1}{n}.$ Συνυπολογίζοντας

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

εκτιμούμε το $\ln 30.$

Υ.Γ. Εντάξει δεν είναι και η καλύτερη προσέγγιση που μπορούμε να κάνουμε αφού μπορούμε να κάνουμε εκτίμηση

κατευθείαν από την $(\bigstar)$ αλλά σαν ιδέα καλή ακούγεται νομίζω.

Θυμίζει την προσέγγιση του $\pi$ πετώντας βελάκια σε στόχο ή την προσέγγιση του από τον ελάχιστο

αριθμό ομοιόμορφων τ.μ. που πρέπει να αθροίσουμε μέχρι να ξεπεράσουμε το

Ούτως ή άλλως πολλά προβλήματα στα οποία η αναλυτική ή αριθμητική λύση είναι ανέφικτη η προσέγγιση μέσω

στοχαστικών πειραμάτων μας δίνει τη λύση.

Ενδιαφέρον. Ευχαριστώ πολύ ,το πρόβλημα αυτό είναι έναυσμα για μένα για περαιτερω μελετη και αναζητηση!

Φύσα τα κεράκια

Φύσα τα κεράκια

Re: Φύσα τα κεράκια

Re: Φύσα τα κεράκια

Re: Φύσα τα κεράκια

Re: Φύσα τα κεράκια

Re: Φύσα τα κεράκια

Re: Φύσα τα κεράκια

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