Discussione:
Estrapolazione con grafico
(troppo vecchio per rispondere)
Cristiano
2012-02-09 23:30:31 UTC
Permalink
Ho tutti questi punti:
Loading Image...

Vorrei stimare l'ordinata massima intorno a x = 100.

Ho, allora, interpolato tutti i punti (minimizzando il chi-quadro)
ottenendo la linea continua del grafico. Poi ho moltiplicato per una
costante la funzione interpolatrice ottenendo la linea tratteggiata (che
approssima bene i vari picchi).

Può essere un sistema attendibile?

Grazie
Cristiano
Tommaso Russo, Trieste
2012-02-10 00:06:50 UTC
Permalink
Non e' un problema matematico: epistemologico, piuttosto. O di filosofia
delle Scienze Naturali.
Post by Cristiano
http://cristianopi.altervista.org/MS_grafico.gif
Vorrei stimare l'ordinata massima intorno a x = 100.
Sembrerebbe una distribuzione stocastica. Gia' il concetto di "valore
massimo" per una distribuzione stocastica non ha molto senso. Al piu'
puoi definire un valore al di sopra del quale cadra' *meno di* una
frazione eps del totale, con eps scelto in modo da poter dire "sono
talmente pochi casi che ce ne possiamo fregare".
Post by Cristiano
Ho, allora, interpolato tutti i punti (minimizzando il chi-quadro)
ottenendo la linea continua del grafico.
Ma... non stai ovviamente parlando di tutti i punti. Per ogni x, gli y
misurati si suddividono in due cluster. Hai eliminato i cluster
inferiori? Quelli che arrivano fino a 4096 per x=51, 16384 per x=59 e
cosi' via?
Post by Cristiano
Poi ho moltiplicato per una
costante la funzione interpolatrice ottenendo la linea tratteggiata (che
approssima bene i vari picchi).
Può essere un sistema attendibile?
No, se non hai un'ipotesi sottostante che la giustifichi. Ipotesi
possibilmente da verificare con qualche test statistico sui dati gia'
disponibili.

Visto che la tua y ha una scala logaritmica mentre x e' lineare, andare
in cerca di una retta interpolante sembrerebbe aver fatto implicitamente
un'ipotesi per cui y=k1*exp(k2*x). + o - qualche errore o variabile casuale.

In questo caso, le distribuzioni dei punti centrati attono le
intersezioni della retta interpolante con x=51,53,55...71 potrebbero
essere ellissoidi d'errore (ma sto cercando di indovinare il perche' dei
gap in corrispondenza dei valori pari di x. Il vero motivo lo sai solo tu).

E, sempre in questo caso, l'ipotesi che fai moltiplicando la retta
interpolatrice per una costante assume che anche la varianza verticale
abbia un'andamento del tipo k3*exp(k2*x), e che l'assenza di punti
visibili equivalga a una frequenza minore dell'eps che hai
implicitamente scelto.

Insomma, dati insufficienti.


Piu' in generale: la scelta di una funzione interpolatrice non e' mai un
problema matematico. La sua forma *deve* scaturire da un'ipotesi
(teoria) sottostante, che deve fare previsioni suscettibili di essere
falsificate.
--
TRu-TS
Buon vento e cieli sereni
Archaeopteryx
2012-02-10 08:45:39 UTC
Permalink
[...] essere ellissoidi d'errore (ma sto cercando di
indovinare il perche' dei gap in corrispondenza dei
valori pari di x. Il vero motivo lo sai solo tu).
Credo che sia proprio il problema di cui forse vuol
valutare gli effetti. Michali-Schnorr (ho googlato, non è
che lo sapessi) pare essere il nome di un generatore di
numeri pseudo-casuali. I generatori pseudo-casuali hanno
sempre un periodo, per quanto su valori grandissimi. Posso
ipotizzare che stiamo vedendo l'effetto della lunghezza
finita della parola dell'elaboratore, ma non saprei.
All'inizio mi sembrava uno spettrogramma...

ciao!

Apx.
Cristiano
2012-02-10 11:48:08 UTC
Permalink
Post by Tommaso Russo, Trieste
Post by Cristiano
Ho, allora, interpolato tutti i punti (minimizzando il chi-quadro)
ottenendo la linea continua del grafico.
Ma... non stai ovviamente parlando di tutti i punti. Per ogni x, gli y
misurati si suddividono in due cluster. Hai eliminato i cluster
inferiori? Quelli che arrivano fino a 4096 per x=51, 16384 per x=59 e
cosi' via?
Le x sono variabili reali (non intere), per cui ad ogni x corrisponde la
sua y. La "particolarità" è che due x consecutive potrebbero avere una y
al minimo e una verso il massimo.
I punti campionati (e interpolati) sono attualmente oltre 150000 (anche
se purtroppo sono solo un infinitesimo di tutti quelli disponibili).
Post by Tommaso Russo, Trieste
Visto che la tua y ha una scala logaritmica mentre x e' lineare,
In realtà x è lg2(n), n è un numero intero (è il prodotto di 2 numeri
primi).
Post by Tommaso Russo, Trieste
andare
in cerca di una retta interpolante sembrerebbe aver fatto implicitamente
un'ipotesi per cui y=k1*exp(k2*x). + o - qualche errore o variabile casuale.
Come ha intuito Archaeopteryx (fortuna che c'è il copia&incolla), il
grafico rappresenta il periodo (finito) di un generatore di numeri
pseudo-casuali, la cui lunghezza è proporzionale a x (che rappresenta
l'escursione massima che la y può avere).
La funzione "naturale" che mi aspetto sarebbe:
y_max = 2^(k * x)
in cui k tiene conto dell'inefficienza del generatore di sfruttare al
100% tutti i bit disponibili.
Forse dovrei utilizzare quella funzione, ma l'errore sembra troppo grande.
Post by Tommaso Russo, Trieste
In questo caso, le distribuzioni dei punti centrati attono le
intersezioni della retta interpolante con x=51,53,55...71 potrebbero
essere ellissoidi d'errore (ma sto cercando di indovinare il perche' dei
gap in corrispondenza dei valori pari di x. Il vero motivo lo sai solo tu).
Purtroppo no. Quei gap si notano solo con la scala y logaritmica e
sembrano una vera stranezza.
Post by Tommaso Russo, Trieste
Insomma, dati insufficienti.
Piu' in generale: la scelta di una funzione interpolatrice non e' mai un
problema matematico. La sua forma *deve* scaturire da un'ipotesi
(teoria) sottostante, che deve fare previsioni suscettibili di essere
falsificate.
Avendo aggiunto informazioni su come calcolo la y e cos'è la x, potremmo
fare un'ipotesi sulla funzione da utilizzare?

Grazie ad entrambi
Cristiano
Tommaso Russo, Trieste
2012-02-10 22:26:55 UTC
Permalink
Riprendo e mi ricollego a quanto ho scritto nel thread "x^e (mod n)".
Post by Cristiano
Le x sono variabili reali (non intere), per cui ad ogni x corrisponde la
sua y. La "particolarità" è che due x consecutive potrebbero avere una y
al minimo e una verso il massimo.
I punti campionati (e interpolati) sono attualmente oltre 150000 (anche
se purtroppo sono solo un infinitesimo di tutti quelli disponibili).
...
Post by Cristiano
In realtà x è lg2(n), n è un numero intero (è il prodotto di 2 numeri
primi).
Come ha intuito Archaeopteryx (fortuna che c'è il copia&incolla), il
grafico rappresenta il periodo (finito) di un generatore di numeri
pseudo-casuali, la cui lunghezza è proporzionale a x (che rappresenta
l'escursione massima che la y può avere).
y_max = 2^(k * x)
in cui k tiene conto dell'inefficienza del generatore di sfruttare al
100% tutti i bit disponibili.
Forse dovrei utilizzare quella funzione, ma l'errore sembra troppo grande.
OK, avevo equivocato pensando che il tuo grafico fosse il risultato di
un gran numero di misure "fisiche" in dipendenza da un parametro x: in
realta', mi par di capire che e' il risultato di un algoritmo che ha in
input dei parametri correlati a x e un *campione* dei altri parametri
che possono assumere valori in un range anche molto esteso.

Questo fatto pero' riporta la tua domanda perfettamente in topic per
i.s.m., e solleva un problema molto interessante: e' possibile inferire
leggi matematiche da risultati *sperimentali*, come si fa per le "leggi
di natura" nelle Scienze Naturali?

La mia risposta e' si': l'esatto equivalente in Matematica delle leggi
naturali sono le *congetture*, e le congetture scaturiscono proprio per
spiegare alcune regolarita' che si riscontrano applicando un certo
algoritmo ad un gran numero di casi.

Il fatto che alcune congetture possano essere dimostrate vere (o false)
non modifica di molto il panorama: lo sviluppo delle potenze di calcolo,
e alcuni affinamenti della logica di cui diro' subito, ci rendono oggi
possibile senz'altro comgetturare la verita' di molti piu' enunciati di
quanti ne potremo mai dimostrare veri o falsi (indipendentemente dal
fatto che essi siano *in principio* dimostrabili veri o falsi; non sto
parlando qui del teorema di Goedel, ma solo del fatto che alcuni
problemi siano "intrattabili". ossia non solubili in tempi "ragionevoli"
- minori di alcune centinaia di miliardi d'anni, per esempio).

Questo, mi pare, sta portando sempre piu' spesso la trattazione della
Matematica nalla stessa direzione di quella delle Scienze Naturali: una
legge Matematica puo' venire *inferita* come congettura da regolarita'
riscontrate, e ritenuta non vera ma *affidabile* fino a prova contraria
- la dimostrazione della sua falsita', magari ottenuta con un controesempio.

Come esempio, cito alcune congetture usate per dimostrare alcuni
teoremi, il cui enunciato contiene fra le ipotesi "e SE la congettura di
XY e' vera, allora...".


Ma la situazione e' ancora piu' complicata dalla vera e propria
dimostrazione di alcuni teoremi che non dimostrano la verita' di un
certo enunciato, ma solo la *probabilita'* di riscontrarlo vero: i c.d.
"teoremi quasi sempre veri" di Erdos, che, guarda caso, riguardano per
lo piu' problemi molto poco trattabili, come quelli che si incontrano
nello studio dei grafi.

Un esempio: se costruiamo un grafo (non orientato) scegliendo N nodi e
collegandone con un arco M coppie scelte a caso, un teorema di Erdos
afferma che, *se*

M > ln(N) * (N-1)/2

e' *quasi sempre vero* che il grafo ottenuto e' completamente connesso
(tutti i nodi sono connessi fra loro, ossia e' possibile passare da
qualsiasi nodo a qualsiasi altro percorrendo una sequenza di archi).

Rigorosamente, Erdos definisce "quasi sempre vero" cosi': One says that
almost every graph has property Q (in a certain model) if the
probability that a graph in the model satisfies Q goes to 1 when N -> inf.


Ovviamente, se l'enunciato affermasse "e' *sempre* vero che", sarebbe
facile dimostrarlo falso: per costruire un controesempio basta prendere
un grafo *completo* (ogni nodo e' collegato direttamente, con un solo
arco, ad ogni altro) con un numero di nodi N non proprio piccolissimo,
aggiungere un nodo non conesso, e si ottiene un grafo che soddisfa
all'ipotesi ma non e' completamente connesso.


La cosa interessante e' che gli enunciati *quasi sempre veri* hanno un
grande *interesse pratico*: nelle'esempio dato, con N "ragionevolmente"
grande, mettendosi nelle condizioni dell'ipotesi, la probabilita' di
costruire (casualmente, non ad hoc come nel controesempio) un grafo non
completamente connesso e' veramente infima, per cui a gran parte degli
effetti pratici e' proprio trascurabile.

E' un po' come la tecnica dei nodi IPv6 di scegliersi un numero IP6
all'interno di una rete domestica: sceglierne uno a caso. La
probabilita' di collisione con un altro nodo che usa lo stesso indirizzo
e' miliardesimi di miliardesimi, per cui il costo *medio* della
procedura di collisione - rilevare la collisione e scegliere un *altro*
numero a caso - e' sicuramente inferiore a quello di rilevare tutti gli
indirizzi gia' in uso e sceglierne uno diverso.
Post by Cristiano
Avendo aggiunto informazioni su come calcolo la y e cos'è la x, potremmo
fare un'ipotesi sulla funzione da utilizzare?
Le informazioni mi sembrano ancora insufficienti. Nelle scienze
sperimentali, quando si "interroga la natura", per intuire la
possibilita' di una legge sottostante bisogna conoscere perfettamente le
modalita' dell'interrogazione.


A quello che ho capito, tu hai scelto una progressione di coppie p e q
crescenti, e per ogni n=p*q hai determinato x come log_2(n). A questo
punto mi sfugge, come tu abbia ottenuto, per ogni caso, l'ordinata dei
punti. E' la lunghezza di una sequenza aperiodica o di un ciclo? Per
determinarle, hai dovuto scegliere e ed r: con il *tuo* algoritmo o con
quello esposto nel libro di A. Menezes, P. van Oorschot, and S.
Vanstone? In particolare, sapere qual'e' il valore di r (o di k=n-r, nel
secondo caso) per ognuna delle tue log_2(n) mi sembra abbastanza
cruciale per qualsiasi ragionamento. Inoltre, per ogni valore di
log_2(n) hai dovuto scegliere una x_0 di partenza (o una y_0, fa lo
stesso). Li hai scelti a caso? Con un altro PRNG?


Per fare qualche congettura come quella che ho suggerito, vedrei piu'
utile un altro grafico, con in ascissa vari valori di r e in ordinata
parecchia lunghezze di ciclo o di "avvicinamento aperiodico" ottenute
per valori diversi della x_0 di partenza.
--
TRu-TS
Buon vento e cieli sereni
Cristiano
2012-02-11 12:57:25 UTC
Permalink
Post by Tommaso Russo, Trieste
Riprendo e mi ricollego a quanto ho scritto nel thread "x^e (mod n)".
Post by Cristiano
Le x sono variabili reali (non intere), per cui ad ogni x corrisponde la
sua y. La "particolarità" è che due x consecutive potrebbero avere una y
al minimo e una verso il massimo.
I punti campionati (e interpolati) sono attualmente oltre 150000 (anche
se purtroppo sono solo un infinitesimo di tutti quelli disponibili).
....
Post by Cristiano
In realtà x è lg2(n), n è un numero intero (è il prodotto di 2 numeri
primi).
Come ha intuito Archaeopteryx (fortuna che c'è il copia&incolla), il
grafico rappresenta il periodo (finito) di un generatore di numeri
pseudo-casuali, la cui lunghezza è proporzionale a x (che rappresenta
l'escursione massima che la y può avere).
y_max = 2^(k * x)
in cui k tiene conto dell'inefficienza del generatore di sfruttare al
100% tutti i bit disponibili.
Forse dovrei utilizzare quella funzione, ma l'errore sembra troppo grande.
OK, avevo equivocato pensando che il tuo grafico fosse il risultato di
un gran numero di misure "fisiche" in dipendenza da un parametro x: in
realta', mi par di capire che e' il risultato di un algoritmo che ha in
input dei parametri correlati a x e un *campione* dei altri parametri
che possono assumere valori in un range anche molto esteso.
Questo fatto pero' riporta la tua domanda perfettamente in topic per
i.s.m., e solleva un problema molto interessante: e' possibile inferire
leggi matematiche da risultati *sperimentali*, come si fa per le "leggi
di natura" nelle Scienze Naturali?
La mia risposta e' si': l'esatto equivalente in Matematica delle leggi
naturali sono le *congetture*, e le congetture scaturiscono proprio per
spiegare alcune regolarita' che si riscontrano applicando un certo
algoritmo ad un gran numero di casi.
[...]

Devo ammettere che non ho capito al 100% la parte che ho omesso;
comunque, grazie per la spiegazione. :-)
Post by Tommaso Russo, Trieste
Post by Cristiano
Avendo aggiunto informazioni su come calcolo la y e cos'è la x, potremmo
fare un'ipotesi sulla funzione da utilizzare?
Le informazioni mi sembrano ancora insufficienti. Nelle scienze
sperimentali, quando si "interroga la natura", per intuire la
possibilita' di una legge sottostante bisogna conoscere perfettamente le
modalita' dell'interrogazione.
A quello che ho capito, tu hai scelto una progressione di coppie p e q
crescenti, e per ogni n=p*q hai determinato x come log_2(n).
Più esattamente, ho scelto le coppie a caso all'interno di un certo
intervallo.
Post by Tommaso Russo, Trieste
A questo
punto mi sfugge, come tu abbia ottenuto, per ogni caso, l'ordinata dei
punti. E' la lunghezza di una sequenza aperiodica o di un ciclo?
Per ogni p, q ed x0 ho misurato la lunghezza della sequenza aperiodica
iniziale e quella della sequenza periodica.
L'ordinata che m'interessa attualmente è la lunghezza della sequenza
aperiodica.
Post by Tommaso Russo, Trieste
Per
determinarle, hai dovuto scegliere e ed r: con il *tuo* algoritmo o con
quello esposto nel libro di A. Menezes, P. van Oorschot, and S.
Vanstone? In particolare, sapere qual'e' il valore di r (o di k=n-r, nel
secondo caso) per ognuna delle tue log_2(n) mi sembra abbastanza
cruciale per qualsiasi ragionamento.
Come detto nell'altro thread, devo usare per forza due versioni, ma in
entrambe, r lo calcolo come descritto nel libro.
Post by Tommaso Russo, Trieste
Inoltre, per ogni valore di
log_2(n) hai dovuto scegliere una x_0 di partenza (o una y_0, fa lo
stesso). Li hai scelti a caso? Con un altro PRNG?
Sì, ho scelto x0 (da r bit) a caso.
Post by Tommaso Russo, Trieste
Per fare qualche congettura come quella che ho suggerito, vedrei piu'
utile un altro grafico, con in ascissa vari valori di r e in ordinata
parecchia lunghezze di ciclo o di "avvicinamento aperiodico" ottenute
per valori diversi della x_0 di partenza.
Ho utilizzato il file con i 150000 punti per ottenere un altro file che
lega r alla lunghezza della sequenza aperiodica (per ogni p, q ed x0
scelti a caso).
Questo è il risultato:
Loading Image...
ma non so se è ciò che intendevi.

Ciao e grazie
Cristiano
Tommaso Russo, Trieste
2012-02-14 20:57:53 UTC
Permalink
Post by Cristiano
Devo ammettere che non ho capito al 100% la parte che ho omesso;
comunque, grazie per la spiegazione. :-)
Mi sa che e' di tuo interesse. Guarda i link che ti ho segnalato
nell'altro thread parallelo (diciamo che le cose si sono evolute in modo
che la' si parla di teoria, qua di pratica :-)
Post by Cristiano
Più esattamente, ho scelto le coppie a caso all'interno di un certo
intervallo.
..
Post by Cristiano
Per ogni p, q ed x0 ho misurato la lunghezza della sequenza aperiodica
iniziale e quella della sequenza periodica. L'ordinata che m'interessa
attualmente è la lunghezza della sequenza aperiodica.
..
Post by Cristiano
Come detto nell'altro thread, devo usare per forza due versioni, ma in
entrambe, r lo calcolo come descritto nel libro.
..
Post by Cristiano
Sì, ho scelto x0 (da r bit) a caso.
OK.
Post by Cristiano
Post by Tommaso Russo, Trieste
Per fare qualche congettura come quella che ho suggerito, vedrei piu'
utile un altro grafico, con in ascissa vari valori di r e in ordinata
parecchia lunghezze di ciclo o di "avvicinamento aperiodico" ottenute
per valori diversi della x_0 di partenza.
Ho utilizzato il file con i 150000 punti per ottenere un altro file che
lega r alla lunghezza della sequenza aperiodica (per ogni p, q ed x0
scelti a caso).
http://cristianopi.altervista.org/MS_r_SAI.gif ma non so se è ciò che
intendevi.
Non esattamente.

Io avrei voluto vedere il grafico di un caso in cui, scelti gli altri
parametri iniziali, dopo aver fissato r in ascissa si fa variare per
parecchie volte l'x di partenza ottenendo vari punti in ordinata.

Di norma, in questi tentativi vale sempre la regola aurea del polyspi di
Papert: per capire l'importanza di un parametro in una legge naturale,
tieni FERMI tutti gli altri e fai variare solo lui, e molto lentamente.


Comunque, avendo fatto l'ipotesi (sensata) che tutti i risultati di
questo tipo siano assimilabili ai risultati ottenuti fissando i parametri
e procedendo alla costruzione di un grafo casuale, e' interessante lo
stesso.

Solo... puoi rifarla mettendo l'ordinata in scala logaritmica? Qui non ci
si capisce niente, perche' tutti i punti si addensano verso il basso.


grazie
--
TRu-TS
Buon vento e cieli sereni
Cristiano
2012-02-15 11:16:56 UTC
Permalink
Post by Tommaso Russo, Trieste
Io avrei voluto vedere il grafico di un caso in cui, scelti gli altri
parametri iniziali, dopo aver fissato r in ascissa si fa variare per
parecchie volte l'x di partenza ottenendo vari punti in ordinata.
E' pressoché uguale agli altri grafici.
Post by Tommaso Russo, Trieste
Solo... puoi rifarla mettendo l'ordinata in scala logaritmica? Qui non ci
si capisce niente, perche' tutti i punti si addensano verso il basso.
Ok, ci rimetto mano e lo posto.

Cristiano
Cristiano
2012-02-15 18:15:23 UTC
Permalink
Post by Tommaso Russo, Trieste
Solo... puoi rifarla mettendo l'ordinata in scala logaritmica?
La tua idea m'è piaciuta molto: :-)
Loading Image...

Sto indagando sulle due stranezze ben visibili (il vuoto da 30 a 33 bit
e l'assenza di valori piccoli per r > 29).
Da una prima analisi, non sembra un bug del programma... Vedrò di
capirci qualcosa.

Cristiano
Tommaso Russo, Trieste
2012-02-18 21:56:00 UTC
Permalink
Post by Cristiano
Post by Tommaso Russo, Trieste
Solo... puoi rifarla mettendo l'ordinata in scala logaritmica?
La tua idea m'è piaciuta molto: :-)
Bello!
Post by Cristiano
http://cristianopi.altervista.org/MS_r_SAI_log.gif
Sembrerebbe suggerire che, fissato r e costruito un grafo "casuale"
(cosa che penso faccia abbastanza bene il tuo algoritmo), i valori di x
in [0,2^r[ che "distano" da un "laghetto" (ciclo) piu' di 2*sqrt(2^r)
"salti" sono molto pochi, tanto che la probabilita' di trovarne uno
pescando a caso e' praticamente nulla.

Se questa *congettura* fosse vera, c'e' da aspettarsi che per r molto
grandi sarebbe "praticamente sempre" vera nel senso di Erdos.

Mi pare che questa sia una risposta "empirica" che risponde
parzialmente, ponendo un limite superiore molto probabile, alla tua
ricerca delle "stima della lunghezza della sequenza aperiodica iniziale".

Mi pare anche, pero', che a te interessi sopratutto trovare un limite
inferiore i che ti assicuri che per valori molto alti di r la lunghezza
della sequenza aperiodica sia *molto probabilmente* superiore a i.
Post by Cristiano
Sto indagando sulle due stranezze ben visibili (il vuoto da 30 a 33 bit
Questo potrebbe dipendere dal modo con cui ti hai ricavato r per ognuno
dei tuoi 150.000 esempi. Dato che tu scegli prima un p e un q, ne ricavi
n, e poi scegli r, potrebbe essere che sia questo procedimento di scelta
a eliminare sistematicamente i valori 30,31,32 e 33.
Post by Cristiano
e l'assenza di valori piccoli per r > 29).
Questo potrebbe essere un indizio della possibilita' di trovare
*proprio* cio' che ti interessa: un limite inferiore "molto probabile"
della lunghezza della sequenza aperiodica, crescente con r e quindi
ragionevomente alto per r molto alto.

Nel mio post del 14/02/2012 21:42, sull'altro thread, avevo ipotizzato
un meccanismo statistico che giustificherebbe questo risultato. Pero' il
grafico che hai pubblicato lascia ancora dubbi sul numero di punti
analizzati per ogni valore di r (contarli non e' possibile), e
l'estrapolazione di quanto dici ai valori di r inferiori a 30 lascia un
po' interdetti.

Non sara' per caso che il numero dei tuoi punti per valori di r
superiori a 33 sia molto inferiore al numero per valori di r inferiori a
30? Sarebbe molto utile estrarre dai tuoi file una tabella

| valore di r | numero di punti |
=================================
5
7
...
48

per cercare di capire il perche' dell'anomalia.

Un'altra cosa molto interessante sarebbe estrarre dai dati un istogramma
per ogni valore di r, che mostri il numero di punti in cui la sequenza
iniziale risulta compresa fra 2^0 e 2, 2 e 2^2, 2^2 e 2^3.... 2^25 2 2^26.

(anche qui, forse una tabella numerica sarebbe meglio interpretabile,
sopratutto per barre dell'istogramma molto basse).



P.S. su quanto hai scritto nell'ultimo post sull'altro thread sto ancora
riflettendo - questa settimana ho avuto una connessione internet
precaria. In compenso ho sciato parecchio :-)
--
TRu-TS
Buon vento e cieli sereni
Cristiano
2012-02-19 23:37:36 UTC
Permalink
Post by Tommaso Russo, Trieste
Mi pare anche, pero', che a te interessi sopratutto trovare un limite
inferiore i che ti assicuri che per valori molto alti di r la lunghezza
della sequenza aperiodica sia *molto probabilmente* superiore a i.
Sì, è proprio questo il fulcro del discorso; se la sequenza iniziale è
troppo corta, il generatore potrebbe risultare inadeguato.
Post by Tommaso Russo, Trieste
Post by Cristiano
Sto indagando sulle due stranezze ben visibili (il vuoto da 30 a 33 bit
Questo potrebbe dipendere dal modo con cui ti hai ricavato r per ognuno
dei tuoi 150.000 esempi. Dato che tu scegli prima un p e un q, ne ricavi
n, e poi scegli r, potrebbe essere che sia questo procedimento di scelta
a eliminare sistematicamente i valori 30,31,32 e 33.
Sì, dipende semplicemente dalla formula usata per calcolare r; tutto
regolare. :-)
Post by Tommaso Russo, Trieste
Post by Cristiano
e l'assenza di valori piccoli per r > 29).
Questo potrebbe essere un indizio della possibilita' di trovare
*proprio* cio' che ti interessa: un limite inferiore "molto probabile"
della lunghezza della sequenza aperiodica, crescente con r e quindi
ragionevomente alto per r molto alto.
Nel mio post del 14/02/2012 21:42, sull'altro thread, avevo ipotizzato
un meccanismo statistico che giustificherebbe questo risultato. Pero' il
grafico che hai pubblicato lascia ancora dubbi sul numero di punti
analizzati per ogni valore di r (contarli non e' possibile), e
l'estrapolazione di quanto dici ai valori di r inferiori a 30 lascia un
po' interdetti.
Non sara' per caso che il numero dei tuoi punti per valori di r
superiori a 33 sia molto inferiore al numero per valori di r inferiori a
30? Sarebbe molto utile estrarre dai tuoi file una tabella
| valore di r | numero di punti |
=================================
5
7
...
48
per cercare di capire il perche' dell'anomalia.
Un'altra cosa molto interessante sarebbe estrarre dai dati un istogramma
per ogni valore di r, che mostri il numero di punti in cui la sequenza
iniziale risulta compresa fra 2^0 e 2, 2 e 2^2, 2^2 e 2^3.... 2^25 2 2^26.
(anche qui, forse una tabella numerica sarebbe meglio interpretabile,
sopratutto per barre dell'istogramma molto basse).
Credo che un'unica tabella possa servire per entrambe le cose:
http://cristianopi.altervista.org/MS_dist_r_SAI.txt
la prima colonna è r, le colonne seguenti rappresentano il numero di
punti che cadono all'interno di floor(lg2(SAI)) (SAI= lunghezza della
sequenza aperiodica iniziale).
Post by Tommaso Russo, Trieste
P.S. su quanto hai scritto nell'ultimo post sull'altro thread sto ancora
riflettendo - questa settimana ho avuto una connessione internet
precaria. In compenso ho sciato parecchio :-)
Beato te, che con la neve ti ci diverti! Io ho passato le due ultime
settimane a spalare la neve intorno casa e sopra al tetto! :-(

Ciao
Cristiano
Tommaso Russo, Trieste
2012-02-24 00:07:29 UTC
Permalink
Post by Cristiano
... Sarebbe molto utile estrarre dai tuoi file una tabella
| valore di r | numero di punti |
=================================
...
Post by Cristiano
Un'altra cosa molto interessante sarebbe estrarre dai dati un istogramma
per ogni valore di r, che mostri il numero di punti in cui la sequenza
iniziale risulta compresa fra 2^0 e 2, 2 e 2^2, 2^2 e 2^3.... 2^25 e
2^26.
http://cristianopi.altervista.org/MS_dist_r_SAI.txt
la prima colonna è r, le colonne seguenti rappresentano il numero di
punti che cadono all'interno di floor(lg2(SAI)) (SAI= lunghezza della
sequenza aperiodica iniziale).
Scusa il ritardo. Per qualche giorno non ho fatto altro che ispezionare
un po' sconsolato il plot che ho fatto subito con i tuoi dati grezzi,
senza neanche normalizzarli:

Loading Image...

come si vede, per ogni r la distribuzione delle lunghezze L delle SAI
nei tuoi casi con dati iniziali casuali cade *molto* rapidamente (anzi,
proprio precipita) verso i valori alti, confermando l'intuizione che la
probabilita' di trovare L superiore a 2*sqrt(2^r) sia molto bassa. Nel
plot lo si vede chiaramente, dalle linee di livello riportate in basso
per n=1 (verde) 2 (viola) fino a 20 (giallo), che verso l'alto della
figura praticamente coincidono formando nel piano log-log una retta con
pendenza 1/2.

Verso valori bassi di L invece, quelli che interessano a te, la discesa
delle distribuzioni per ogni r e' molto piu' dolce ("distribuzione a
coda lunga") e l'unica conclusione che si potrebbe trarne, molto
prudenziale, e' che per valori di L che cadono al di sotto della retta

log_2 L = - 15 + 1/2 r
(ossia la retta che va da r=30, L=1 a r=50, L=2^10)

la probabilita' p0 di trovarli e' ragionevolmente inferiore a 1/1000 o
anche 1/10000. Che non mi pareva esattamente il risultato che cercavi... :-)


Poi mi e' finalmente tornato alla memoria un vecchio trucco - che ho
anche insegnato :-( - ed ho posto z in scala logaritmica. Ecco il risultato:

Loading Image...

qui si vede chiaramente che la coda dalla parte bassa e' lunga si', ma
non lunghissima: e' una vera "power-law tail" della forma p(L)=kL^gamma.

Per stimare gamma, r per r, ho ruotato gli istogrammi in modo da
guardarli di lato:

Loading Image...

e ho visto che in sostanza gamma e' praticamente lo stesso per ogni r:
tutte le curve verso destra hanno un ampio tratto rettilineo con la
stessa pendenza. Quant'e' la pendenza? Se interpoli (a occhio) le curve
con un fascio di rette parallele vedi subito che, aumentando L da 2^10 a
2^20 (ossia moltiplicandolo per 1024), il numero di casi aumenta da 1 a
circa 1000...

====================
==> | gamma = 1 |
====================


A questo punto diventa facile: visto che per la stima precedente per
r=30 hai probabilita' inferiore a 1/1000 di trovare una SAI piu' breve
di 2^0 = 1, se vuoi ottenere una probabilita' 2^x volte inferiore di
trovare una SAI piu' breve di 2^y, basta che sommi alla r di partenza
2x+2y.

Per esempio, se ti "accontenti" di una probabilita' di un miliardesimo
di miliardesimo, 10^-18, ossia 10^-15 volte inferiore a 1/1000, di
ottenere una SAI di lunghezza inferiore a 10^18, un miliardo di miliardi,

tenendo conto che 10^-15 = ca. 2^-50 e 10^18 = ca. 2^-60, il risultato
sarebbe assicurato scegliendo

r = 30 + 2*50 + 2*60 = 250.


Dato che in un altro tuo post dicevi, se non erro, che nell'uso
effettivo r viene scelto dell'ordine *delle migliaia*, non dovresti
avere difficolta' ad assicurarti che incocciare in una stringa piu'
breve del numero di barioni nell'Universo (ca 2^300) abbia meno
probabilita' di quella che l'entropia di un sistema macroscopico
diminuisca sensibilmente spontaneamente.

- o -

Prima che tu ti metta a saltare dalla gioia, pero', devo richiamare il
problema epistemologico di base.

Quella che ho fatto sopra non e' un'analisi matematica su un algoritmo,
quanto piuttosto un'analisi su *risultati sperimentali*
dell'applicazione di un algoritmo a un campione casuale facendo variare
un parametro.

Quant'e' affidabile?


La mia opinione e' che sia tanto affidabile quanto un'analisi corretta
di *risultati sperimentali* nell'ambito delle scienza naturali.

Nelle scienze naturali si fa l'ipotesi che due fenomeni quantitativi
siano legati fra loro da una legge matematica *semplice* che derivi da
un meccanismo sottostante ignoto, ma operante. Nella "matematica
sperimentale" fatta sin qui l'ipotesi sostanzialmente e' la stessa:
l'algoritmo che appliche crea un grafo casuale ma con proprieta' che
derivano da "regolarita' nascoste" insite nell'algoritmo stesso.

L'analisi grafica dei dati sperimentali suggerisce "leggi semplici" per
le grandezze di tuo interesse.


Se il risultato che cerchi fosse ottenibile con un' *interpolazione*, ti
direi di dormire tranquillo.

Il punto e' che ho fatto invece un' *estrapolazione*, e non di poco
conto: da risultati ottenuti per valori di r fra 5 e 48, ho estrapolato
fino a r=250, e addirittura fino a r = N*1000.


Le assunzioni cruciali sono essenzialmente 2:

gamma = 1

log_2 L = - 15 + 1/2 r

"gamma = 1" e' "troppo bella per NON essere vera", troppo semplice e
suscettibile di interpretazioni statistiche ragionevoli: non le espongo
perche' le ho solo intuite, ma *congetturo* che un Erdos potrebbe
dimostrare essere una proprieta' che vale con p->1 per r->inf.

Anche per "log_2 L = - 15 + 1/2 r", cioe' la dipendenza lineare (sul
piano log-log) da r di log(L), dove L e' quel valore al di sotto del
quale la probabilita' di ottenere una SAI e' minore di una certa soglia,
sospetto che potrebbe essere dimostrabile con considerazioni
statistiche: che pero' non intuisco, per cui non posso escludere una
dipendenza che sia lineare per valori "piccoli" di r, ma che contenga
anche termini quadratici o cubici che si fanno sentire solo a valori
piu' alti. Nelle Scienze Naturali, ne ho viste troppe di curve che
cominciano dritte come una freccia e poi s'incurvano: si pensi per
esempio ad una logistica S(t) nel piano t,log(S(T)): inizia come una
retta (creescita all'inizio esponenziale) e poi incontra i limiti dello
sviluppo che non consentono ad S di superare la saturazione.

Per cui ti invito a considerare quanto detto sopra come congetture su
cui sarebbe bello indagare (e la strada maestra e' la teoria dei grafi),
ma non come "leggi naturali" corroborate dagli esperimenti su cui basare
un prodotto di crittografia.

Magari, come indagine ulteriore, sarebbe bello ottenere qualche
distribuzione per valori di r piu' alti, 250 o anche 1000 (o 4000). Temo
pero' che i requisiti in termini di memoria e di tempo di CPU siano
veramente fuori portata. Anzi, se i risultati congetturati fossero veri,
sarebbero *sicuramente* fuori portata.
Post by Cristiano
P.S. su quanto hai scritto nell'ultimo post sull'altro thread sto ancora
riflettendo - questa settimana ho avuto una connessione internet
precaria. In compenso ho sciato parecchio :-)
Beato te, che con la neve ti ci diverti! Io ho passato le due ultime
settimane a spalare la neve intorno casa e sopra al tetto! :-(
Mi spiace di aver toccato un punto dolente... qui il burian ha tenuto
banco per 2 settimane non consentendo all'aria umida di stagnare sopra
noi, per cui *tutta* la neve e' arrivata dall'altra parte dell'Adriatico :-(

In compenso, in quelle due settimane abbiamo avuto vento costantemente
sugli 80 km/h, con continui rinforzi a 120 e punte di 150-160 (una
massima a 168), con questi risultati:

Loading Image...

(visto di fronte):
Loading Image...
(visto dal retro)
Loading Image...

questo, poi, per fortuna e' accaduto di notte:
Loading Image...

(da vicino):
Loading Image...
(da lontano si capisce meglio):
Loading Image...


Dopo 15 giorni io non ne potevo piu' *DEL RUMORE*. Quando sono arrivato
a Tarvisio, calma di vento e rumori ovattati dal manto nevoso, mi sono
sentito rigenerato :-)
--
TRu-TS
Buon vento e cieli sereni
Cristiano
2012-02-26 16:14:24 UTC
Permalink
Post by Tommaso Russo, Trieste
Scusa il ritardo.
Non devi certo scusarti; mi stai facendo un grosso favore!
Post by Tommaso Russo, Trieste
Per qualche giorno non ho fatto altro che ispezionare
un po' sconsolato il plot che ho fatto subito con i tuoi dati grezzi,
http://trusso.freeshell.org/Cristiano/plot1.png
come si vede, per ogni r la distribuzione delle lunghezze L delle SAI
nei tuoi casi con dati iniziali casuali cade *molto* rapidamente (anzi,
proprio precipita) verso i valori alti, confermando l'intuizione che la
probabilita' di trovare L superiore a 2*sqrt(2^r) sia molto bassa. Nel
plot lo si vede chiaramente, dalle linee di livello riportate in basso
per n=1 (verde) 2 (viola) fino a 20 (giallo), che verso l'alto della
figura praticamente coincidono formando nel piano log-log una retta con
pendenza 1/2.
Interpolando tutti i valori utili (circa 144000, escludendo le r più
piccole di 19, non molto regolari) confermo 1/2 per la pendenza (il
programma calcola 0.497873).
Post by Tommaso Russo, Trieste
Verso valori bassi di L invece, quelli che interessano a te, la discesa
delle distribuzioni per ogni r e' molto piu' dolce ("distribuzione a
coda lunga") e l'unica conclusione che si potrebbe trarne, molto
prudenziale, e' che per valori di L che cadono al di sotto della retta
log_2 L = - 15 + 1/2 r
(ossia la retta che va da r=30, L=1 a r=50, L=2^10)
la probabilita' p0 di trovarli e' ragionevolmente inferiore a 1/1000 o
anche 1/10000. Che non mi pareva esattamente il risultato che cercavi... :-)
In che senso? Vuoi dire che mi aspettavo valori più piccoli?

Nel grafico si vedono sono solo 3 punti (su 143698) al di sotto di
quella retta: 2 per r= 48 e 1 per r= 42.
Post by Tommaso Russo, Trieste
Poi mi e' finalmente tornato alla memoria un vecchio trucco - che ho
http://trusso.freeshell.org/Cristiano/plot2.png
qui si vede chiaramente che la coda dalla parte bassa e' lunga si', ma
non lunghissima: e' una vera "power-law tail" della forma p(L)=kL^gamma.
Per stimare gamma, r per r, ho ruotato gli istogrammi in modo da
http://trusso.freeshell.org/Cristiano/plot3.png
tutte le curve verso destra hanno un ampio tratto rettilineo con la
stessa pendenza. Quant'e' la pendenza? Se interpoli (a occhio) le curve
con un fascio di rette parallele vedi subito che, aumentando L da 2^10 a
2^20 (ossia moltiplicandolo per 1024), il numero di casi aumenta da 1 a
circa 1000...
====================
==> | gamma = 1 |
====================
A questo punto diventa facile: visto che per la stima precedente per
r=30 hai probabilita' inferiore a 1/1000 di trovare una SAI piu' breve
di 2^0 = 1, se vuoi ottenere una probabilita' 2^x volte inferiore di
trovare una SAI piu' breve di 2^y, basta che sommi alla r di partenza
2x+2y.
Per esempio, se ti "accontenti" di una probabilita' di un miliardesimo
di miliardesimo, 10^-18, ossia 10^-15 volte inferiore a 1/1000, di
ottenere una SAI di lunghezza inferiore a 10^18, un miliardo di miliardi,
tenendo conto che 10^-15 = ca. 2^-50 e 10^18 = ca. 2^-60, il risultato
sarebbe assicurato scegliendo
r = 30 + 2*50 + 2*60 = 250.
Bene! Risultato molto confortante. :-)
Post by Tommaso Russo, Trieste
Dato che in un altro tuo post dicevi, se non erro, che nell'uso
effettivo r viene scelto dell'ordine *delle migliaia*, non dovresti
avere difficolta' ad assicurarti che incocciare in una stringa piu'
breve del numero di barioni nell'Universo (ca 2^300) abbia meno
probabilita' di quella che l'entropia di un sistema macroscopico
diminuisca sensibilmente spontaneamente.
Nell'uso pratico, p * q è un numero da 1000, 2000 bit, ma r potrebbe
essere anche molto "piccolo" (inferiore a 200).
Però, grazie al tuo aiuto, risulta ovvio che l'esponente 'e' dovrà
essere più piccolo possibile (3 o 5), in modo che r sia sempre molto grande.
Post by Tommaso Russo, Trieste
gamma = 1
log_2 L = - 15 + 1/2 r
"gamma = 1" e' "troppo bella per NON essere vera", troppo semplice e
suscettibile di interpretazioni statistiche ragionevoli: non le espongo
perche' le ho solo intuite, ma *congetturo* che un Erdos potrebbe
dimostrare essere una proprieta' che vale con p->1 per r->inf.
Del resto, in un altro messaggio dicevo che la funzione "naturale" che
descrive il problema dev'essere qualcosa del tipo:
y_max = 2^(k * x).
A questo punto, la x è r e il risultato dell'interpolazione è la
magnifica e semplicissima formula:
y_max= k * 2 ^ (r/2 - 0.5256).
Risultati come 2 ^ (qualcosa) e r/2 sono troppo belli, in questo caso,
per non essere veri. :-)
Post by Tommaso Russo, Trieste
Magari, come indagine ulteriore, sarebbe bello ottenere qualche
distribuzione per valori di r piu' alti, 250 o anche 1000 (o 4000). Temo
pero' che i requisiti in termini di memoria e di tempo di CPU siano
veramente fuori portata. Anzi, se i risultati congetturati fossero veri,
sarebbero *sicuramente* fuori portata.
Avere risultati per r intorno a 60 è già un problema, figuriamoci per r=
250! :-)

Attualmente è in esecuzione un programma che calcola e memorizza solo i
valori minimi del periodo e delle SAI, infischiandosi dei valori al di
sopra di quelli calcolabili con la memoria disponibile.
Ho anche scritto una versione del programma che utilizza il disco fisso
invece della RAM, ma è 27 volte più lento del già lento programma attuale.

Bisognerebbe utilizzare uno di quei progetti di calcolo distribuito tra
tanti PC, ma visto l'interesse per l'argomento... :-(
Post by Tommaso Russo, Trieste
Mi spiace di aver toccato un punto dolente... qui il burian ha tenuto
banco per 2 settimane non consentendo all'aria umida di stagnare sopra
noi, per cui *tutta* la neve e' arrivata dall'altra parte dell'Adriatico :-(
Me ne sono accorto! :-)
A giudicare dalle foto, direi che anche dalle tue parti ne avete avuti
di problemi. :-(

Ciao e grazie mille per il grande aiuto
Cristiano

Continua a leggere su narkive:
Risultati di ricerca per 'Estrapolazione con grafico' (newsgroup and mailinglist)
108
risposte
Mi consigliate dei libri "di destra" per cortesia?
iniziato 2009-11-30 13:29:07 UTC
it.cultura.religioni
9
risposte
estrapolazione dati da un immagine
iniziato 2003-07-27 23:38:13 UTC
it.comp.www.php
108
risposte
Mi consigliate dei libri "di destra" per cortesia?
iniziato 2009-11-30 13:29:07 UTC
it.arti.cinema
42
risposte
[AFFARI NOSTRI] IDLM è in calo :-(
iniziato 2009-06-11 19:30:01 UTC
it.discussioni.leggende.metropolitane
8
risposte
breviario grafico, antiballe
iniziato 2010-03-17 16:26:55 UTC
it.discussioni.ufo
Risultati di ricerca per 'Estrapolazione con grafico' (Domande e Risposte)
7
risposte
come si verifica un ritardo di fase in condensatori / induttori con immagini visive
iniziato 2012-10-05 17:55:47 UTC
elettronica
1
rispondi
Ho tre biglietti in lista d'attesa con stato: WL3, WL4, WL5. Verranno confermati tutti e 3 insieme?
iniziato 2013-02-18 17:02:46 UTC
viaggio
4
risposte
Che cos'è il grafico del QI in Idiocracy?
iniziato 2014-01-16 21:00:14 UTC
sci-fi
2
risposte
In che modo la testata termonucleare produce scala con le dimensioni?
iniziato 2015-02-18 08:05:22 UTC
ingegneria
3
risposte
2003 F150 5.4L V8 con regolazione del carburante a lungo termine High Bank 2
iniziato 2015-04-21 23:11:05 UTC
automobili
Discussioni interessanti ma non correlate
3
risposte
C'è qualche verità nell'interpretare la definizione di secondo come corrispondente alle oscillazioni?
iniziato 2016-05-16 22:02:45 UTC
4
risposte
Come immaginare la propagazione del segnale WiFi?
iniziato 2016-05-18 11:27:43 UTC
7
risposte
Come ha fatto la mia cera di candela a strisciare sui lati del barattolo?
iniziato 2016-05-18 20:43:20 UTC
1
rispondi
Se avessimo un computer "perfettamente efficiente" e tutta l'energia disponibile nella Via Lattea, quale numero potrebbe contare?
iniziato 2016-05-22 14:05:27 UTC
7
risposte
Lancio di satelliti Supergun
iniziato 2016-05-25 12:50:31 UTC
Loading...