Indovina il seme
Ho un mazzo di 40 carte da briscola. Quattro semi (denari, coppe, spade, bastoni) e dieci carte per ogni seme (da 1 a 10).
Il gioco è questo: scartare una carta dopo l'altra cercando di indovinarne il seme. Supponiamo di giocare in modo perfetto (vale a dire, ricordando le carte scese) assegnando una qualche preferenza ai semi, per esempio denari - coppe - spade - bastoni, in caso di parità di semi scesi.
La mia domanda è: qual è il numero medio di carte indovinate se si gioca in modo perfetto?
Procedendo a caso il numero medio è ovviamente 10, ma giocando con la memoria delle carte scese dovrebbe essere apprezzabilmente più alto.
Naturalmente uno può riformulare la cosa dicendo che le carte sono i numeri da 1 a 40 e la cosa da indovinare è la classe resto modulo 4. Io ho una idea di cosa potrebbe essere ma lo devo ancora dimostrare.
Il gioco è questo: scartare una carta dopo l'altra cercando di indovinarne il seme. Supponiamo di giocare in modo perfetto (vale a dire, ricordando le carte scese) assegnando una qualche preferenza ai semi, per esempio denari - coppe - spade - bastoni, in caso di parità di semi scesi.
La mia domanda è: qual è il numero medio di carte indovinate se si gioca in modo perfetto?
Procedendo a caso il numero medio è ovviamente 10, ma giocando con la memoria delle carte scese dovrebbe essere apprezzabilmente più alto.
Naturalmente uno può riformulare la cosa dicendo che le carte sono i numeri da 1 a 40 e la cosa da indovinare è la classe resto modulo 4. Io ho una idea di cosa potrebbe essere ma lo devo ancora dimostrare.
Risposte
Interessante...
Una domanda: perché quella precisazione sulla preferenza dei semi? Supponi di avere le tue 40 carte divise in 10 blu, 10 rosse, 10 verdi e 10 gialle, che motivo c'è di sapere - per dire - che le rosse vengono "prima" delle gialle? Oppure non ho capito, spiegami.
Una domanda: perché quella precisazione sulla preferenza dei semi? Supponi di avere le tue 40 carte divise in 10 blu, 10 rosse, 10 verdi e 10 gialle, che motivo c'è di sapere - per dire - che le rosse vengono "prima" delle gialle? Oppure non ho capito, spiegami.
"Rggb":E' per evitare di andare a caso una volta che i semi scesi sono alla pari. Per rendere la cosa algoritmica, insomma. Se tu non dessi una preferenza ai semi non sapresti (per dire) da che seme partire.
Una domanda: perché quella precisazione sulla preferenza dei semi? Supponi di avere le tue 40 carte divise in 10 blu, 10 rosse, 10 verdi e 10 gialle, che motivo c'è di sapere - per dire - che le rosse vengono "prima" delle gialle? Oppure non ho capito, spiegami.
Io alla prima carta dico "denari". Se viene denari, alla carta successiva devo scegliere uno dei semi più probabili (che sono coppe, spade e bastoni) e scelgo coppe perché viene prima di spade e bastoni nella mia preferenza. Se non facessi così alla seconda carta dovrei andare a caso e il procedimento non sarebbe univocamente determinato dalla sequenza in cui sono poste le carte.
Spero di essere stato chiaro
Chiarissimo: in questo modo garantisci la perfezione. Il ganzo è che - così a occhio - anche se non hai seme preferito e quindi a parità di carte uscite procedi sempre a caso, direi che il numero medio è lo stesso 
Sto pensando ad una soluzione
- solo pensando, per adesso niente carta&penna: mi viene in mente una sequenza di potenze...
Sto pensando ad una soluzione
- solo pensando, per adesso niente carta&penna: mi viene in mente una sequenza di potenze...
Bel problema; ti dico subito che la soluzione è ancora lontana.
Qualche considerazione.
Se vogliamo calcolare il numero medio di carte azzeccate la struttura di preferenza è irrilevante questo perchè la probabilità che tu azzecchi la carta non dipende da quello che dici ma da quello che è uscito;
serve soltanto a dare una struttura completamente determinata nella nostra selezione.
Se ragioniamo estrazione per estrazione sicuramente si individuano le prime $4$ probabilità che sono: $10/40\ 10/39\ 10/38\ 10/37$. Il problema arriva ora.
La quinta estrazione potrà avere probabilità di azzecarla $9/36$ se nelle prime quattro ho avuto $4$ semi diversi (la prob è $(((10),(1))^4)/(((40),(4)))$), mentre è $10/36$ con il complemento di quella.
Da un punto di vista logico si potrebbe continuare a ragionare in questa maniera; il problema è che risulta essere molto oneroso da un punto di vista computazionale (vengono una cosa tipo un centinaio di probabilità). Si dovrebbe trovare una formula in funzione dell'estrazioni effettuate e del valore massimo che un seme può possedere (che aumenta al crescere delle quaterne strazioni), se uno vi riuscisse poi lo fa fare al computer.
Il risutato atteso comunque migliora perchè iterando questa logica abbiamo che la probabilità di azzecare l'estrazione i-esima è maggiore di $([(40-i)/4]+1)/(40-i+1)$ (con la quadra intendo la parte intera), cioè nelle prime quattro al numeratore abbiamo sempre $10$; dalla 5 alla 8 abbiamo o $9$ e così via. Con la probabilità limitante che ho scritto sopra si considera la strada più pessimistica ovvero che ogni $4$ carte mi escono tutti semi diversi.
Con questo si conclude che il valore atteso è maggiore di (se non ho commesso errori di calcolo) $11.966$ circa, che però è una bela sottostima; pensa infatti all'ultima carta e quella viene prob $1$; per la penultima la limitazione da un mezzo ma se sono dello stesso seme è uno.
Queste diciamo sono le prime impressioni che ho avuto, te che idee hai?
Qualche considerazione.
Se vogliamo calcolare il numero medio di carte azzeccate la struttura di preferenza è irrilevante questo perchè la probabilità che tu azzecchi la carta non dipende da quello che dici ma da quello che è uscito;
serve soltanto a dare una struttura completamente determinata nella nostra selezione.
Se ragioniamo estrazione per estrazione sicuramente si individuano le prime $4$ probabilità che sono: $10/40\ 10/39\ 10/38\ 10/37$. Il problema arriva ora.
La quinta estrazione potrà avere probabilità di azzecarla $9/36$ se nelle prime quattro ho avuto $4$ semi diversi (la prob è $(((10),(1))^4)/(((40),(4)))$), mentre è $10/36$ con il complemento di quella.
Da un punto di vista logico si potrebbe continuare a ragionare in questa maniera; il problema è che risulta essere molto oneroso da un punto di vista computazionale (vengono una cosa tipo un centinaio di probabilità). Si dovrebbe trovare una formula in funzione dell'estrazioni effettuate e del valore massimo che un seme può possedere (che aumenta al crescere delle quaterne strazioni), se uno vi riuscisse poi lo fa fare al computer.
Il risutato atteso comunque migliora perchè iterando questa logica abbiamo che la probabilità di azzecare l'estrazione i-esima è maggiore di $([(40-i)/4]+1)/(40-i+1)$ (con la quadra intendo la parte intera), cioè nelle prime quattro al numeratore abbiamo sempre $10$; dalla 5 alla 8 abbiamo o $9$ e così via. Con la probabilità limitante che ho scritto sopra si considera la strada più pessimistica ovvero che ogni $4$ carte mi escono tutti semi diversi.
Con questo si conclude che il valore atteso è maggiore di (se non ho commesso errori di calcolo) $11.966$ circa, che però è una bela sottostima; pensa infatti all'ultima carta e quella viene prob $1$; per la penultima la limitazione da un mezzo ma se sono dello stesso seme è uno.
Queste diciamo sono le prime impressioni che ho avuto, te che idee hai?
Io ho avuto qualche idea ma devo elaborare meglio quello che ho pensato. Sto partendo da un caso facile: 4 carte e 2 semi. Qui il numero medio risulta [tex]2.8\bar{3}[/tex]. Con 4 carte e 4 semi il numero medio è [tex]2.08\bar{3}[/tex].
Diciamo che n=40 è il numero di carte e k=4 è il numero di semi. Indichiamo con S l'insieme di tutte le possibili sequenze delle n carte, e data una sequenza s (cioè un elemento di S) chiamiamo [tex]i_p(s)[/tex] il numero di carte indovinate nella sequenza s con preferenza p (una "preferenza" è come sopra: un ordine dato ai semi). Dobbiamo calcolare il numero
[tex]M(n,k):=\frac{1}{n!} \sum_{s \in S}i_p(s)[/tex].
Per fare questo potrebbe risultare utile osservare che detto P l'insieme delle preferenze (ha [tex]k![/tex] elementi) si ha
[tex]\frac{1}{k!} \sum_{p \in P} \frac{1}{n!} \sum_{s \in S}i_p(s) = \frac{1}{n!} \sum_{s \in S}i_p(s) = M(n,k)[/tex].
In particolare si ha [tex]M(n,k) = \frac{1}{n!} \sum_{s \in S} \frac{1}{k!} \sum_{p \in P} i_p(s)[/tex]. Quindi anziché mediare sulle sequenze direttamente uno potrebbe tentare di mediare prima sulle preferenze e poi sulle sequenze. Questo dovrebbe semplificare il problema.
Comunque come ho detto ci devo pensare bene ancora.
Diciamo che n=40 è il numero di carte e k=4 è il numero di semi. Indichiamo con S l'insieme di tutte le possibili sequenze delle n carte, e data una sequenza s (cioè un elemento di S) chiamiamo [tex]i_p(s)[/tex] il numero di carte indovinate nella sequenza s con preferenza p (una "preferenza" è come sopra: un ordine dato ai semi). Dobbiamo calcolare il numero
[tex]M(n,k):=\frac{1}{n!} \sum_{s \in S}i_p(s)[/tex].
Per fare questo potrebbe risultare utile osservare che detto P l'insieme delle preferenze (ha [tex]k![/tex] elementi) si ha
[tex]\frac{1}{k!} \sum_{p \in P} \frac{1}{n!} \sum_{s \in S}i_p(s) = \frac{1}{n!} \sum_{s \in S}i_p(s) = M(n,k)[/tex].
In particolare si ha [tex]M(n,k) = \frac{1}{n!} \sum_{s \in S} \frac{1}{k!} \sum_{p \in P} i_p(s)[/tex]. Quindi anziché mediare sulle sequenze direttamente uno potrebbe tentare di mediare prima sulle preferenze e poi sulle sequenze. Questo dovrebbe semplificare il problema.
Comunque come ho detto ci devo pensare bene ancora.
Il caso peggiore è stato descritto da Daje (per ogni gruppo di 4 carte, 4 semi diversi).
In questa condizione abbiamo la speranza di indovinare circa 12 carte (concordo con il 11,966 di daje) (anzichè 10 - il 10 inteso come 1/4 per 40 carte, ovvero in caso di reimmissione).
Il migliore dei casi è quello che le prime 30 escono solo 3 semi, in questa situazione abbiamo una speranza di indovinare circa 23,5 carte.
Tra questi due "limiti" tutte le altre combinazioni.
Non dovrebbe essere difficile simulare con il pc, tutte le varie combinazioni, cosi' da trovare un valore medio.
In questa condizione abbiamo la speranza di indovinare circa 12 carte (concordo con il 11,966 di daje) (anzichè 10 - il 10 inteso come 1/4 per 40 carte, ovvero in caso di reimmissione).
Il migliore dei casi è quello che le prime 30 escono solo 3 semi, in questa situazione abbiamo una speranza di indovinare circa 23,5 carte.
Tra questi due "limiti" tutte le altre combinazioni.
Non dovrebbe essere difficile simulare con il pc, tutte le varie combinazioni, cosi' da trovare un valore medio.
"Umby":
Non dovrebbe essere difficile simulare con il pc, tutte le varie combinazioni, cosi' da trovare un valore medio.
Fatto. Una prima simulazione mi fornisce (circa) $n=13.37$ ovvero 13 come numero medio.
"Rggb":
[quote="Umby"]Non dovrebbe essere difficile simulare con il pc, tutte le varie combinazioni, cosi' da trovare un valore medio.
Fatto. Una prima simulazione mi fornisce (circa) $n=13.37$ ovvero 13 come numero medio.[/quote]
Sono curioso di sapere come hai costruito la simulazione
"Martino":
Con 4 carte e 4 semi il numero medio è [tex]2.08\bar{3}[/tex].
Calcolato direttamente, "a mano" per capirci, o tramite la tua (abbozzo di) idea?
Comunque, il mio simulatore non dovrebbe avere errori poiché trova lo stesso risultato... oppure abbiamo sbagliato entrambi lo stesso calcolo
"DajeForte":
Sono curioso di sapere come hai costruito la simulazione
Eccolo qui.
// carte.c 1.0.1 by RGGB 10-AUG-2010, 11-AUG-2010 (C) none
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
#define N_LOOPS 10000
#define DBG
#define N_CARDS 40
#define N_SEEDS 4
int main(int argn, char *argv)
{
double avg; // media (calcolata, non intera)
int tot, // totale semi azzeccati in tutte le giocate
deck[N_CARDS], // Il mio mazzo di carte
seed[N_SEEDS], // I semi usciti nelle giocate
mySeed, // Che seme "gioco"
min, // Quale seme e' minimo
i, j, k;
// Messaggio di inizio (?)
printf("\nSimulazione di un gioco matematico di carte.");
srand((int) getpid());
// Ciclo esterno per quante simulazioni voglio generare
printf("\nInizio di %d simulazioni...", N_LOOPS);
tot=0;
avg=0.0;
for (i=0; i < N_LOOPS; i++)
{
DBG if (!(i%1000)) printf(".");
// Imposta i totali semi mescolati
k=N_CARDS/N_SEEDS;
for (j=0; j < N_SEEDS; j++) seed[j]=k;
// Mescola le carte
for (j=0; j < N_CARDS; j++)
{
while(1)
{
//k=4*random()/RAND_MAX;
k=rand()%N_SEEDS;
if (k >= 0 && k < N_SEEDS && seed[k] > 0)
{
// Carta correttamente mescolata
deck[j]=k;
seed[k]--;
break;
};
};
};
DBG if (!(i%1000))
DBG {
DBG printf("\nMazzo corrente:\n");
DBG for (j=0; j < N_CARDS; j++) printf("%d", deck[j]);
DBG };
// Imposta i totali estratti
for (j=0; j < N_SEEDS; j++) seed[j]=0;
// "Si gioca"
for (j=0; j < N_CARDS; j++)
{
// La mia scelta: quello minore
mySeed=0;
min=seed[0];
for (k=1; k < N_SEEDS; k++)
{
if (min > seed[k]) { mySeed=k; min=seed[k]; };
};
// Verifico se la mia scelta e' indovinata
if (mySeed == deck[j]) tot++;
// Comunque incremento semi usciti
seed[deck[j]]++;
};
};
printf("\nfine.");
// Stampa risultato
printf("\nTotale %d indovinate su %d simulazioni, con %d carte e %d semi.",
tot, N_LOOPS, N_CARDS, N_SEEDS);
avg=(double) tot / (double) N_LOOPS;
printf("\nLa media di indovinate per giocata di %d carte e' %f\n\n",
N_CARDS, avg);
};//(main)
Non fate caso ai "DBG"
EDIT: piccole modifiche al codice, ora è di uso più generale.
Molto interessante! Io facendo un ragionamento alla buona credevo che il valore medio potesse essere 25, ma evidentemente mi sbagliavo alla grande.
Oggi ci ho pensato un po'. Con 6 carte e 2 semi il valore medio viene 4.1 (confermi Rggb?). Questi valori medi nei casi piccoli li trovo facendo i conti a mano. Non è difficile, nel caso di 6 carte e 2 semi si tratta di scrivere 20 sequenze binarie (quelle corrispondenti alle sequenze originali di cifre da 1 a 6 ridotte modulo 2), calcolare per ogni sequenza il numero di carte indovinate e fare la media (vd. tabella qui sotto).
Il problema è che non sembra esserci un metodo diretto per calcolare il numero di carte indovinate di una data sequenza.
Per esempio la sequenza 111000 con preferenza "10" ha numero 4, e con preferenza "01" ha 3. Quindi il numero medio sulle preferenze è 3.5. Questa regola che associa ad una sequenza la media sulle preferenze resta misteriosa.
[tex]\begin{array}{c|c|c|c} \text{sequenza} & p=[10] & p=[01] & \text{media} \\ \hline 111000 & 4 & 3 & 3.5 \\ \hline 000111 & 3 & 4 & 3.5 \\ \hline 110100 & 4 & 3 & 3.5 \\ \hline 001011 & 3 & 4 & 3.5 \\ \hline 110010 & 5 & 3 & 4 \\ \hline 001101 & 3 & 5 & 4 \\ \hline 110001 & 4 & 4 & 4 \\ \hline 001110 & 4 & 4 & 4 \\ \hline 101100 & 5 & 3 & 4 \\ \hline 010011 & 3 & 5 & 4 \end{array}[/tex] [tex]\begin{array}{c|c|c|c} \text{sequenza} & p=[10] & p=[01] & \text{media} \\ \hline 101010 & 6 & 3 & 4.5 \\ \hline 010101 & 3 & 6 & 4.5 \\ \hline 101001 & 5 & 4 & 4.5 \\ \hline 010110 & 4 & 5 & 4.5 \\ \hline 100101 & 4 & 5 & 4.5 \\ \hline 011010 & 5 & 4 & 4.5 \\ \hline 100110 & 5 & 4 & 4.5 \\ \hline 011001 & 4 & 5 & 4.5 \\ \hline 100011 & 4 & 4 & 4 \\ \hline 011100 & 4 & 4 & 4 \end{array}[/tex]
Come si vede la media delle medie è 4.1.
Oggi ci ho pensato un po'. Con 6 carte e 2 semi il valore medio viene 4.1 (confermi Rggb?). Questi valori medi nei casi piccoli li trovo facendo i conti a mano. Non è difficile, nel caso di 6 carte e 2 semi si tratta di scrivere 20 sequenze binarie (quelle corrispondenti alle sequenze originali di cifre da 1 a 6 ridotte modulo 2), calcolare per ogni sequenza il numero di carte indovinate e fare la media (vd. tabella qui sotto).
Il problema è che non sembra esserci un metodo diretto per calcolare il numero di carte indovinate di una data sequenza.
Per esempio la sequenza 111000 con preferenza "10" ha numero 4, e con preferenza "01" ha 3. Quindi il numero medio sulle preferenze è 3.5. Questa regola che associa ad una sequenza la media sulle preferenze resta misteriosa.
[tex]\begin{array}{c|c|c|c} \text{sequenza} & p=[10] & p=[01] & \text{media} \\ \hline 111000 & 4 & 3 & 3.5 \\ \hline 000111 & 3 & 4 & 3.5 \\ \hline 110100 & 4 & 3 & 3.5 \\ \hline 001011 & 3 & 4 & 3.5 \\ \hline 110010 & 5 & 3 & 4 \\ \hline 001101 & 3 & 5 & 4 \\ \hline 110001 & 4 & 4 & 4 \\ \hline 001110 & 4 & 4 & 4 \\ \hline 101100 & 5 & 3 & 4 \\ \hline 010011 & 3 & 5 & 4 \end{array}[/tex] [tex]\begin{array}{c|c|c|c} \text{sequenza} & p=[10] & p=[01] & \text{media} \\ \hline 101010 & 6 & 3 & 4.5 \\ \hline 010101 & 3 & 6 & 4.5 \\ \hline 101001 & 5 & 4 & 4.5 \\ \hline 010110 & 4 & 5 & 4.5 \\ \hline 100101 & 4 & 5 & 4.5 \\ \hline 011010 & 5 & 4 & 4.5 \\ \hline 100110 & 5 & 4 & 4.5 \\ \hline 011001 & 4 & 5 & 4.5 \\ \hline 100011 & 4 & 4 & 4 \\ \hline 011100 & 4 & 4 & 4 \end{array}[/tex]
Come si vede la media delle medie è 4.1.
"Martino":
Oggi ci ho pensato un po'. Con 6 carte e 2 semi il valore medio viene 4.1 (confermi Rggb?).
Confermo, anche se con la simulazione mi viene un valore leggermente minore (3.94 circa).
Comunque se "copincolli" il codice puoi fare prove anche su casi con numero di semi/carte differenti, e magari intuire una regola generale. Non ci sono particolari opzioni per il compilatore (usa gcc, o.c.). NB che stamattina ho fatto due piccole modifiche.
"Martino":
Il problema è che non sembra esserci un metodo diretto per calcolare il numero di carte indovinate di una data sequenza.
Vedi sopra: magari ci viene in mente qualcosa dai calcoli. Certo, dal "venirci in mente" a "dimostrare che" c'è un bel po' da fare...
@Rggb: secondo me la tua simulazione sottostima il valore cercato. Infatti un errore del 4% sui 4.1 aspettati mi sembra un pochino troppo anche in considerazione che ci sono solamente 20 possibili permutazioni. Inoltre a te viene una media (col mazzo completo) 13.37 che (secondo me) è troppo vicina al limite inferiore che abbiamo trovato.
In un programma che ho scritto a me viene 14.68.
In un programma che ho scritto a me viene 14.68.
Forse sono riuscito a trovare la formula per due semi. Rggb, puoi provare a vedere se corrisponde a qualche risultato sperimentale?
Ho provato con n=6 e torna.
E' questa (n è il numero di carte): [tex]\displaystyle \text{Media}(n,2) = \frac{\sum_{k=1}^{n/2} \frac{2k+1}{2k} \binom{2k-2}{k-1} 2^{n-2k}}{\frac{1}{2} \binom{n}{n/2}}[/tex]
Ho provato con n=6 e torna.
E' questa (n è il numero di carte): [tex]\displaystyle \text{Media}(n,2) = \frac{\sum_{k=1}^{n/2} \frac{2k+1}{2k} \binom{2k-2}{k-1} 2^{n-2k}}{\frac{1}{2} \binom{n}{n/2}}[/tex]
Scusate il ritardo, sono andato a funghi 
(e fra l'altro son tornato con le pive nel sacco...)
Non ho trovato errori nel mio algoritmo, ma ovviamente l'esperienza di debugging mi dice "se ti dicono che l'errore c'è vuol dire che c'è"... sto ricontrollando, ti farò sapere.
Puoi postare un po' di codice, che confronto gli algoritmi?
(e fra l'altro son tornato con le pive nel sacco...)"DajeForte":
@Rggb: secondo me la tua simulazione sottostima il valore cercato. Infatti un errore del 4% sui 4.1 aspettati mi sembra un pochino troppo anche in considerazione che ci sono solamente 20 possibili permutazioni. Inoltre a te viene una media (col mazzo completo) 13.37 che (secondo me) è troppo vicina al limite inferiore che abbiamo trovato.
Non ho trovato errori nel mio algoritmo, ma ovviamente l'esperienza di debugging mi dice "se ti dicono che l'errore c'è vuol dire che c'è"... sto ricontrollando, ti farò sapere.
"DajeForte":
In un programma che ho scritto a me viene 14.68.
Puoi postare un po' di codice, che confronto gli algoritmi?
"Rggb":
Non ho trovato errori nel mio algoritmo, ma ovviamente l'esperienza di debugging mi dice "se ti dicono che l'errore c'è vuol dire che c'è"... sto ricontrollando, ti farò sapere.
[...]
Puoi postare un po' di codice, che confronto gli algoritmi?
Io purtoppo il C non lo so usare (ed è una grave mancanza) e quindi non so leggere il programma per trovare dove sia il baco.
Ho scritto questo codice in R che però è carente in termini di tempistiche.
N=10000
nc=2
ns=3
k1=nc*ns
y=ns+1-1/nc
R=matrix(NA,(nc*ns),N)
P=matrix(NA,(nc*ns),N)
P[1,]=1/ns
for(j in 1:N){
S=seq(1,y,1/nc)
for(i in 1:(k1-1)){
a=S[floor(runif(1,1,(k1+2-i)))]
S=setdiff(S,a)
K=as.data.frame(table(floor(S)))
P[i+1,j]=max(K\$Freq)/(k1-i)
}}
q=apply(P,2,sum)
mean(q)
sd(q)
sd(q)/mean(q)
Non so come fare a scriverti le spiegazioni perchè mi azzera gli spazzi. Comunque nel primo blocco ci sono gli input (simulazioni e composizione del mazzo); nel secondo crea variabili di comodo; nel for costruisce l'urna e genera le estrazioni (qua si deve ottimizzare sia ottimizzando quello che ho scritto sia invece cambiando gli elementi che si vanno a simulare) ed infine hai il risultato (mean(q)) e qualche misura di scostamento dei risutati delle singole traiettorie.
Sono comunque sicuro che sia giusto perchè mi ritorna i numeri corretti per valori di piccole dimensioni.
A questo punto ho scritto anche un altro codice che calcola il numero medio esatto, secondo la logica che ho descritto nel mio primo post.
Nel probema mazzo napoletano questo è $14.66626$, che quindi è molto vicino al numero generato dalla mia simulazione (col mazzo francese mi viene $18.4007$).
Questo poi nel caso di due semi (caso molto esemplificato) restituisce il risultato di Martino.
"Martino":
E' questa (n è il numero di carte): [tex]\displaystyle \text{Media}(n,2) = \frac{\sum_{k=1}^{n/2} \frac{2k+1}{2k} \binom{2k-2}{k-1} 2^{n-2k}}{\frac{1}{2} \binom{n}{n/2}}[/tex]
Ti riporto alcuni valori di stima calcolati col simulatore (errato? spero non più del 4% calcolato da DajeForte):
$n=100, m=53.9$
$n=400, m=207.9$
$n=1000, m=512.5$
EDIT:
Prima verifica, spero di aver calcolato bene, la formula di Martino mi fornisce $m=55.78$ per $n=100$ (sempre due semi)... siamo in linea con quanto diceva DajeForte, ovvero c'è qualcosa che non va. Ma ho verificato ancora (ed ancora non ho trovato l'errore...), e chiedo: non è che stiamo calcolando semplicemente due valori differenti?
Io, brutalmente, calcolo la media con $M=\text{numero di volte che ho indovinato}/\text{numero di volte che ho giocato}$
Mi sono incaponito sul problema!
In effetti questo mi capita spesso quando trovo un "errore" misterioso. Ciò è dovuto al fatto che sia il mio algoritmo (che genera sequenze casuali) sia il conteggio manuale dei casi semplici sia l'algoritmo di DajeForte mi sembrano corretti. Ancora non ne sono venuto a capo
Però alcune considerazioni:
Ma non è necessario calcolare ogni sequenza (v. sotto).
Ogni sequenza differente ha uguale media (puoi verificarlo facilmente), quindi ti basta di calcolare per una sola sequenza, e direi di usare la più "naturale" 0, 1, 2, 3...
Questo dovrebbe semplificarti le formule (oppure l'hai già considerato, in tal caso /ignore me/).
Come la media di qualunque sequenza
Fra l'altro ho fatto la "controprova sperimentale". Pur assumendo ci sia un errore nel mio algoritmo, con una piccola modifica ho fatto sì che, invece di scegliere una data sequenza prefissata, quando "non sa cosa scegliere" scelga a caso. Ovviamente i risultati che ottengo sono identici. Infatti avevo detto
Passo la palla a Martino per le spiegazioni della sua formula, ché mi ha incuriosito.
In effetti questo mi capita spesso quando trovo un "errore" misterioso. Ciò è dovuto al fatto che sia il mio algoritmo (che genera sequenze casuali) sia il conteggio manuale dei casi semplici sia l'algoritmo di DajeForte mi sembrano corretti. Ancora non ne sono venuto a capo
Però alcune considerazioni:
"Martino":
Non è difficile, nel caso di 6 carte e 2 semi si tratta di scrivere 20 sequenze binarie (quelle corrispondenti alle sequenze originali di cifre da 1 a 6 ridotte modulo 2), calcolare per ogni sequenza il numero di carte indovinate e fare la media (vd. tabella qui sotto).
Ma non è necessario calcolare ogni sequenza (v. sotto).
"Martino":
Il problema è che non sembra esserci un metodo diretto per calcolare il numero di carte indovinate di una data sequenza.
Per esempio la sequenza 111000 con preferenza "10" ha numero 4, e con preferenza "01" ha 3. Quindi il numero medio sulle preferenze è 3.5. Questa regola
che associa ad una sequenza la media sulle preferenze resta misteriosa.
Ogni sequenza differente ha uguale media (puoi verificarlo facilmente), quindi ti basta di calcolare per una sola sequenza, e direi di usare la più "naturale" 0, 1, 2, 3...
Questo dovrebbe semplificarti le formule (oppure l'hai già considerato, in tal caso /ignore me/).
"Martino":
Come si vede la media delle medie è 4.1.
Come la media di qualunque sequenza
Fra l'altro ho fatto la "controprova sperimentale". Pur assumendo ci sia un errore nel mio algoritmo, con una piccola modifica ho fatto sì che, invece di scegliere una data sequenza prefissata, quando "non sa cosa scegliere" scelga a caso. Ovviamente i risultati che ottengo sono identici. Infatti avevo detto
"Rggb":
Il ganzo è che - così a occhio - anche se non hai seme preferito e quindi a parità di carte uscite procedi sempre a caso, direi che il numero medio è lo stesso
Passo la palla a Martino per le spiegazioni della sua formula, ché mi ha incuriosito.
Siano [tex]n[/tex] il numero delle carte ed [tex]s[/tex] il numero dei semi, allora necesariamente con la strategia del "seme preferito", che avete utilizzato, avrete che le carte indovinate sono sensibilmente superiori a [tex]\frac{n}{s}[/tex].
Sto seguendo il vostro discorso e con VBA ho duplicato i vostri algoritmi, ma siamo sicuri che la strategia del "seme preferito" sia la migliore???
Sto seguendo il vostro discorso e con VBA ho duplicato i vostri algoritmi, ma siamo sicuri che la strategia del "seme preferito" sia la migliore???
@Rggb: Ancora sono all'oscuro del funzionamento del tuo programma, sto provando a leggerlo in tutti i modi ma non ci riesco.
Però ti consiglierei di fare qualche prova stupida del tipo:
dipende da come lavora il programma (questa va bene per quello della simulazione che ho scritto)
metti una carta sola per seme ed un po di semi (quanti vuoi).
A questo punto nel mio prog tutte letraiettorie restituiscono esattamente quel valore perchè indipendentemente da cosa esce la strategia/struttura è quella.
Per quanto riguarda la preferenza come dici non cambia ai fini del valore atteso anche perchè se tu vai a prenderti la tabella è facile vedere che ci sono dei comportamenti a specchio delle sequenze secondo le due preferenze.
P.S. ma poi a me il tuo programma manco lo compila mi spara subito errore.
ma fai qualcosa di particolare; io lo ho salvato poi lo compilo con gpp.
Vabe vediamo domani
Ciao
Però ti consiglierei di fare qualche prova stupida del tipo:
dipende da come lavora il programma (questa va bene per quello della simulazione che ho scritto)
metti una carta sola per seme ed un po di semi (quanti vuoi).
A questo punto nel mio prog tutte letraiettorie restituiscono esattamente quel valore perchè indipendentemente da cosa esce la strategia/struttura è quella.
Per quanto riguarda la preferenza come dici non cambia ai fini del valore atteso anche perchè se tu vai a prenderti la tabella è facile vedere che ci sono dei comportamenti a specchio delle sequenze secondo le due preferenze.
P.S. ma poi a me il tuo programma manco lo compila mi spara subito errore.
ma fai qualcosa di particolare; io lo ho salvato poi lo compilo con gpp.
Vabe vediamo domani
Ciao
Salve ragazzi
Scusate ma ho avuto problemi con la connessione.
Ora cerco di scrivere il procedimento che mi ha portato alla formula e postarlo.
Rggb, puoi confrontare la mia formula con le prove sperimentali nel caso di 40 carte e 2 semi? Dovrebbe risultare esatto.
Scusate ma ho avuto problemi con la connessione.
"Rggb":Certo, ovvio! Ma mi chiedevo appunto se mediare prima sulle preferenze semplificasse il problema. Per esempio, mi sembra proprio che il caso di due soli semi sia risolvibile con questa tecnica.
Ogni sequenza differente ha uguale media (puoi verificarlo facilmente), quindi ti basta di calcolare per una sola sequenza, e direi di usare la più "naturale" 0, 1, 2, 3...
Ora cerco di scrivere il procedimento che mi ha portato alla formula e postarlo.
Rggb, puoi confrontare la mia formula con le prove sperimentali nel caso di 40 carte e 2 semi? Dovrebbe risultare esatto.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo