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

Οκτώβριος 4, 2010

Αποδείξτε το προφανές

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 12:00 πμ

Σε ένα N\times N πίνακα από κουκίδες όλες οι κουκίδες είναι αρχικά ενωμένες με τις 4 γειτονικές τους με ακμές (εκτός από αυτές που είναι στα σύνορα οι οποίες ενώνονται με λιγότερες). Για κάθε μια από τις ακμές που υπάρχουν στην αρχή ρίχνουμε ανεξάρτητα ένα νόμισμα που έρχεται κορώνα με πιθανότητα p, ίδια για όλες τις ακμές, και αν το νόμισμα έρθει γράμματα σβήνουμε την ακμή.

Θεωρείστε το ενδεχόμενο E μετά από τις διαγραφές ακμών να υπάρχει μονοπάτι που ξεκινάει από κάποια κουκίδα της αριστερής μεριάς και καταλήγει σε κάποια κουκίδα της δεξιάς μεριάς του πίνακα (το μονοπάτι αποτελείται από ακμές που δε σβήστηκαν).

Αποδείξτε ότι η πιθανότητα του E είναι αύξουσα συνάρτηση του p.

Advertisements

2 Σχόλια »

  1. Έστω M_{p} η πιθανότητα να υπάρχει τέτοιο μονοπάτι.
    Έστω p_{1} < p_{2}.
    Τότε p_{1} = p_{2} \frac{p_{1}}{p_{2}} και p_{1} /p_{2}<1.
    Ξεκινούμε κρατώντας κάθε ακμή με πιθανοτητα p_{2}.
    Στο γράφημα που προκύπτει, επαναλαμβάνουμε τη διαδικασία κρατώντας
    κάθε ακμή με πιθανοτητα p_{1} /p_{2}.
    Το τελικό γράφημα μπορεί να θεωρηθεί σαν να έχει δημιουργηθεί ριχνοντας
    νόμισμα που έρχεται κορώνα με πιθανότητα p_{1}, λόγω ανεξαρτησίας.
    Αν υπάρχει μονοπάτι στο τελικό γράφημα, θα υπάρχει και στο
    προκύπτον και συνεπώς M_{p_{1}} \leq M_{p_{2}}.

    Μου αρέσει!

    Σχόλιο από henk&christos — Οκτώβριος 7, 2010 @ 12:38 πμ

  2. Πολύ σωστά.

    Η λύση που πρότεινες είναι αυτό που ονομάζουμε coupling (σύζευξη) δύο πειραμάτων.

    Ένας άλλος, κάπως πιο συμμετρικός, τρόπος να πετύχουμε το ίδιο είναι σε κάθε ακμή να ρίχνουμε μια ανεξάρτητη και ομοιόμορφη τυχαία μεταβλητή στο [0,1]. Με βάση το αποτέλεσμα αυτού του τυχαίου πειράματος μπορούμε (με ντετερμινιστικό τρόπο) να κατασκευάσουμε τα αποτελέσματα των δύο πειραμάτων που μας ενδιαφέρουν για p_1, p_2 ως εξής: αν η τυχαία μεταβλητή μιας ακμής είναι μικρότερη από το p_1 τότε κρατάμε την ακμή αλλιώς όχι (ομοίως για το p_2).

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

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Οκτώβριος 7, 2010 @ 12:54 πμ


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: