Προβλήματα Μαθηματικών

Απρίλιος 25, 2011

Στοίχημα

Filed under: Λυμένα Προβλήματα,Με επιπλέον ερωτήματα — Michalis Loulakis @ 6:46 μμ

Ένας φοιτητής έχει 1 ευρώ και χρειάζεται να συγκεντρώσει 1000 ευρώ για να πάει διακοπές. Αποφασίζει να στοιχηματίσει παίζοντας κορώνα-γράμματα με ένα τίμιο νόμισμα, όπου σε κάθε γύρο θα διπλασιάζει το ποντάρισμά του αν προβλέψει σωστά το αποτέλεσμα του στριψίματος  και θα χάνει το ποντάρισμά του αν προβλέψει λάθος. Έχει αποφασίσει να παίζει μέχρι είτε να χάσει όλα του τα χρήματα είτε να συγκεντρώσει τα 1000 ευρώ. Μπορεί σε κάθε γύρο να στοιχηματίσει οποιοδήποτε ακέραιο ποσό σε ευρώ που δεν ξεπερνά την τρέχουσα περιουσία του, αλλά αναρωτιέται αν υπάρχει στρατηγική που θα μεγιστοποιήσει την πιθανότητα να φτάσει τα 1000 ευρώ. Δείξτε ότι η πιθανότητα αυτή είναι το πολύ 1/1000 και βρείτε μια στρατηγική που του εξασφαλίζει αυτήν την πιθανότητα.

Advertisements

10 Σχόλια »

  1. Έστω Χ(t) η τυχαία μεταβλητή όπου: Χ(1)=1 αν ο φοιτητής κερδίσει και Χ(1)=0 αν ο φοιτητής χάσει τα χρήματά του στη στιγμή ένα (t=1). Ομοίως και για τις άλλες χρον. στιγμές…Η πιθανότητα να κερδίσει είναι P(Χ(t)=1)=1/2 για κάθε t=1,2,3,4,5,…και να χάσει P(Χ(t)=0)=1/2 για κάθε t=1,2,3,4,5,…αφού το νόμισμα είναι αμερόληπτο.
    ‘Εχουμε δηλ. κάποια μαρκοβιανή διαδικασία αφού το να κερδίσει ο φοιτητής τα 1000€ εξαρτάται από το αμέσως προηγούμενο ποσό που διαθέτει και ποντάρει σύμφωνα μ’ αυτό.
    Τώρα χρειαζόμαστε έναν αναδρομικό τύπο που προσφέρει τη βέλτιστη λύση και φυσικά την βελτ. στρατηγική.
    Χρησιμοποιούμε την προς τα πίσω μέθοδο…

    Μου αρέσει!

    Σχόλιο από zf1986 — Απρίλιος 27, 2011 @ 7:55 μμ

  2. Η περιουσία του φοιτητή είναι μαρκοβιανή αλυσίδα- τι εννοείς με το «χρησιμοποιούμε την προς τα πίσω μέθοδο»;

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Απρίλιος 28, 2011 @ 3:40 μμ

  3. Έστω F_t η περιουσία του φοιτητή τη στιγμή t.
    Αν την επόμενη στιγμή ποντάρει 0 < b
    Έστω επίσης T η χρονική στιγμή κατά την οποία ο φοιτητής
    σταματά να παίζει. Από martingale stopping έχουμε επιπλέον ότι \mathbb{E}[F_T] = 1 .

    Η επόμενη παρατήρηση ειναι ότι το παιχνίδι σταματά αν και μόνον αν ο φοιτητής
    έχει περιουσία 0 ή τουλάχιστον 1000 ευρώ. Έστω p η πιθανότητα να έχει 0 ευρώ, q η
    πιθανότητα να έχει τουλάχιστον 1000, έστω 1000+s.
    Αφού η αναμενόμενη περιουσία του είναι 1, έχουμε
    1 = 0 \cdot p + (1000 + s) \cdot q \; , s \geq 0 άρα q \leq 1/1000 .
    Αυτό δείχνει ότι η πιθανότητα να πάει διακοπές είναι το πολύ 1/1000
    και q = 1/1000 αν και μόνο αν s=0, δηλαδή μια στρατηγική είναι βέλτιστη
    αν και μόνο αν αποφεύγει την περίπτωση ο φοιτητής να τελειώσει με
    περισσότερα από 1000 ευρώ.

    Μου αρέσει!

    Σχόλιο από henk&christos — Μαΐου 4, 2011 @ 4:16 μμ

  4. ‘Έφαγε’ κάποιες αράδες στη 2η γραμμή..

    Αν την επόμενη στιγμή ποντάρει 0 < b \leq F_t ευρώ, τότε
    \mathbb{E}[F_{t+1}] = 1/2 (F_t - b) + 1/2 (F_t + b) = F_t
    που δείχνει ότι η ακολουθία F_t είναι martingale και άρα
    \mathbb{E}[F_t] = F_0 = 1 .

    Μου αρέσει!

    Σχόλιο από henk&christos — Μαΐου 4, 2011 @ 4:41 μμ

  5. Το άνω σχόλιο δεν είναι εντελώς σωστό. Θα έπρεπε να είχα γράψει
    \mathbb{E}[F_{t+1} | F_t] = \ldots = F_t .

    Από τα άνω (αν δεν στερούνται νοήματος) προκύπτει ότι μια στρατηγική
    που εξασφαλίζει αυτή την πιθανότητα είναι, π.χ. να ποντάρει 1 ευρώ κάθε φορά.
    Επίσης μια άλλη είναι να ποντάρει όλη του την περιουσία, αν αυτη είναι μικρότερη από 500 ευρώ
    και τη διαφορά αυτής από τα 1000 ευρώ, αν είναι μεγαλύτερη από 500.

    Έχει νόημα να ψάξουμε για τη βέλτιστη στρατηγική που είναι συγχρόνως και η πιο ‘γρήγορή’ ;

    Μου αρέσει!

    Σχόλιο από henk&christos — Μαΐου 4, 2011 @ 6:17 μμ

  6. Κατά βάση είναι σωστά αυτά που γράφεις. Βέβαια θα πρέπει να λάβει κανείς υπ’ όψιν ότι το ποσό του στοιχήματος μπορεί να εξαρτάται από ό,τι έχει γίνει στο παρελθόν, αλλά και πάλι η F_t είναι martingale. Επίσης για να εφαρμόσεις το θεώρημα επιλεκτικής στάσης χρειάζεται ο χρόνος στάσης να είναι φραγμένος. Για να δικαιολογήθει το επιχείρημά σου μπορούμε να πάρουμε -κλασικά- τον T\wedge N και να αφήσουμε το N\to\infty χρησιμοποιώντας ότι 0\le F_t\le 1000.

    Υπάρχει όμως κι ένας φαινομενικά πιο στοιχειώδης τρόπος. Αν ορίσουμε P(x) την πιθανότητα νίκης που δίνει η βέλτιστη στρατηγική με αρχικό κεφάλαιο x, τότε έχουμε \displaystyle P(x)=\max_{1\le b\le x} \frac{P(x+b)+P(x-b)}{2}. Από αυτό μπορεί κανείς να δει ότι η P(x)-x/1000 λαμβάνει την ελάχιστη και μέγιστη τιμή της στο \{0,1000\} και επειδή P(0)=0, P(1000)=1, βρίσκει κανείς τελικά ότι P(x)= x/1000. Στην ουσία αυτός ο τρόπος δεν είναι διαφορετικός από τη δική σου λύση- υπάρχει μια αναλογία ανάμεσα στις ιδιότητες των (super)martingale και των (υπερ)αρμονικών συναρτήσεων!

    Τελικά, οποιαδήποτε στρατηγική δίνει την ίδια πιθανότητα, αρκεί να μην ποντάρεις πάνω από αυτά που χρειάζεσαι για να συμπληρώσεις τα 1000, και φυσικά η ερώτησή σου έχει πολύ νόημα. Αλλά αυτό ας είναι το αντικείμενο του επόμενου προβλήματος!

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Μαΐου 5, 2011 @ 7:46 μμ

  7. Στην περίπτωση που το νόμισμα δεν είναι τίμιο και η πιθανότητα να έρθει κορώνα »αλλάζει» σε κάθε ρίψη ακολουθώντας την ομοιόμορφη κατανομή .Δηλαδή στην i ρίψη η πιθανότητα να έρθει κορώνα είναι pi~U(0,1).Υπάρχει πολιτική ώστε να μεγιστοποιηθεί η πιθανότητα και ποια είναι αυτή η πιθανότητα ?

    Μου αρέσει!

    Σχόλιο από xar7 — Μαΐου 26, 2011 @ 2:25 πμ

  8. Αν οι p_i είναι ανεξάρτητες μεταξύ τους και από τα προηγούμενα αποτελέσματα τότε η πιθανότητα είναι ίδια, όπως και οι πολιτικές που την επιτυγχάνουν. Αυτό συμβαίνει γιατί και πάλι η F_n είναι martingale. Θα είχε όμως ενδιαφέρον αν οι πιθανότητες p_i ήταν ίδιες μεταξύ τους, αλλά άγνωστες σε εμάς. Σ’ αυτήν την περίπτωση τα προηγούμενα αποτελέσματα έχουν μια πληροφορία για την τιμή του p που μπορεί να είναι χρήσιμη. Πριν από αυτό όμως θα πρέπει να βρούμε τη βέλτιστη στρατηγική για δεδομένο p\neq 1/2– το επόμενο ερώτημα υποδεικνύει ότι αν p\ll 1/2 είναι καλύτερα να είναι κανείς επιθετικός, ενώ αν p\gg 1/2 είναι καλύτερα να είναι συντηρητικός. Το να βρει κανείς όμως τη βέλτιστη στρατηγική μάλλον είναι δύσκολο αναλυτικά.

    Νέο ερώτημα
    Αν p\neq 1/2 υπολογίστε την πιθανότητα να φτάσει τα 1000 ευρώ για τις δύο ακραίες στρατηγικές: 1. αν ποντάρει 1 ευρώ σε κάθε γύρο και 2. αν ποντάρει όσα χρειάζεται για να φτάσει τα 1000 ευρώ αν αυτό είναι δυνατόν και όλα διαφορετικά.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Μαΐου 26, 2011 @ 4:12 πμ

  9. Κάτι μου διαφεύγει..
    Ο φοιτητής ποντάρει κάθε φορά στο αποτέλεσμα του στριψίματος.
    Αυτό δε σημαίνει αναγκαστικά ότι έχει σταθεροποιήσει το αποτέλεσμα
    στο οποιο ποντάρει. Μπορεί να επιλέξει να ποντάρει σε κορώνα, μπορεί
    σε γράμματα.
    Αυτή την επιλογή την κάνει με κάποια πιθανότητα ;
    Αν αυτή η πιθανότητα είναι 1/2, νομίζω πως και πάλι η F_t είναι martingale.

    Μου αρέσει!

    Σχόλιο από henk&christos — Μαΐου 30, 2011 @ 7:30 μμ

  10. Mea culpa. Όταν έγραφα p\neq 1/2, είχα στο νου μου εγκαταλείψει το κορώνα/γράμματα. Το νέο ερώτημα ας αφορά ένα παιχνίδι όπου η πιθανότητα νίκης του φοιτητή είναι p, και κερδίζει ή χάνει ένα ποσό ίσο με το ποντάρισμά του, όπως π.χ. αν παίζει μαύρο/κόκκινο στη ρουλέτα, όπου p=18/37.

    Στην περίπτωση του νομίσματος τώρα, πράγματι αν διαλέγει στην τύχη αν θα ποντάρει σε κορώνα ή σε γράμματα τότε όπως λες η F_t είναι martingale ακόμα και αν p\neq 1/2, και η πιθανότητα νίκης του είναι 1/1000. Μόνο που δεν θα ήθελε να διαλέγει στην τύχη! Να μια καλύτερη στρατηγική της οποίας η πιθανότητα νίκης υπολογίζεται εύκολα: Ποντάρει γύρο πάρα γύρο, και όταν ποντάρει βάζει 1 ευρώ στην όψη που ήρθε στον αμέσως προηγούμενο γύρο (που δεν πόνταρε.) Δεν είναι δύσκολο να δει κανείς ότι με αυτήν τη στρατηγική είναι σαν να ποντάρει 1 ευρώ σε κάθε γύρο ενός παιχνιδιού με πιθανότητα νίκης p^2+(1-p)^2>1/2. Και όπως θα δείτε αν κάνετε το νέο ερώτημα, η πιθανότητα νίκης με αυτή τη στρατηγική είναι > 1/1000.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Μαΐου 30, 2011 @ 9:36 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Blog στο WordPress.com.

Αρέσει σε %d bloggers: