Griglia infinita di uni e di zeri...
Immaginiamo una matrice infinita. Le varie celle possono essere bianche o nere (0 o 1 se preferite). Immaginiamo di partire da una casella, muovendoci solo in orizzontale e verticale, con la restrizione di camminare solo sulle caselle dello stesso colore di quella da cui siamo partiti. Il più delle volte definiamo così una certa "area" raggiungibile, oltre i confini della quale non possiamo andare perchè siamo bloccati da celle di colore diverso.
Uno potrebbe chiedersi: quant'è grande quest'area, in media? Dal momento che le idee combinatoriche che ho avuto al riguardo sono abbastanza difficili da portare a termine, ho provato con la foza bruta. Programmando un po' di routines in pari/gp (pace sia su di lui), sembrerebbe che l'area media oscilli intorno a valori come 57,59,62... eccetera. Abbastanza sorprendente...
Naturalmente sorgono pensieri di due tipi, che mi fanno dubitare che la risposta sia del tutto attendibile...
In primo luogo, per forza di cose la mia matrice non è infinita, dunque dovei tenere in conto l'approssimazione che faccio quando il programma va a sbattere contro il bordo e io gli dico di fermarsi.
Secondariamente, molte volte la media molto elevata che abbiamo osservato è dovuta in buona parte a un paio di valori sorprendentemente grandi, dunque proprio quei valori che, per l'osservazione precedente, avrebbero in alcuni casi potuto essere molto maggiori.
Magari, addirittura, la media potrebbe divergere, sebbene sia molto innaturale da pensare...
Insomma, adesso la solita domanda... qualcuno ha già studiato il problema?
Uno potrebbe chiedersi: quant'è grande quest'area, in media? Dal momento che le idee combinatoriche che ho avuto al riguardo sono abbastanza difficili da portare a termine, ho provato con la foza bruta. Programmando un po' di routines in pari/gp (pace sia su di lui), sembrerebbe che l'area media oscilli intorno a valori come 57,59,62... eccetera. Abbastanza sorprendente...
Naturalmente sorgono pensieri di due tipi, che mi fanno dubitare che la risposta sia del tutto attendibile...
In primo luogo, per forza di cose la mia matrice non è infinita, dunque dovei tenere in conto l'approssimazione che faccio quando il programma va a sbattere contro il bordo e io gli dico di fermarsi.
Secondariamente, molte volte la media molto elevata che abbiamo osservato è dovuta in buona parte a un paio di valori sorprendentemente grandi, dunque proprio quei valori che, per l'osservazione precedente, avrebbero in alcuni casi potuto essere molto maggiori.
Magari, addirittura, la media potrebbe divergere, sebbene sia molto innaturale da pensare...
Insomma, adesso la solita domanda... qualcuno ha già studiato il problema?
Risposte
"Rigel":
Ecco il codice.
Ti è difficile postare un file testo contenente la griglia ( 0, 1 ) delle 100 simulazioni da te effettuate ?
Mi è piu' facile lavorare su una "base dati comune" anzichè verificare il tuo codice.
Ehm, si tratta di griglie 1000x1000...
Per quel che può servire, ti posso postare l'output del programma:
181, 1, 4, 9, 3, 5, 2, 734, 2, 97,
128, 58, 2, 43, 4, 943, 1347, 5, 9, 795,
216, 38, 810, 123, 25, 305, 135, 145, 1181, 72,
26, 2, 127, 34, 29, 177, 3, 34, 22, 50758,
157, 25, 2, 8, 878, 18, 115, 5, 89, 67,
3, 47272, 20, 11, 446, 30, 4, 30, 23, 487,
367, 25, 12, 7, 52, 238, 7707, 479, 98905, 14,
11, 119, 52, 48, 10, 123, 16, 5, 13, 7,
1, 50, 3, 21240, 246, 23, 15, 52, 359, 28,
2916, 1, 1, 19, 1947, 136, 8, 37, 4, 15,
Media = 2436.350000, varianza = 146774187.340909
Sono in effetti sospetti i valori molto elevati (>10000); dovrei dare un'occhiata per vedere se ci sono problemi al bordo.
Per quel che può servire, ti posso postare l'output del programma:
181, 1, 4, 9, 3, 5, 2, 734, 2, 97,
128, 58, 2, 43, 4, 943, 1347, 5, 9, 795,
216, 38, 810, 123, 25, 305, 135, 145, 1181, 72,
26, 2, 127, 34, 29, 177, 3, 34, 22, 50758,
157, 25, 2, 8, 878, 18, 115, 5, 89, 67,
3, 47272, 20, 11, 446, 30, 4, 30, 23, 487,
367, 25, 12, 7, 52, 238, 7707, 479, 98905, 14,
11, 119, 52, 48, 10, 123, 16, 5, 13, 7,
1, 50, 3, 21240, 246, 23, 15, 52, 359, 28,
2916, 1, 1, 19, 1947, 136, 8, 37, 4, 15,
Media = 2436.350000, varianza = 146774187.340909
Sono in effetti sospetti i valori molto elevati (>10000); dovrei dare un'occhiata per vedere se ci sono problemi al bordo.
Quei lavori elevati sono effettivamente errati; aumentando la dimensione della griglia (e dunque la probabilità di finire al bordo) tendono a sparire.
Questi i risultati con griglia 2000x2000:
7, 1, 2412, 327, 9, 52, 28, 185, 1, 4,
19, 4291, 44, 56, 3, 15, 145, 1, 89, 8,
12, 20, 9, 8, 12, 3, 7, 20, 1, 1734,
2, 31, 6, 18, 5, 5507, 124, 1126, 15, 22,
1, 28, 58, 74, 12, 25, 2271, 1, 39, 277,
164, 365, 23, 130, 733, 37, 1, 229, 48, 56,
9, 4, 1682, 45, 8, 20, 2, 27, 132, 25,
14, 14, 119, 1, 117, 43, 8, 9, 3, 1,
408, 430, 5, 11, 155, 129, 60, 15, 38, 35,
54, 568, 11, 5, 680, 1, 75, 109, 67, 4,
Media = 260.940000, varianza = 629606.218586
E questi con griglia 3000x3000:
65, 5236, 110, 5, 170, 241, 8, 14, 22, 16,
51, 1, 70, 4, 550, 17, 10, 9, 1, 45,
64, 139, 1067, 1, 74, 82, 129, 30, 82, 10,
8, 1, 65, 7, 1, 79, 20, 6, 116, 1,
14, 4, 9, 3080, 689, 16, 1935, 48, 72, 48,
46, 10639, 335, 61, 22, 14, 1, 3, 30, 1,
581, 235, 8, 36, 5, 446, 12, 2187, 689, 32,
62, 20, 4237, 47, 11, 7, 8, 4, 267, 773,
1002, 73, 650, 7, 78, 1, 30, 3551, 203, 1,
10, 68, 122, 1, 1309, 56, 41, 6, 63, 35,
Media = 426.680000, varianza = 1799858.745051
Questi i risultati con griglia 2000x2000:
7, 1, 2412, 327, 9, 52, 28, 185, 1, 4,
19, 4291, 44, 56, 3, 15, 145, 1, 89, 8,
12, 20, 9, 8, 12, 3, 7, 20, 1, 1734,
2, 31, 6, 18, 5, 5507, 124, 1126, 15, 22,
1, 28, 58, 74, 12, 25, 2271, 1, 39, 277,
164, 365, 23, 130, 733, 37, 1, 229, 48, 56,
9, 4, 1682, 45, 8, 20, 2, 27, 132, 25,
14, 14, 119, 1, 117, 43, 8, 9, 3, 1,
408, 430, 5, 11, 155, 129, 60, 15, 38, 35,
54, 568, 11, 5, 680, 1, 75, 109, 67, 4,
Media = 260.940000, varianza = 629606.218586
E questi con griglia 3000x3000:
65, 5236, 110, 5, 170, 241, 8, 14, 22, 16,
51, 1, 70, 4, 550, 17, 10, 9, 1, 45,
64, 139, 1067, 1, 74, 82, 129, 30, 82, 10,
8, 1, 65, 7, 1, 79, 20, 6, 116, 1,
14, 4, 9, 3080, 689, 16, 1935, 48, 72, 48,
46, 10639, 335, 61, 22, 14, 1, 3, 30, 1,
581, 235, 8, 36, 5, 446, 12, 2187, 689, 32,
62, 20, 4237, 47, 11, 7, 8, 4, 267, 773,
1002, 73, 650, 7, 78, 1, 30, 3551, 203, 1,
10, 68, 122, 1, 1309, 56, 41, 6, 63, 35,
Media = 426.680000, varianza = 1799858.745051
"Lord K":
Mi viene in mente una distribuzione binomiale (di Bernoulli), considerando un cammino di [tex]n[/tex] passi con probabilità di continuare pari a [tex]1/2[/tex] con infiniti lanci... risulta che il valore atteso di quella area sia [tex]\infty[/tex] anche perchè il valore atteso della binomiale è un minorante del valore che l'area percorribile.
Non credo sia corretto: la binomiale si può applicare (ed è quello che hai fatto tu) per calcolare il valore atteso del numero di celle dello stesso colore di quella iniziale (che in una matrice infinita è difatti ovviamente illimitato), ma in questo caso conta anche come sono disposte le celle di uno stesso colore e di conseguenze che la cella j sia raggiungibile non dipende solo dal colore della cella stessa e di conseguenza gli eventi "la cella j è raggiungibile" NON sono indipendenti tra loro.
"Rigel":
Ehm, si tratta di griglie 1000x1000...
Non importa la grandezza.
Se riesci a generare il file, zippandolo (si tratta di un file testo) ottieni un valore di compressione molto alto
"Rigel":
Sono in effetti sospetti i valori molto elevati (>10000); dovrei dare un'occhiata per vedere se ci sono problemi al bordo.
Perchè ritieni sospetti questi valori elavati !!!
Secondo me, è normale che ci siano .... anzi, piu si va avanti più è facile "continuare"
Mi spiego meglio: è più facile che la "catena" si spezzi all'inizio che non dopo.
"Umby":
Secondo me, è normale che ci siano .... anzi, piu si va avanti più è facile "continuare"
Mi spiego meglio: è più facile che la "catena" si spezzi all'inizio che non dopo.
Mi sembra sensato: più aumenta il perimetro della "marea nera" e più è improbabile contenerla
"lukul":
fu^2: l'area "dovrebbe essere" (con elevata probabilità) finita perchè la tua matrice è binaria (consentimi questa accezione
per indicare che è composta solo dai numeri uno e da zero) e random (cioè avente una distribuzione CASUALE degli elementi)
dunque supponi che ogni pixel ha probabilità 0.5 di essere bianco e 0.5 di essere nero. Parlare di distribuzioni ha completamente senso.
In una dimensione l'area è limitata con probabilità uno, in dimensione due secondo me è falso come ho già detto.
"fu^2":
In una dimensione l'area è limitata con probabilità uno, in dimensione due secondo me è falso come ho già detto.
Cercavo di definire il problema così (e in questo modo mi muoverei per una eventuale dimostrazione), senza usare matrici predefinite in dimensione:
- la cella iniziale ha 4 adiacenti ognuna con $p=1/2$ di essere dello stesso colore, quindi ha un valore atteso di 2 celle adiacenti dello stesso colore;
- le celle adiacenti a queste sono 8, ma se considero il valore atteso di prima sono 5 (6 a seconda della configurazione), essendo sempre $p=1/2$ ho valore atteso di 2 (3) celle dello stesso colore;
- le celle adiacenti a queste sono 12, già le configurazioni si complicano ma credo si possa calcolare il valore atteso;
e possiamo proseguire, magari cercando una formula ricorsivamente utilizzabile.
Quindi è logico aspettarsi una varianza elevata dell'area, così come (sembra) è logico aspettarsi una area mediamente grande (infinita?). Magari dopo provo a fare un algoritmo.
"lukul":
Lord K: mi spiace, ma ciò che affermi contraddice i risultati numerici.
E perchè mai dovrebbe contraddirla? Tu non hai mai fatto prove su uno spazio infinito e qui il discorso statistico calza a pennello. Aiutami a capire plz.
"Rggb":
[quote="fu^2"]In una dimensione l'area è limitata con probabilità uno, in dimensione due secondo me è falso come ho già detto.
Cercavo di definire il problema così (e in questo modo mi muoverei per una eventuale dimostrazione), senza usare matrici predefinite in dimensione:
- la cella iniziale ha 4 adiacenti ognuna con $p=1/2$ di essere dello stesso colore, quindi ha un valore atteso di 2 celle adiacenti dello stesso colore;
- le celle adiacenti a queste sono 8, ma se considero il valore atteso di prima sono 5 (6 a seconda della configurazione), essendo sempre $p=1/2$ ho valore atteso di 2 (3) celle dello stesso colore;
- le celle adiacenti a queste sono 12, già le configurazioni si complicano ma credo si possa calcolare il valore atteso;
e possiamo proseguire, magari cercando una formula ricorsivamente utilizzabile.
Quindi è logico aspettarsi una varianza elevata dell'area, così come (sembra) è logico aspettarsi una area mediamente grande (infinita?). Magari dopo provo a fare un algoritmo.[/quote]
Le adiacenze non sono facilmente individuabili perchè dipendono dal percorso effettuato, infatti se pensi ad un percorso di sole 3 caselle puoi avere 8 o 7 adiacenze in base al percorso. Il processo che fa capo alla distribuzione di Bernoulli (o binomiale) continua a convincermi che il tutto non può che far supporre ad una area infinita e finora non ci sono algoritmi che mi convincano altrimenti.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo