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

Απρίλιος 24, 2010

Διαγώνισμα πολλαπλής επιλογής

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

Ένα διαγώνισμα αποτελείται από n ερωτήσεις πολλαπλής επιλογής. Κάθε ερώτηση έχει 5 δυνατές απαντήσεις από τις οποίες μόνο μια είναι σωστή. Αν κάποιος απαντήσει σωστά μια ερώτηση παίρνει 1 μονάδα, ενώ αν απαντήσει λάθος χάνει 0,25 μονάδες. Ο διαγωνιζόμενος θεωρείται ότι πέτυχε στο διαγώνισμα αν πάρει συνολικά τουλάχιστον 0,5 n μονάδες.

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

Advertisements

8 Σχόλια »

  1. Με χρήση της ανισότητας Markov.
    Αν X είναι η τυχαία μεταβλητή που μετρά τις μονάδες που πέτυχε ο διαγωνιζόμενος, τότε X = \sum_{i} X_i, όπου X_i, i=1,\cdots,n τυχαία μεταβλητή που παίρνει την τιμή 1, με πιθανότητα 1/5 και την τιμή -1/4, με πιθανότητα 4/5. Οπότε,

    \mathbb{P}(X\geq n/2) = \mathbb{P}(e^X \geq e^{n/2}) το οποίο είναι μικρότερο ή ίσο του
    e^{-n/2} \prod_i \mathbb{E}\big[ e^{X_i} \big] = \big( e^{-1/2} (\frac{1}{5} e + \frac{4}{5} e^{-1/4}) \big)^n \approx (0.71)^n.

    Μου αρέσει!

    Σχόλιο από henk&christos — Απρίλιος 30, 2010 @ 11:03 πμ

  2. Αυτό είναι ένα αρκετά καλό φράγμα αφού αναδεικνύει την εκθετική μείωση αλλά μπορούμε και καλύτερα. Με μια μικρή παραλλαγή της απόδειξης του henk&christos δείξτε ότι

    \mathbb{P}(X\geq n/2) \le \left(\frac{4}{27}\right)^{n/5}\approx (0.68)^n.

    Για να βοηθήσω λίγο, η e^{\lambda x} είναι γνησίως αύξουσα συνάρτηση για οποιοδήποτε \lambda>0.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Απρίλιος 30, 2010 @ 2:51 μμ

  3. \mathbb{P}(X\geq n/2) = \mathbb{P}(e^{tX}\geq e^{tn/2})
    απ’όπου παίρνουμε ένα φράγμα που εξαρτάται του t και το ελαχιστοποιούμε ως προς t>0.
    Αναρωτιέμαι αν μπορεί κανεις να πάρει ακόμα καλύτερο φράγμα χρησιμοποιώντας Διωνυμικά κατανομή. Με την παρατήρηση ότι, για να πετύχει στις εξετάσεις χρειάζεται τουλάχιστον το 60\% των ερωτήσεων να έχουν απαντηθεί σωστά,
    η πιθανότητα να πετύχει ισούται με
    f(n) := \sum_{k=0.6n}^{n} \binom{n}{k}(1/5)^k(4/5)^{n-k}.

    Μου αρέσει!

    Σχόλιο από henk&christos — Απρίλιος 30, 2010 @ 3:11 μμ

  4. για την ακρίβεια, το άθροισμα ξεκινά από k=\left\lceil 0.6n \right\rceil

    Μου αρέσει!

    Σχόλιο από henk&christos — Απρίλιος 30, 2010 @ 3:15 μμ

  5. Πολύ σωστά. Ωραία και η ερώτησή σου, η απάντηση στην οποία είναι όχι, με την έννοια του ότι

    \displaystyle \lim_{n\to\infty} \frac{1}{n}\log \mathbb{P} \big[X\ge \frac{n}{2}\big] = \frac{1}{5}\log\left(\frac{4}{27}\right).

    Το άνω φράγμα το δείξαμε ήδη. Το κάτω είναι αρκετά πιο δύσκολο. Μήπως όμως μπορείτε να το δείξετε?

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Απρίλιος 30, 2010 @ 3:26 μμ

  6. f(n)\geq (1/5)^n

    Μου αρέσει!

    Σχόλιο από henk&christos — Μαΐου 3, 2010 @ 3:24 μμ

  7. Ναι, αλλά \frac{1}{5}<\left(\frac{4}{27}\right)^{\frac{1}{5}}.

    Θα θέλαμε να δείξουμε ότι

    \displaystyle \liminf_{n\to\infty} \frac{1}{n} \log\mathbb{P} \big[X\ge \frac{n}{2}\big] \ge \frac{1}{5}\log\left(\frac{4}{27}\right).

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Μαΐου 3, 2010 @ 4:59 μμ

  8. Υπόδειξη:
    Αν ο φοιτητής μας είχε διαβάσει λίγο παραπάνω, ώστε να γνώριζε τη σωστή απάντηση με πιθανότητα 0,5 (οπότε η πιθανότητα να δώσει μια σωστή απάντηση είτε επειδή την γνωρίζει είτε από τύχη ήταν 0,6) τότε το ενδεχόμενο να επιτύχει στο διαγώνισμα δεν θα ήταν και τόσο σπάνιο. Μάλιστα το κεντρικό οριακό θεώρημα μας λέει ότι το άθροισμα

    \displaystyle \sum_{k=0,6n}^n {n\choose k}\left(3/5\right)^k\left(2/5\right)^{n-k}

    συγκλίνει στο 1/2 αλλά και ποιοί όροι συνεισφέρουν ουσιαστικά σε αυτό. Προσπαθήστε τώρα να κάνετε τον τύπο για την πιθανότητα f(n) που έγραψε ο henk&christos στο σχόλιο 3 να μοιάζει με τον παραπάνω τύπο.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Μαΐου 23, 2010 @ 2:25 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

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

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