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

Δεκέμβριος 7, 2012

Ένα τίμιο κέρμα

Filed under: Λυμένα Προβλήματα — Michalis Loulakis @ 1:50 πμ

Έχουμε ένα κέρμα που φέρνει γράμματα με πιθανότητα p>0, σταθερή αλλά άγνωστη. Μπορείτε χρησιμοποιώντας αυτό το κέρμα να κατασκευάσετε έναν αλγόριθμο με δύο δυνατές τελικές καταστάσεις και πιθανότητα 1/2 να καταλήξει σε καθεμιά από αυτές; Μπορείτε δηλαδή να προσομοιώσετε ένα τίμιο κέρμα χρησιμοποιώντας μόνο ένα κέρμα που δεν ξέρετε αν είναι τίμιο;

Advertisements

2 Σχόλια »

  1. 1. ρίξε το κέρμα δύο φορές
    2. αν έρθει ΚΚ ή ΓΓ ξαναρίξε

    Οι δύο τελικές καταστάσεις είναι Κορώνα – Γράμματα και Γράμματα – Κορώνα

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

    Μου αρέσει!

    Σχόλιο από shortmanikos — Δεκέμβριος 8, 2012 @ 11:16 μμ

  2. Σωστά. Σύμφωνα με τον αλγόριθμο που περίγραψες (και οφείλεται στον John von Neumann) αν η πιθανότητα να καταλήξουμε σε κάθε κατάσταση είναι q από τον τύπο της ολικής πιθανότητας έχουμε
    q=p(1-p)+\big(p^2+(1-p)^2\big)q \Leftrightarrow q=\frac{1}{2}.
    Η πιθανότητα να τερματίσει ο αλγόριθμος σε μια επανάληψη είναι p(1-p)>0 και επειδή επαναλαμβάνουμε ανεξάρτητες δοκιμές Bernoulli η πιθανότητα να μην τερματίσει ο αλγόριθμος είναι 0.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Δεκέμβριος 9, 2012 @ 7:42 μμ


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: