www.vincenzomanzoni.com

[Omino Na]

Problema dibattuto con amici, mi sembrava interessante postarlo.

E' data una matrice A di NxN, riempita casualmente di zeri e uni (N>=3). Sia data una matrice B di 3x3 anch'essa riempita casualmente di zeri e di uni.
Sia X la variabile aleatoria "Il numero di volte che la matrice B � contenuta come sottomatrice nella matrice A".

Per N=3, la A diventa di 3x3, e la probabilit� di trovare nella matrice B la matrice A � uguale alla probabilit� che A==B. Dunque 1/2^9, dato che ogni valore della matrice pu� assumere 2 valori, e che i valori sono 9. Dunque il valore attesto per trovare B in A � di 1/2^9. E' una Bernoulli di parametro p=1/2^9. E ci siamo.

Ora sia N generico. Non � difficile dimostrare che le possibili sottomatrici 3x3 contenute in una matrice NxN sono (N-2)^2. Dunque, il tutto si riduce a chiedersi: quante volte la B � uguale a una di queste sottomatrici della A. Ossia abbiamo (N-2)^2 bernoulli di parametro 1/2^9. Il valore attesto � dunque il prodotto dei due parametri, ovvero (N-2)^2 / 2^9. Ma c'� ancora qualche osservazione interessante dal punto di vista teorico.

(se servisse qui c'� un programma in Matlab che svolge tutti i calcoli: http://web.rossoalice.it/daniele_ghisi/altro/matbin.m)

- Che la matrice piccola B sia casuale � COMPLETAMENTE IRRILEVANTE ai fini dell'esperimento. Potremmo prenderne una fissata, ad esempio anche quella con tutti zeri. Sarebbe completamente irrilevante.
- Che la matrice A sia casuale � SOSTANZIALE. Questa sua composizione aleatoria di zeri e uni, infatti, garantisce l'indipendenza della "scansione". Mi spiego meglio. Prendiamo N=4. Ossia, prendiamo una 4x4 e vedi quante volte contiene una 3x3 fissata (o casuale, come detto � la stessa cosa): iniziamo a prendere la prima sottomatrice 3x3, quella in alto a sinistra. Vediamo se coincide oppure no. Spostiamo tutto a destra di un "gradino", e abbiamo un'altra sottomatrice 3x3. In generale, questa sottomatrice DIPENDE SENSIBILMENTE dalla matrice precedente - hanno due colonne in comune!! Ma se la matrice A � casualmente composta da 1 e 0 (con gli 1 e 0 distribuiti uniformemente), spostandomi a destra di un gradino, ottengo un'altra sottomatrice COMPLETAMENTE CASUALE, esattamente quanto quella precedente, pertanto formalmente (e praticamente) indipendente dalla precedente!!! Gli elementi della mia sottomatrice di "scansione", cambiano aleatoriamente, pertanto � come se io avessi ogni volta una matrice indipendente dalla precedente.

E qui il problema sarebbe risolto. Abbiamo il valore attesto (N-2)^2/2^9, confermato dal computer. Ma complichiamoci la vita.
Abbiamo detto che l'aleatoriet� di B � irrilevante.
L'aleatoriet� di A NO.
Prendendo una A fissata, prendendo una B aleatoria, vedendo quante volte questa B � contenuta nella A fissata, si ottengono risultati del tutto diversi. Esempio. Con N=100, consideriamo la matrice A fissata, composta da tutti ZERI (oppure tutti UNI, � simmetrico il problema, e sono uguali i risultati, ovviamente), prendendo una B aleatoria, vedendo quante volte � contenuta, ripetendo l'esperimento pi� volte, vediamo che la media si attesta a un valore ben diverso da quello di prima. In generale (qualitativamente) questo valore � tanto pi� alto tanto maggiore � la "simmetria interna" della matrice A (dunque dovrebbe avere un massimo per A composta da tutti zeri o tutti uni). Sarebbe interessante tradurre questo concetto anche quantitativamente.
_________________
"Se un matematico e un fisico riescono a mettersi d'accordo su una cosa � molto ma molto probabile che questa sia vera." (Wiso, da it.scienza.matematica)

[Andrea]

[Omino Na]