Zarul fermecat

de Mihai Scorțaru · 2 august 2015

Acest articol a pornit de la o postare pe Facebook în care am propus un puzzle cu o monedă magică (avea doar 47% șanse să cadă pe o parte). Postarea a fost, la rândul său, inspirată de o problemă propusă la InfoArena.

Așadar, începem cu o monedă: moneda magică cade pe o parte cu probabilitatea de 47% și pe cealaltă parte cu probabilitatea de 53%; având o astfel de monedă, trebuie să încercăm să simulăm "funcționarea" unei monede obișnuite.

Cu alte cuvinte, vrem să putem alegem între două variante, cu probabilitate egală (50%) de a o alege pe fiecare.

Moneda magică - cazul particular

Nu rezolvăm nimic dacă aruncăm moneda o singură dată; rezultatul va fi cap cu probabilitatea 0.47 (47%) și pajură cu probabilitatea 0.53 (53%). Dar, ce se întâmplă dacă aruncăm de două ori? Avem patru variante: cap-cap, cap-pajură, pajură-cap și pajură-pajură. Să calculăm probabilitățile fiecăreia:

cap-cap: 0.47 · 0.47 = 0.2209;
cap-pajură: 0.47 · 0.53 = 0.2491;
pajură-cap: 0.53 · 0.47 = 0.2491;
pajură-pajură: 0.53 · 0.53 = 0.2809.

Observăm două probabilități egale; suntem drumul cel bun; ar trebui să le putem folosi pentru simularea monedei reale. De exemplu, dacă am avea doar rezultate cap-pajură și pajură-cap, atunci am putea lua decizia în funcție de rezultatul primei aruncări.

Dar, ce facem când se întâmplă să avem cap-cap sau pajură-pajură? Simplu! Ignorăm și mai încercăm odată.

Așadar, soluția noastră ar fi cam așa: aruncăm moneda magică de două ori; dacă rezultatele sunt diferite ne oprim și alegerea este dată de rezultatul primei aruncări; dacă rezultatele sunt la fel, atunci repetăm procesul.

O implementare

Vom folosi limbajul Swift pentru a ilustra simularea monedei reale folosind-o pe cea magică. Motivul alegerii nu este foarte relevant, dar vom vedea în secțiunea următoare de ce Swift este un limbaj "simpatic" de data aceasta. Avem nevoie de o funcție care să simuleze aruncarea unei monede magice. Aceasta va returna true cu o probabilitatea de 47% și false cu o probabilitate de 53%. Implementarea ar putea fi următoarea:

import Darwin
func moneda_magică() -> Bool {
    return arc4random_uniform(100) < 47
}

import Darwin

func moneda_magică() -> Bool {

return arc4random_uniform(100) < 47

}

Să verificăm dacă funcția realizează ceea ce ne dorim. Vom simula 10000 de aruncări și ne așteptăm ca aproximativ 4700 dintre ele să fie cap. Codul care testează ar putea fi următorul:

var cap = 0, pajură = 0
for i in 1...10000 {
    if moneda_magică() {
        cap++
    } else {
        pajură++
    }
}

println("Cap: " + String(cap))
println("Pajură " + String(pajură))

var cap = 0, pajură = 0

for i in 1...10000 {

if moneda_magică() {

cap++

} else {

pajură++

}

println("Cap: " + String(cap))

println("Pajură " + String(pajură))

La prima rulare, "scorul" a fost 4663 - 5337; la a doua rezultatul a fost 4719 - 5281. Pare în regulă!

Să simulăm acum moneda reală. Vom avea două variabile boolene prima_aruncare și a_doua_aruncare; vom folosi funcția metoda_magică pentru a le da valori și vom efectua această operația atâta timp cât valorile obținute sunt aceleași. Când ne oprim, vom returna valoarea variabilei prima_aruncare. Implementarea este:

func moneda_reală() -> Bool {
    var prima_aruncare, a_doua_aruncare: Bool
    do {
        prima_aruncare = moneda_magică()
        a_doua_aruncare = moneda_magică()
    } while prima_aruncare == a_doua_aruncare
    return prima_aruncare
}

func moneda_reală() -> Bool {

var prima_aruncare, a_doua_aruncare: Bool

do {

prima_aruncare = moneda_magică()

a_doua_aruncare = moneda_magică()

} while prima_aruncare == a_doua_aruncare

return prima_aruncare

}

Putem modifica foarte ușor codul care testează. Trebuie doar să înlocuim apelul moneda_magică din linia 3 cu un apel moneda_reală. La prima rulare, "scorul" a fost 4959 - 5041; la a doua rezultatul a fost 5064 - 4934. Pare OK și de data aceasta...

Șansa de a avea nevoie de o repetiție este de 22.09% + 28.09% = 50.18% la fiecare pas. Ar fi interesant de calculat de câte ori repetăm aruncările în medie... Poate cu altă ocazie. Nu vom umple articolul cu formule de data aceasta!

Moneda magică - cazul general

Moneda magică avea o șansă de 47% de a cădea pe o parte. Numărul a fost ales arbitrar (și oarecum aproape de 50%) pentru ca șansele de a fi nevoie de prea multe repetiții. Dar, ideea funcționează pentru orice probabilitate α. Probabilitățile ar fi:

cap-cap: α · α = α²;
cap-pajură: α · (1 - α) = α - α²;
pajură-cap: (1 - α) · α = α - α²;
pajură-pajură: (1 - α) · (1 - α) = 1 - 2 · α + α².

Din nou, probabilitățile pentru cap-pajură și pajură-cap sunt egale, deci putem folosi aceeași idee. Noua funcția moneda_magică va avea un parametru α. Putem preciza acum motivul pentru care am ales limbajul Swift: putem folosi chiar numele α. Noua implementare ar putea fi:

import Darwin
func moneda_magică(α : Float) -> Bool {
    return Float(arc4random()) / Float(UINT32_MAX) < α
}

import Darwin

func moneda_magică(α : Float) -> Bool {

return Float(arc4random()) / Float(UINT32_MAX) < α

}

Nu vom complica implementarea cu validări; presupunem că valorile α sunt corecte: numere din intervalul deschis (0, 1). Putem testa și această implementare folosind noul apel. Dacă înlocuim apelul din linia 3 cu moneda_magică(0.47) ar trebui să avem tot aproximativ 4700 de aruncări pentru care rezultatul ar fi cap. Scorul nostru a fost 4701 - 5299 la prima rulare și 4704 - 5296 la a doua. Este doar o coincidență că valorile sunt mai apropiate de ținta de 4700 - 5300; la rulări succesive am obținut și valori mai îndepărtate.

Acum putem experimenta și cu alte niveluri de "magie". Pentru a verifica modul în care se comportă o monedă care are 99% șanse să cadă pe una din părți, putem înlocui apelul cu moneda_magică(0.99). Scorurile noastre au fost 9883 - 177 și 9889 - 111; ne-am fi așteptat la rezultate în jur de 9900 - 100.

Acum putem simula comportamentul monedei reale folosind orice fel de monedă magică. Să încercăm cu una care are probabilitatea de numai 25% de a cădea pe o anumită parte. Implementarea ar putea fi:

func moneda_reală() -> Bool {
    var prima_aruncare, a_doua_aruncare: Bool
    do {
        prima_aruncare = moneda_magică(0.25)
        a_doua_aruncare = moneda_magică(0.25)
    } while prima_aruncare == a_doua_aruncare
    return prima_aruncare
}

func moneda_reală() -> Bool {

var prima_aruncare, a_doua_aruncare: Bool

do {

prima_aruncare = moneda_magică(0.25)

a_doua_aruncare = moneda_magică(0.25)

} while prima_aruncare == a_doua_aruncare

return prima_aruncare

}

Sau, putem decide ca funcția care simulează moneda reală să primească și ea un parametru care să indice probabilitatea corespunzătoare monedei magice care să fie utilizată.

func moneda_reală(α : Float) -> Bool {
    var prima_aruncare, a_doua_aruncare: Bool
    do {
        prima_aruncare = moneda_magică(α)
        a_doua_aruncare = moneda_magică(α)
    } while prima_aruncare == a_doua_aruncare
    return prima_aruncare
}

func moneda_reală(α : Float) -> Bool {

var prima_aruncare, a_doua_aruncare: Bool

do {

prima_aruncare = moneda_magică(α)

a_doua_aruncare = moneda_magică(α)

} while prima_aruncare == a_doua_aruncare

return prima_aruncare

}

Se poate ajunge la confuzii; apelul ar fi moneda_reală(0.25) . Nu avem o "monedă reală" cu probabilitatea de 25% de a cădea pe o parte, ci o simulare a unei monede reale folosind o monedă magică având această probabilitate.

Indiferent de alegerea făcută, trebuie să obținem scoruri apropiate de 5000 - 5000. Rezultatele au fost 5083 - 4917, respectiv 5068 - 4932.

Putem calcula și șansele de a avea nevoie de o repetiție: α² + 1 - 2 · α + α² = 1 - 2 · α + 2 · α². Este evident că aceste șanse cresc dacă α se depărtează de 0.5. Putem simula moneda reală și cu monede magice cu probabilități de 99% (sau chiar mai mult), dar va dura foarte mult. Poate ar mai trebui menționat că dacă moneda magică este, de fapt, una reală, atunci α este exact 0.5 și probabilitatea de repetiție este tot 0.5, conform așteptărilor.

Trei variante

Monedele reale au o șansă (foarte, foarte mică) de a cădea pe dungă (cu cât moneda este mai mică și muchia mai groasă șansele cresc). Dar, monedele magice ar putea avea orice șansă de a cădea pe dungă. Folosind astfel de monede magice, putem alege între trei variante. Evident, dorim ca fiecare dintre cele trei variante să aibă aceeași șansă de a fi aleasă. Vom nota cu α probabilitatea de a obține cap, cu β probabilitatea de a obține pajură și cu γ probabilitatea de a obține dungă. Evident, trebuie să avem α + β + γ = 1.

Să simulăm o astfel de monedă magică. De data aceasta funcția va avea doi parametri (două dintre probabilități) și va returna 1, 2 sau 3.

func moneda_magică(α: Float, β : Float) -> Int {
    let valoare = Float(arc4random()) / Float(UINT32_MAX)
    if valoare < α {
        return 1
    }
    if valoare < α + β {
        return 2
    }
    return 3
}

func moneda_magică(α: Float, β : Float) -> Int {

let valoare = Float(arc4random()) / Float(UINT32_MAX)

if valoare < α {

return 1

}

if valoare < α + β {

return 2

}

return 3

}

Pentru a verifica această funcție am putea scrie următorul cod (am folosit o probabilitate de 45% pentru cap și 35% pentru pajură, deci dunga are o probabilitate de 20%):

var cap = 0, pajură = 0, dungă = 0
for i in 1...10000 {
    switch moneda_magică(0.45, 0.35) {
    case 1:
        cap++
    case 2:
        pajură++
    case 3:
        dungă++
    default: ()
    }
}

println("Cap: " + String(cap))
println("Pajură " + String(pajură))
println("Dungă " + String(dungă))

var cap = 0, pajură = 0, dungă = 0

for i in 1...10000 {

switch moneda_magică(0.45, 0.35) {

case 1:

cap++

case 2:

pajură++

case 3:

dungă++

default: ()

}

println("Cap: " + String(cap))

println("Pajură " + String(pajură))

println("Dungă " + String(dungă))

La prima rulare rezultatul obținut a fost 4537 - 3437 - 2026, iar la a doua 4431 - 3450 - 2119.

Să vedem acum ce se întâmplă când aruncăm moneda. Dacă o aruncăm o singură dată probabilitățile sunt α, β și γ; nu avem ce face cu ele. Să vedem ce se întâmplă dacă aruncăm de două ori:

cap-cap: α · α = α²;
cap-pajură: α · β = αβ;
cap-dungă: α · γ = αγ;
pajură-cap: β · α = αβ;
pajură-pajură: β · β = β²;
pajură-dungă: β · γ = βγ;
dungă-cap: γ · α = αγ;
dungă-pajură: γ · β = βγ;
dungă-dungă: γ · γ = γ².

Pe modelul de la cazul anterior, am vrea să identificăm trei probabilități egale. Nu avem! Să încercăm cu trei aruncări:

cap-cap-cap: α · α · α = α³;
cap-cap-pajură: α · α · β = α²β;
cap-cap-dungă: α · α · γ = α²γ;
cap-pajură-cap: α · β · α = α²β;
cap-pajură-pajură: α · β · β = αβ²;
cap-pajură-dungă: α · β · γ = αβγ;
cap-dungă-cap: α · γ · α = α²γ;
cap-dungă-pajură: α · γ · β = αβγ;
cap-dungă-dungă: α · γ · γ = αγ²;
pajură-cap-cap: β · α · α = α²β;
pajură-cap-pajură: β · α · β = αβ²;
pajură-cap-dungă: β · α · γ = αβγ;
pajură-pajură-cap: β · β · α = αβ²;
pajură-pajură-pajură: β · β · β = β³;
pajură-pajură-dungă: β · β · γ = β²γ;
pajură-dungă-cap: β · γ · α = αβγ;
pajură-dungă-pajură: β · γ · β = β²γ;
pajură-dungă-dungă: β · γ · γ = βγ²;
dungă-cap-cap: γ · α · α = α²γ;
dungă-cap-pajură: γ · α · β = αβγ;
dungă-cap-dungă: γ · α · γ = αγ²;
dungă-pajură-cap: γ · β · α = αβγ;
dungă-pajură-pajură: γ · β · β = β²γ;
dungă-pajură-dungă: γ · β · γ = βγ²;
dungă-dungă-cap: γ · γ · α = αγ²;
dungă-dungă-pajură: γ · γ · β = βγ²;
dungă-dungă-dungă: γ · γ · γ = γ³.

E mai bine; am evidențiat câteva variante care au cu siguranță aceeași probabilitate. Practic, sunt combinațiile care duc la trei rezultate diferite pentru cele trei aruncări. La fel ca în cazul în care aveam o singură variantă, putem decide că prima aruncare decide. Am putea scrie următoarea funcție pentru a alege între trei variante folosind noua monedă magică:

func trei_variante(α : Float, β : Float) -> Int {
    var prima_aruncare, a_doua_aruncare, a_treia_aruncare: Int
    do {
        prima_aruncare = moneda_magică(α, β)
        a_doua_aruncare = moneda_magică(α, β)
        a_treia_aruncare = moneda_magică(α, β)
    } while prima_aruncare == a_doua_aruncare || prima_aruncare == a_treia_aruncare || a_doua_aruncare == a_treia_aruncare
    return prima_aruncare
}

func trei_variante(α : Float, β : Float) -> Int {

var prima_aruncare, a_doua_aruncare, a_treia_aruncare: Int

do {

prima_aruncare = moneda_magică(α, β)

a_doua_aruncare = moneda_magică(α, β)

a_treia_aruncare = moneda_magică(α, β)

} while prima_aruncare == a_doua_aruncare || prima_aruncare == a_treia_aruncare || a_doua_aruncare == a_treia_aruncare

return prima_aruncare

}

Testul merge mult mai încet. De data aceasta doar 6 dintre cele 27 de combinații posibile la o încercare nu duc la o repetare. Dacă probabilitățile ar fi apropiate de 1 / 3, am avea 7 / 9 șanse să repetăm la fiecare încercare. În cazul general, șansa de a repeta este 1 - 6αβγ.

Putem efectua o mică optimizare: nu mai are rost să aruncăm a treia monedă dacă în urma primelor două aruncări am obținut același rezultat.

func trei_variante(α : Float, β : Float) -> Int {
    var prima_aruncare, a_doua_aruncare, a_treia_aruncare: Int?
    do {
        prima_aruncare = moneda_magică(α, β)
        a_doua_aruncare = moneda_magică(α, β)
        if prima_aruncare != a_doua_aruncare {
            a_treia_aruncare = moneda_magică(α, β)
        }
    } while prima_aruncare == a_doua_aruncare || prima_aruncare == a_treia_aruncare || a_doua_aruncare == a_treia_aruncare
    return prima_aruncare!
}

func trei_variante(α : Float, β : Float) -> Int {

var prima_aruncare, a_doua_aruncare, a_treia_aruncare: Int?

do {

prima_aruncare = moneda_magică(α, β)

a_doua_aruncare = moneda_magică(α, β)

if prima_aruncare != a_doua_aruncare {

a_treia_aruncare = moneda_magică(α, β)

}

} while prima_aruncare == a_doua_aruncare || prima_aruncare == a_treia_aruncare || a_doua_aruncare == a_treia_aruncare

return prima_aruncare!

}

Am obținut următoarele rezultate: 3298 - 3442 - 3260, respectiv 3354 - 3330 - 3316.

Zarul fermecat

Pentru un zar avem șase probabilități: α, β, γ, δ, ε și ζ cu proprietatea α + β + γ + δ + ε = 1. Funcția care simulează zarul fermecat are nevoie de cinci dintre ele și va returna un număr cuprins între 1 și 6. Le vom pune într-un șir:

func zar_fermecat(probabilități: [Float]) -> Int {
    let valoare = Float(arc4random()) / Float(UINT32_MAX)
    var sumă : Float = 0
    for i in 0..<5 {
        sumă += probabilități[i]
        if (valoare < sumă) {
            return i + 1
        }
    }
    return 6
}

func zar_fermecat(probabilități: [Float]) -> Int {

let valoare = Float(arc4random()) / Float(UINT32_MAX)

var sumă : Float = 0

for i in 0..<5 {

sumă += probabilități[i]

if (valoare < sumă) {

return i + 1

}

return 6

}

Să testăm acum un zar fermecat ale cărui probabilități sunt 25%, 20%, 18%, 15%, 12%, respectiv 10%.

var rezultate = [Float](count: 6, repeatedValue: 0.0)
var probabilități : [Float] = [0.25, 0.20, 0.18, 0.15, 0.12]
for i in 1...10000 {
    rezultate[zar_fermecat(probabilități) - 1]++
}
println(rezultate)

var rezultate = [Float](count: 6, repeatedValue: 0.0)

var probabilități : [Float] = [0.25, 0.20, 0.18, 0.15, 0.12]

for i in 1...10000 {

rezultate[zar_fermecat(probabilități) - 1]++

}

println(rezultate)

Am obținut 2484 - 1984 - 1758 - 1570 - 1192 - 1012, respectiv 2477 - 2009 - 1791 - 1463 - 1236 - 1024.

Știm acum cam care este rețeta: vom arunca de șase ori și vrem rezultate diferite la fiecare dintre cele șase aruncări. Dacă reușim, prima aruncare va fi cea care va da rezultatul.

De data aceasta va fi mult mai lent: avem 6⁶ = 46656 variante și doar 6! = 720 dintre ele ne permit să luăm o decizie. Dacă probabilitățile sunt apropiate de 1/6, șansa de a repeta este (46656 - 720) / 46656 = 45936 / 46656 = 319 / 324 (peste 98%). Vom optimiza din nou oprindu-ne la prima repetiție.

O implementare ar putea fi:

func verificare(probabilități: [Float], prima_aruncare : Int) -> Bool {
    var rezultate = [Bool](count: 6, repeatedValue: false)
    rezultate[prima_aruncare - 1] = true
    for i in 1...5 {
        let aruncare = zar_fermecat(probabilități)
        if (rezultate[aruncare - 1]) {
            return false
        }
        rezultate[aruncare - 1] = true
    }
    return true
}

func zar(probabilități: [Float]) -> Int {
    while (true) {
        let prima_aruncare = zar_fermecat(probabilități)
        if verificare(probabilități, prima_aruncare) {
            return prima_aruncare
        }
    }
}

func verificare(probabilități: [Float], prima_aruncare : Int) -> Bool {

var rezultate = [Bool](count: 6, repeatedValue: false)

rezultate[prima_aruncare - 1] = true

for i in 1...5 {

let aruncare = zar_fermecat(probabilități)

if (rezultate[aruncare - 1]) {

return false

}

rezultate[aruncare - 1] = true

}

return true

}

func zar(probabilități: [Float]) -> Int {

while (true) {

let prima_aruncare = zar_fermecat(probabilități)

if verificare(probabilități, prima_aruncare) {

return prima_aruncare

}

De data aceasta ne vom mulțumi cu 1000 de simulări; rezultatele sunt 177 - 159 - 164 - 159 - 174 - 167, respectiv 156 - 168 - 158 - 177 - 154 - 187.

Cazul general

Este foarte ușor acum să alegem între n variante dacă avem la dispoziție un dispozitiv care să ne permită alegerea uneia dintre cele n cu o anumită probabilitate. Vom face câte n alegeri până în momentul în care cele n alegeri dau rezultate diferite. Alegerea finală va fi dată de prima dintre cele n.

Putem face câteva optimizări pentru a mări puțin viteza, dar modificările nu sunt importante. Codul sursă complet este:

import Darwin

var probabilități : [Float] = [0.4, 0.3, 0.2]
var sume = [Float](count: probabilități.count, repeatedValue: 0)

var suma : Float = 0
for i in 0..<probabilități.count {
    suma += probabilități[i]
    sume[i] = suma
}

func dispozitiv_cu_probabilități_diferite() -> Int {
    let valoare = Float(arc4random()) / Float(UINT32_MAX)
    for i in 0..<sume.count {
        if (valoare < sume[i]) {
            return i
        }
    }
    return sume.count
}

func verificare(prima_aruncare : Int) -> Bool {
    var rezultate = [Bool](count: sume.count + 1, repeatedValue: false)
    rezultate[prima_aruncare] = true
    for i in 1...sume.count {
        let aruncare = dispozitiv_cu_probabilități_diferite()
        if (rezultate[aruncare]) {
            return false
        }
        rezultate[aruncare] = true
    }
    return true
}

func dispozitiv_cu_probabilități_egale() -> Int {
    while (true) {
        let prima_aruncare = dispozitiv_cu_probabilități_diferite()
        if verificare(prima_aruncare) {
            return prima_aruncare
        }
    }
}

var rezultate = [Int](count: sume.count + 1, repeatedValue: 0)
for i in 1...1000 {
    rezultate[dispozitiv_cu_probabilități_egale()]++
}
println(rezultate)

import Darwin

var probabilități : [Float] = [0.4, 0.3, 0.2]

var sume = [Float](count: probabilități.count, repeatedValue: 0)

var suma : Float = 0

for i in 0..<probabilități.count {

suma += probabilități[i]

sume[i] = suma

}

func dispozitiv_cu_probabilități_diferite() -> Int {

let valoare = Float(arc4random()) / Float(UINT32_MAX)

for i in 0..<sume.count {

if (valoare < sume[i]) {

return i

}

return sume.count

}

func verificare(prima_aruncare : Int) -> Bool {

var rezultate = [Bool](count: sume.count + 1, repeatedValue: false)

rezultate[prima_aruncare] = true

for i in 1...sume.count {

let aruncare = dispozitiv_cu_probabilități_diferite()

if (rezultate[aruncare]) {

return false

}

rezultate[aruncare] = true

}

return true

}

func dispozitiv_cu_probabilități_egale() -> Int {

while (true) {

let prima_aruncare = dispozitiv_cu_probabilități_diferite()

if verificare(prima_aruncare) {

return prima_aruncare

}

var rezultate = [Int](count: sume.count + 1, repeatedValue: 0)

for i in 1...1000 {

rezultate[dispozitiv_cu_probabilități_egale()]++

}

println(rezultate)

Pe lângă faptul că am redenumit funcțiile în dispozitiv_cu_probabilități_egaleși dispozitiv_cu_probabilități_diferite, am realizat câteva alte modificări și optimizări:

funcția care genera numere în funcție de probabilități calcula o sumă pentru a vedea exact "zona" în care "cade" valoarea generată aleator; sumele respective sunt aceleași, deci pot fi calculate o singură dată;
nu e neapărat necesar să transmitem ca parametru vectorul care conține probabilități (sau sume); putem să folosim o variabilă globală;
nu mai avem un număr constant de elemente în vectori; vectorul probabilități ne va da numărul variantelor și toți ceilalți vectori vor avea dimensiuni care depind de dimensiunea acestuia;
ca exemplificare, am folosit un dispozitiv care poate genera patru valori distincte, probabilitățile fiind 40%, 30%, 20% și 10%;
pentru simplitate, variantele generate nu sunt numerotate începând cu 1, ci începând cu 0.

Zarul fermecat

Moneda magică - cazul particular

O implementare

Moneda magică - cazul general

Trei variante

Zarul fermecat

Cazul general

Un proiect