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

Αύγουστος 19, 2010

Ατέλειωτος περίπατος

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

Στις κορυφές του \mathbb{Z}^2 τοποθετούμε με πιθανότητα p μια μπαταρία, ανεξάρτητα για διαφορετικές κορυφές. Ένα ρομπότ ξεκινά από την αρχή των αξόνων με μια μπαταρία που επαρκεί για να διανύσει απόσταση ακριβώς 1, και ένα χάρτη με τις κορυφές όπου υπάρχει μπαταρία. Αν στην κορυφή που θα μεταβεί βρει μια μπαταρία μπορεί να συνεχίσει τον περίπατό του για ακόμα ένα βήμα. Δείξτε ότι υπάρχει ένα p_*>0, τέτοιο ώστε αν p<p_* ο περίπατος του ρομπότ θα τελειώσει σε πεπερασμένο χρόνο με πιθανότητα 1.

Advertisements

3 Σχόλια »

  1. Έστω W_p η πιθανότητα να υπάρχει ατέλειωτος περίπατος
    όταν τοποθετούνται μπαταρίες με πιθανότητα p.
    Έστω p_1  p δεν τοποθετούμε.
    Αν X_n \leq p_1 τότε θα ισχύει επίσης X_n \leq p_2 που σημαίνει πως
    W_p είναι αύξουσα συνάρτηση του p.
    Το ζητούμενο p_{\ast} είναι το
    p_{\ast} := \inf \{p\in [0,1] : W_p > 0 \} ,
    είναι καλά ορισμένο (λόγω μονοτονίας) και μένει να δείξουμε ότι p_{\ast}>0.
    Θα δείξουμε ότι p_{\ast}\geq 1/3, δηλαδή ότι W_p=0, για p\in [0,1/3).
    Αρχικά παρατηρούμε ότι η πιθανότητα να ακολουθήσει περίπατο μήκους n είναι p^n.
    Επίσης το πλήθος των (διαφορετικών) περιπάτων μήκους n είναι το πολύ 4\cdot 3^{n-1}.
    Αυτό γιατί το ρομπότ δεν κάνει ‘όπισθεν’.
    Συνεπώς ο μέσος αριθμός περιπάτων μήκους n, \mathbb{E}_n, του ρομπότ είναι το πολύ
    4 \cdot 3^{n-1}\cdot p^n.
    Άν p < 1/3, τότε \mathbb{E}_n \rightarrow 0, καθώς n \rightarrow \infty.
    Οπότε,
    W_p \leq \mathbb{P}[ο αριθμός περιπάτων μήκους n είναι \geq 1] \leq  \mathbb{E}_n \rightarrow 0,
    λόγω της ανισότητας Markov.

    Μου αρέσει!

    Σχόλιο από henk&christos — Νοέμβριος 10, 2010 @ 3:08 μμ

  2. Πολύ σωστά. Αν και το επιχείρημά σου για τη μονοτονία δεν είναι απολύτως σαφές,
    η απόδειξη γιαυτό το κομμάτι έχει στην ουσία δοθεί στο πρόβλημα «αποδείξτε το προφανές«.

    Νέο ερώτημα
    Μπορείτε να δείξετε ότι p_\ast <1;

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Νοέμβριος 16, 2010 @ 1:31 μμ

  3. Το κείμενο δεν εμφανίστηκε ολοκληρο και το κομμάτι που λείπει στην 3η γραμμή
    είναι στην ουσία ‘κλοπή’ της ιδεας του Μιχάλη Κουλουντζάκη από το σχόλιο 2
    του προβλήματος ‘Αποδειξτε το προφανές’.
    Σε κάθε κορυφή, v ρίχνουμε ανεξάρτητη και ομοιόμορφη τυχαία μεταβλητή, X_v,
    με τιμές στο [0,1].
    Αν X_v \leq p τοποθετούμε μπαταρία, αλλιώς δεν τοποθετούμε.
    Τα p_1, p_2 είναι τέτοια ώστε p_1 \leq p_2.

    Μου αρέσει!

    Σχόλιο από henk&christos — Νοέμβριος 17, 2010 @ 8:50 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

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