11 palline

[franco]

Da Facebook:

In un'urna con 11 palline numerate da 1 a 11 ne vengono estratte 5 al giorno e poi rimesse dentro.
Qual è la probabilità che dopo 5 giorni siano stati estratti tutti i numeri almeno una volta?

[NothIng]

Sto affrontando il problema come fosse un processo markoviano ma sono poco confidente del risultato ottenuto.

Ho chiesto aiuto all'intelligenza artificiale, duck.ai, per scrivere una macro excel che esegua la simulazione, mi fornisce un valore di circa 75.2%.
Ecco il codice che ha generato solo leggermete ritoccato

Codice: Seleziona tutto

Sub SimulaEstrazioni()
    Dim k As Long ' Numero totale di oggetti
    Dim n As Long ' Numero di oggetti da estrarre
    Dim estrazioni As Long ' Numero di estrazioni
    Dim i As Long, j As Long, oggetti As Long
    Dim oggettiEstratti() As Long ' Dichiarato come array dinamico
    Dim oggetto As Long
    Dim conteggioSuccessi As Long
    Dim numeroSimulazioni As Long
    Dim probabilita As Double
    Dim conteggioOggettiDistinti As Long
    Dim oggettiDisponibili As Collection
    Dim estrazione As Long

    ' Imposta i valori di k, n e il numero di simulazioni
    k = 11 'InputBox("Inserisci il numero totale di oggetti (k):")
    g = 5 'InputBox("Inserisci il numero di giorni (g):")
    estrazioni = 5
    numeroSimulazioni = 1000000 ' Numero di simulazioni da eseguire

    conteggioSuccessi = 0

    ' Esegui le simulazioni
    For i = 1 To numeroSimulazioni
        ' Inizializza la collezione per tenere traccia degli oggetti estratti
        Set oggettiDisponibili = New Collection
                
        ' Inizializza l'array per tenere traccia degli oggetti estratti
        ReDim oggettiEstratti(1 To estrazioni * g) As Long ' Cambiato a estrazioni
            
        ' Esegui le estrazioni di n oggetti per g giorni
        For giorno = 1 To g
            ' Aggiungi tutti gli oggetti disponibili alla collezione
            For j = 1 To k
                oggettiDisponibili.Add j
            Next j
        
            For estraz = 1 To estrazioni
                ' Estrai un oggetto casuale dalla collezione
                oggetto = Int((oggettiDisponibili.Count) * Rnd) + 1
                ' Aggiungi l'oggetto estratto all'array
                oggettiEstratti((giorno - 1) * estrazioni + estraz) = oggettiDisponibili(oggetto)
                ' Rimuovi l'oggetto estratto dalla collezione
                oggettiDisponibili.Remove oggetto
            Next estraz
        Next giorno
      
        ' Conta gli oggetti distinti estratti
         trovato = 0
         For oggetti = 1 To k
         esiste = 0
            For j = 1 To estrazioni * g
                If (oggettiEstratti(j) = oggetti) And (esiste = 0) Then
                    esiste = 1
                    trovato = trovato + 1
                End If
            Next j
         Next oggetti
                
        If trovato >= k Then
            conteggioSuccessi = conteggioSuccessi + 1
        End If
  
    Next i

    ' Calcola la probabilità
    probabilita = conteggioSuccessi / numeroSimulazioni

    ' Mostra il risultato
    MsgBox "La probabilità di estrarre almeno " & g & " oggetti distinti dopo " & estrazioni & " estrazioni è: " & Format(probabilita, "0.00%")
End Sub

[franco]

Sto affrontando il problema come fosse un processo markoviano ma sono poco confidente del risultato ottenuto.

Ho chiesto aiuto all'intelligenza artificiale, duck.ai, per scrivere una macro excel che esegua la simulazione, mi fornisce un valore di circa 75.2%.

Uhm

Ho fatto anche io una simulazione (usando le funzioni di excel e una piccola macro in VBA per fare 100.000 iterazioni) e mi viene un valore molto diverso: circa il 55%.

Un altro utente Facebook ha scritto un programmino di simulazione in C++ ed ha ottenuto circa il 54,7% con un milione di iterazioni.

In realtà però mi piacerebbe arrivare al risultato con delle formule ... ma al momento non riesco a trovare una chiave!

[panurgo]

La mia catena di Markov mi dice:

$\displaystyle\frac{1559295200}{2847396321}=0,5476\ldots$

[franco]

La mia catena di Markov mi dice:

$\displaystyle\frac{1559295200}{2847396321}=0,5476\ldots$

Mi sembra assolutamente allineato con i risultati sperimentali

Io sto sbattendo la testa contro il muro e non riesco proprio a trovare una strada praticabile ...
Mi sa che mi metto comodo ed aspetto con trepitazione tue notizie

[panurgo]

Mi sembra assolutamente allineato con i risultati sperimentali

Significa che le tue simulazioni funzionano bene...

Un suggerimento: le probabilità di cui parliamo sono governate dalla distribuzione ipergeometrica

$\displaystyle \Pr\left(n+k\middle|n\right)= \frac{{{n}\choose{5-k}}{{11-n}\choose{k}}}{{{11}\choose{5}}}$

Sono già usciti $n$ numeri, altri $k$ numeri escono in questa estrazione: $5-k$ numeri di questa estrazione sono tra gli $n$ numeri gia usciti mentre gli altri $k$ sono tra gli $11-n$ numeri non ancora usciti.

${{n}\choose{5-k}}$ sono i modi in cui possono essere presi i numeri vecchi, ${{11-n}\choose{k}}$ sono i modi in cui possono essere presi i numeri nuovi e ${{11}\choose{5}}$ sono i modi in cui possono essere presi cinque numeri su undici.

Un esempio, la probabilità di avere cinque numeri usciti partendo da cinque numeri è

$\displaystyle \Pr\left(5\middle|5\right)= \frac{{{5}\choose{5}}{{6}\choose{0}}}{{{11}\choose{5}}}=\frac1{462}$

Ancora

$\displaystyle \Pr\left(6\middle|5\right)= \frac{{{5}\choose{4}}{{6}\choose{1}}}{{{11}\choose{5}}}=\frac{30}{462}=\frac{5}{77}$

[franco]

Un suggerimento: le probabilità di cui parliamo sono governate ...

Grazie al tuo suggerimento e ad una tabellina excel con 207 righe (ma in massima parte compilata con copia/incolla) ci sono arrivato!

Immagino che tu avrai usato delle elegantissime matrici ma non è roba per me ... mi accontento

[Quelo]

La mia simulazione conferma 54,76%

Codice: Seleziona tutto

from random import sample
u = list(range(11))                             # insieme [0, 1, ... 10]

t = 100_000_000                                 # iterazioni
f = 0                                           # estrazioni complete

for i in range(t):
    e = set()                                   # insieme vuoto {}
    for j in range(5): e |= set(sample(u,5))    # 5 estrazioni, ad ogni estrazione si aggiungono a e le palline nuove
    if len(e)==11: f += 1                       # conta gli insiemi completi

print(f/t)

[NothIng]

Ho chiesto aiuto all'intelligenza artificiale, duck.ai, per scrivere una macro excel che esegua la simulazione, mi fornisce un valore di circa 75.2%.

Oops ecco a cosa succede ad usare l'intelligenza degli altri....
Nel precedente codice che ho postato la distribuzione dei numeri da 1 a 11 non è uniforme e cambia ad ogni estrazione.
Ho risolto il bug, ecco il codice, è prolisso rispetto al post di Quelo.

Codice: Seleziona tutto

Sub SimulaEstrazioni()
    Dim totOggetti As Integer ' Numero totale di oggetti
    Dim n As Integer ' Numero di oggetti da estrarre
    Dim oggetti As Integer ' Numero di oggetti estratti
    Dim simul As Long, j As Long
    Dim numeriEstratti() As Integer
    Dim oggettiEstratti() As Integer ' Dichiarato come array dinamico
    Dim oggetto As Integer
    Dim conteggioSuccessi As Long
    Dim numeroSimulazioni As Long
    Dim probabilita As Double

    ' Imposta i valori di totOggetti, n e il numero di simulazioni
    totOggetti = 11 'InputBox("Inserisci il numero totale di oggetti:")
    g = 5 'InputBox("Inserisci il numero di giorni:")
    n = 5
    numeroSimulazioni = 100000 ' Numero di simulazioni da eseguire

    conteggioSuccessi = 0
  
    Randomize ' Inizializza il generatore di numeri casuali
    ' Esegui le simulazioni
    For simul = 1 To numeroSimulazioni

        ' Inizializza l'array per tenere traccia degli oggetti estratti
        ReDim oggettiEstratti(1 To n * g) As Integer ' Cambiato a estrazioni
            
        ' Esegui le estrazioni di n oggetti per g giorni
        For giorno = 1 To g
            ReDim numeriEstratti(1 To n) As Integer
            
            ' Estrai i numeri per il giorno corrente
            EstraiOggettiCasuali totOggetti, n, numeriEstratti
            ' Aggiungi tutti gli oggetti disponibili alla collezione
            AggiungiOggettiEstratti oggettiEstratti, numeriEstratti, (giorno - 1) * n
        Next giorno

      
        ' Conta gli oggetti estratti distinti
         trovato = 0
         For oggetti = 1 To totOggetti
            esiste = 0
            For j = 1 To n * g
                If (oggettiEstratti(j) = oggetti) And (esiste = 0) Then
                    esiste = 1
                    trovato = trovato + 1
                End If
            Next j
         Next oggetti
                
        ' Conta i successi
        If trovato >= totOggetti Then
            conteggioSuccessi = conteggioSuccessi + 1
        End If
  
    Next simul

    ' Calcola la probabilità
    probabilita = conteggioSuccessi / numeroSimulazioni

    ' Mostra il risultato
    MsgBox "La probabilità di estrarre almeno " & n & " oggetti distinti dopo " & g & " giorni è: " & Format(probabilita, "0.00%")
End Sub


Sub EstraiOggettiCasuali(totOggetti As Integer, n As Integer, ByRef numeriEstratti() As Integer)
    Dim i As Integer
    Dim numero As Integer
    Dim trovato As Boolean

    For i = 1 To n
        Do
            numero = Int((totOggetti) * Rnd + 1) ' Genera un numero casuale per ogni oggetti
            trovato = False
            
            ' Controlla se il numero è già stato generato
            For j = 1 To i - 1
                If numeriEstratti(j) = numero Then
                    trovato = True
                    Exit For
                End If
            Next j
            
        Loop While trovato ' Ripeti finché non trovi un numero unico
        
        numeriEstratti(i) = numero ' Aggiungi il numero all'array
    Next i
End Sub

Sub AggiungiOggettiEstratti(ByRef oggettiEstratti() As Integer, numeriEstratti() As Integer, offset As Integer)
    Dim i As Integer
    
    For i = 1 To UBound(numeriEstratti)
        oggettiEstratti(offset + i) = numeriEstratti(i)
    Next i
End Sub

Un suggerimento: le probabilità di cui parliamo sono governate dalla distribuzione ipergeometrica

Questo problema mi ricorda una vecchia storia di mandorle e nocciole

[panurgo]

...per non parlare dei gormiti

[panurgo]

Questo è il mio codice in R

Codice: Seleziona tutto

maxRipetizioni <- 1e6
numRipetizioni <- 0
casiFavorevoli <- 0
palline <- (1:11)
while (numRipetizioni < maxRipetizioni) {
  numRipetizioni <- numRipetizioni + 1
  controllo <- rep(0,11)
  numEstrazioni <- 0
  while(sum(controllo) < 11) {
    numEstrazioni <- numEstrazioni + 1
    controllo[sample(palline,5,replace=FALSE)] <- 1
  }
  casiFavorevoli <- casiFavorevoli + as.numeric(numEstrazioni <= 5)
}
print(casiFavorevoli/numRipetizioni)

[franco]

Quelo credo abbia usato il linguaggio Pyton.
Nothing ha usato Visual Basic
Panurgo ha usato R
...
Per ampliare la gamma, questo è il codice in C++ postato su Facebook (come immagine) da un un utente:

11.jpg (55.29 KiB) Visto 127729 volte

Così ad occhio direi che Pyton è quello più efficiente/sintetico

Io, che mastico poco di linguaggi di programmazione, ho usato un foglio Excel con le funzioni SORTBY, RANDARRAY, e MATCH, più una piccolissima routine in Visual Basic per fargli reiterare i conti (vabbè, ci mette 40 secondi per fare 100.000 iterazioni )

[Quelo]

Per completare la panoramica, ecco anche il codice in Decimal Basic (per semplificarmi la vita ho usato le stringhe come array)
Python ci mette 14 secondi per 1 milione di iterazioni, mentre Decimal Basic 36
C++ è probabilmente il più veloce

Codice: Seleziona tutto

LET r=1000000                             ! iterazioni
LET c=0                                   ! contatore

FOR i=1 TO r
   LET e$="00000000000"                   ! palline estratte in 5 giorni
   FOR g=1 TO 5
      LET a$="ABCDEFGHIJK"                ! riempimento dell'urna
      FOR h=1 TO 5
         LET p=INT((12-h)*RND+1)          ! scelta casuale della pallina
         LET q=ORD(a$(p:p))-64            
         LET e$(q:q)="1"                  ! aggiunta a quelle estratte
         LET a$(p:p)=""                   ! rimozione dall'urna
      NEXT H
   NEXT G
   IF e$="11111111111" THEN LET c=c+1     ! verifica se tutte le palline sono state estratte
NEXT I

PRINT(c/r)

[NothIng]

Sono un principiante e mi limito ad affrontare un problema più semplice.
In un'urna con 5 palline numerate da 1 a 5 ne vengono estratte 3 al giorno e poi rimesse dentro.
Qual è la probabilità che dopo 3 giorni siano stati estratti tutti i numeri almeno una volta?

Questo problema ha una dimensione più semplice dell'originale e si possono contare i casi più facilmente.
La simulazione dice che la probabilità è circa il 69%.

Con la prima estrazione si passa sempre dallo stato "0 numeri diversi" allo stato "3 numeri diversi"$^*$.

Con la seconda estrazione si può:

• rimanere nello stato "3 numeri diversi". Succede quando quando si estraggono gli stessi 3 numeri della prima estrazione. Probabilità = $\frac{1}{10}$

• passare nello stato "5 numeri diversi". Succede quando la terzina contiene i due numeri che mancavano nella prima estrazione. Probabilità = $\frac{3}{10}$

• passare nello stato "4 numeri diversi". Succede negli altri casi. Probabilità 1 - 0.1 - 0.3 = 0.6

Con la terza estrazione si può:

• rimanere nello stato "3 numeri diversi". Non porta nello stato "5 numeri diversi"

• rimanere nello stato "4 numeri diversi". Non porta nello stato "5 numeri diversi"

• passare dallo stato "3 numeri diversi" allo stato "4 numeri diversi". Non porta nello stato "5 numeri diversi"

• passare dallo stato "3 numeri diversi" allo stato "5 numeri diversi". Succede quando la terzina contiene i due numeri che mancavano nelle prime due estrazioni. Probabilità = $\frac{3}{10}$

• passare dallo stato "4 numeri diversi" allo stato "5 numeri diversi". Succede quando la terzina contiene il numero che mancavano nella quartina. Probabilità = $\frac{3}{5}^{**}$

Ecco il grafo degli stati:

GrafoStati.png (23.74 KiB) Visto 125929 volte

Trovo rassicurante che la somma dei valori di uscita di ogni nodo sia 1: da ogni nodo si può pur andare da qualche parte!

Per arrivare nello stato "5 numeri diversi" con 3 estrazioni si possono considerare le possibili transizioni con i relativi pesi:
0->3->5->5 + 0->3->4->5 + 0->3->3->5: $\frac{10}{10}*\frac{3}{10}*1 + \frac{10}{10}*\frac{6}{10}*\frac{3}{5} + \frac{10}{10}*\frac{1}{10}*\frac{3}{10} = \frac{30 + 36 + 3}{100} = \frac{69}{100}$
è lo stesso valore detto dalla simulazione: altra cosa che trovo rassicurante.

Estendere questi risultati al problema originale richiede ancora un poco di studio.....
________________________________________________________________________________________
$^*$: Le terzine distinte possibili sono 10: $123, 124, 125, 134, 135, 145, 234, 235, 245, 345$
$^{**}$: Si arriva nello stato "4 numeri diversi" perché sono stati estratti 4 numeri differenti; le quartine distinte possibili sono 5: $1234, 1235, 1245, 1345, 2345$

[NothIng]

GrafoStati.png (23.74 KiB) Visto 122283 volte

Ecco i miei primi passi nel mondo della distribuzione ipergeometrica fatti per calcolare i pesi delle transizioni, usando i suggerimenti di Panurgo.

Transizione "0" -> "1":
ci sono $3$ numeri su un totale di $5$ che fanno avvenire la transizione: $peso=\displaystyle \frac{\binom{5}{3}\binom{5-5}{3-3}}{\binom{5}{3}} = 1$

Transizione "3" -> "3":
ci sono $3$ numeri su un totale dei $3$ estratti precedentemente che fanno avvenire la transizione: $peso=\displaystyle \frac{\binom{3}{3}\binom{5-3}{3-3}}{\binom{5}{3}} = \frac{1}{10}$

Transizione "3" -> "4":
c'è $1$ numero su un totale dei $2$ non estratti precedentemente che fa avvenire la transizione: $peso=\displaystyle \frac{\binom{2}{1}\binom{5-2}{3-1}}{\binom{5}{3}} = \frac{6}{10}$

Transizione "3" -> "5":
ci sono $2$ numeri su un totale dei $2$ non estratti precedentemente che fanno avvenire la transizione: $peso=\displaystyle \frac{\binom{2}{2}\binom{5-2}{3-2}}{\binom{5}{3}} = \frac{3}{10}$

Transizione "4" -> "4":
ci sono $3$ numeri su un totale dei $4$ estratti precedentemente che fanno avvenire la transizione: $peso=\displaystyle \frac{\binom{4}{3}\binom{5-4}{3-3}}{\binom{5}{3}} = \frac{2}{5}$

Transizione "4" -> "5":
c'è $1$ numero su un totale degli $1$ non estratti precedentemente che fa avvenire la transizione: $peso=\displaystyle \frac{\binom{1}{1}\binom{5-1}{3-1}}{\binom{5}{3}} = \frac{3}{5}$

Transizione "5" -> "5":
ci sono $3$ numeri su un totale dei $5$ estratti precedentemente che fanno avvenire la transizione: $peso=\displaystyle \frac{\binom{5}{3}\binom{5-5}{3-3}}{\binom{5}{3}} = 1$