Discussione sul pi greco

[arulbero]

Python è un linguaggio molto versatile e può essere considerato sia interpretato che compilato allo stesso tempo, visto che in esecuzione genera automaticamente il bytecode come qualsiasi altro compilato.

Riguardo il parallelo basta aggiungere una manciata di codice e sei apposto.


FaSan


EDIT : ho fatto un piccolo test su una macchina virtuale, ed ho ottenuto il risultato PI con 1miliardo di punti in 8 minuti, sfruttando una singola cpu (virtualizzata). Dopo cena ho un pò più di tempo e ci applico il multithread, vediamo come và

Con la mia cpu Core2 Duo P8700 e programma compilato con free pascal riesco a fare 1 miliardo di punti in poco più di 1 minuto, pensando di portare il programma su altri pc più potenti e con più core la strada migliore mi sembra proprio il multithread.

Grazie a tutti per l'aiuto!

EDIT: se qualcuno vuole provare il mio programmino è questo https://dl.dropboxusercontent.com/u/134071847/Stimapigreco2.exe, è per Windows, basta cliccarci su, inserire il numero di punti (provate 10000000000) dovrebbe impiegarci meno di 10 minuti. Non ci sono virus!

[picchio]

E fare una griglia di punti al posto del casuale, ti risparmieresti la generazione di numeri casuali che per milioni di punti temo crei alla fine sempre gli stessi. Svolgeresti tantissimi calcoli ripetuti e forse inutili.

Vuoi mettere la sensazione di lanciare tante freccette contro un bersaglio, contare quante entrano e quante no nel cerchio, e da questa pseudocasualitá simulata ricavare la stima di pigreco?  

A mio avviso il metodo ha molto senso se lo fai con figure irregolari e per una stima di massima, se vuoi affinare la stima a qualche decimale credo non sia il massimo accanirsi ma senza queste prese di posizione forse saremmo ancora al tempo della pietra :-)

[arulbero]

E fare una griglia di punti al posto del casuale, ti risparmieresti la generazione di numeri casuali che per milioni di punti temo crei alla fine sempre gli stessi. Svolgeresti tantissimi calcoli ripetuti e forse inutili.

A mio avviso il metodo ha molto senso se lo fai con figure irregolari e per una stima di massima, se vuoi affinare la stima a qualche decimale credo non sia il massimo accanirsi ma senza queste prese di posizione forse saremmo ancora al tempo della pietra :-)

Sono d'accordo, non é sicuramente il metodo più efficace né quello che converge più rapidamente, ma ormai mi ha preso e voglio vedere se almeno é possibile arrivare a un errore di non più di una parte su un miliardo.
Tieni conto che se si potessero generare effettivamente dei numeri reali e quindi dei veri punti 0-dimensionali ( e non dei numeri su una macchina con una precisione finita che quindi corrispondono a dei rettangolini, un po' come l'impronta di una freccia fisica su un bersaglio) non potrebbe succedere certo di generare milioni di punti uguali 

La parte che mi intriga di più é proprio quella della generazione pseudocasuale dei numeri, che é tutt'altro che scontata quando si tenta di parallelizzare la procedura (ad esempio, quattro sequenze di numeri casuali generati da 4 thread paralleli mantengono le stesse proprietá statistiche di un'unica sequenza di numeri casuali? Non é scontato, bisogna vedere come é implementata la funzione random che si utilizza).

D'altronde in un forum dedicato al bitcoin un po' di curiosità per le sequenze stocastiche e le loro proprietà ci sta bene.

[picchio]

Ho fatto un programma in c++ che, chiesto l'errore assoluto desiderato "spara" fino a che non raggiunge quella precisione.
Io l'ho compilato su GNU/Linux e funziona, non ci mette molto ad ottenere valori di qualche decimale...
Non so se gli errori di calcolo alla fine hanno la meglio ... se qualcuno puo' intervenire ben venga!

Code:

// File: pigreco_while.cpp
#include <iostream>
#include <stdio.h>
#include <stdlib.h> /* per drand48() e sran48() */
using namespace std;
double PI=3.14159265358979323846264338328;
int main() {
  long i, c, data;
  double x, y, pi, errore, precisione;
  cout<<"Precisione (valore assoluto)? ";
  cin>>precisione;
  data=time(NULL);
  srand48(data);
  c=0;
  i=0;
  do  {
    x=drand48();
    y=drand48();
    if (x*x+y*y<1) {
      c++;
    }
    i++;
    //cout<<"("<<x<<"; "<<y<<") ";                                                                                           
    pi = ((double) c/(double) i)* 4.;
    errore = pi-PI;
    if (errore<0) errore=-errore;
    //cout<<errore<<" pi="<<pi<<endl;                                                                                        
    if ((i%10000)==0) cout<<"\n Spari effettuati: "<<i<<endl;
  } while (errore>precisione);
  printf("\nValore stimato di pi greco = %.30f\n", pi);
  printf("   Valore NOTO di pi greco = %.30f\n", PI);
  cout<<"tiri = "<<i<<"; centri="<<c<<"; seed = "<<data<< "; errore="<< errore<<endl;
  return 0;
}

Per compilarlo uso:

Code:

$ g++ pigreco_while.cpp -o pigreco_while -Wall
$ echo "0.00000001"|./pigreco_while

Devo dire che a lanciarlo si ha come la sensazione di "minare" in quanto a volte si ferma dopo pochi cicli, a volte dopo migliaia.
Feedbak benvenuti e buon pi greco day.
EDIT:
Qualche esempio di esecuzione:

Code:

$ echo "0.00000001"|./pigreco_while
Valore stimato di pi greco = 3.141592660980685458582684077555
   Valore NOTO di pi greco = 3.141592653589793115997963468544
tiri = 34119; centri=26797; seed = 1426291102; errore=7.39089e-09

$ echo "0.00000001"|./pigreco_while
Valore stimato di pi greco = 3.141592653082085906390830132295
   Valore NOTO di pi greco = 3.141592653589793115997963468544
tiri = 430439; centri=338066; seed = 1426291107; errore=5.07707e-10

[arulbero]

Devo dire che a lanciarlo si ha come la sensazione di "minare" ....
Qualche esempio di esecuzione:

Code:

$ echo "0.00000001"|./pigreco_while
Valore stimato di pi greco = 3.141592660980685458582684077555
   Valore NOTO di pi greco = 3.141592653589793115997963468544
tiri = 34119; centri=26797; seed = 1426291102; errore=7.39089e-09

$ echo "0.00000001"|./pigreco_while
Valore stimato di pi greco = 3.141592653082085906390830132295
   Valore NOTO di pi greco = 3.141592653589793115997963468544
tiri = 430439; centri=338066; seed = 1426291107; errore=5.07707e-10

Ciao picchio e buon pi greco day a tutti!
Stamattina  3 / 14 / 15 alle 9:26:53 secondi sono state "festeggiate" le  prime 9 cifre decimali del pi greco! Succede 1 volta ogni 100 anni  

Per quanta riguarda il tuo programmino ho trovato interessante l'idea che hai avuto; mi spiego meglio, tu vuoi vedere dopo quanto tempo si arriva entro un certo limite di errore, effettivamente da come l'ha impostato tu  questo ricorda molto da vicino il concetto di difficoltà dei bitcoin.
Ovviamente se dovessimo usare veramente il programma per vedere quanto il metodo Monte Carlo funziona nella stima di pi greco (la velocitá di convergenza dell'algoritmo al risultato) non avrebbe molto senso fare così, poiché affermare di riuscire a fare un errore dell'ordine di e-09 / e-10 solo con poche decine di migliaia di punti sarebbe un po' come ricavare dal fatto che un certo blocco é minato in 30 secondi una stima per eccesso della propria velocità di risoluzione del problema.

La grossa differenza tra il mining e la stima di pi greco é che con il pi greco tu sai che piú calcoli fai, migliore diventa l'approssimazione (almeno fino a un certo punto), mentre con il mining si é costretti a parlare di probabilitá di trovare una soluzione. Io per arrivare a una stima "stabile" delle prime 6 cifre di pi greco ho dovuto generare centinaia di miliardi di punti, se per caso dopo 10000 punti ottengo le prime 5 cifre corrette e al 10001 punto la stima risulta corretta solo fino alla 4^ cifra, l'algoritmo allora non ha localizzato la soluzione, l'ha semplicemente solo "indovinata".

Sarebbe possibile, almeno a livello teorico,  fare il mining sostituendo il problema di ottenere la famosa stringa con un tot di 0 iniziali con quello di approssimare pi greco fino alla x-esima cifra decimale ?  
Con il pi greco bisognerebbe trovare l'accoppiata seed  / numero di punti generati per dimostrare di avere trovato la soluzione richiesta, ma forse tutti dovrebbero usare una stessa funzione random?
Sarebbe piú facile "barare" e fornire una soluzione al problema che non richieda molti calcoli?

EDIT: mi é venuto in mente che come minimo bisogna trovare però almeno un modo per collegare il calcolo del pi greco alle transazioni contenute nel blocco da validare ...

[picchio]

Ciao
solo alcune considerazioni/domande:
- ha senso parlare di convergenza del algoritmo parlando di numeri casuali? Al massimo si parla di probabilità di commettere un errore minore di x dopo n lanci. Un pochettino come il chi quadro ...
- quando ho lanciato il programmino che ho fatto ho pensato anche io ad una moneta che ha come sistema di minig qualcosa collegato al numero pi greco, secondo me qualcuno ci ha gia' pensato ... se riesco provo a cercare ...  non sarebbe male ...
- riflettevo anche su pi greco e blockchain e potrebbe essere interessante studiare un sistema che usa come generatore casuale gli hash dei blocchi e dia come risultato la stima di pi greco della chain. Si potrebbe applicare una griglia al quadrato 1*1 di k*k linee che danno luogo a k^2 punti nel quadrato, poi si conta dal primo a sinistra in basso verso destra salendo una volta arrivato alla x>=1 (non so se mi son spiegato ...), in sostanza si ottiene un intero per ciascuo degli k^2 punti. SI prende il primo hash della chain, si fa modulo k^2 e si determina il primo estratto. Questo e' il primo lancio. Poi si procede come al solito. Ogni blocco abbiamo un aggiornamento del valore.
La stima dipenderà ovviamente anche dal valore di k. Se ci sono idee su come sceglierlo, magari usando qualcosa legato alla difficoltà...

[arulbero]

- ha senso parlare di convergenza del algoritmo parlando di numeri casuali? Al massimo si parla di probabilità di commettere un errore minore di x dopo n lanci. Un pochettino come il chi quadro ...

L'algoritmo dal mio punto di vista converge quasi come fosse un limite, da un certo punto in poi l'errore è "sempre" (con "sempre" intendo con probabilità 1) minore di un certo valore e così via, potremmo dire che la successione di stime di pi greco che si aggiorna dopo ogni lancio è una successione di Cauchy (fino al punto in cui subentrano gli errori dovuti alla precisione finita della macchina) che converge a pi greco.

- riflettevo anche su pi greco e blockchain e potrebbe essere interessante studiare un sistema che usa come generatore casuale gli hash dei blocchi e dia come risultato la stima di pi greco della chain. Si potrebbe applicare una griglia al quadrato 1*1 di k*k linee che danno luogo a k^2 punti nel quadrato, poi si conta dal primo a sinistra in basso verso destra salendo una volta arrivato alla x>=1 (non so se mi son spiegato ...), in sostanza si ottiene un intero per ciascuo degli k^2 punti. SI prende il primo hash della chain, si fa modulo k^2 e si determina il primo estratto. Questo e' il primo lancio. Poi si procede come al solito. Ogni blocco abbiamo un aggiornamento del valore.
La stima dipenderà ovviamente anche dal valore di k. Se ci sono idee su come sceglierlo, magari usando qualcosa legato alla difficoltà...

Se ho capito, riassumendo:
1) dividi il quadrato 1x1 in una griglia regolare di k^2 punti
2) si prende l'hash di ciascun blocco (modulo k^2) e si ottiene così quale è il punto estratto (che corrisponde a uno dei vertici di questa griglia e solo a uno di questi, ad esempio il numero 7512 che corrisponde a una certa posizione nel quadrato)
3) alla fine di tutti i blocchi si calcola la stima di pi greco (che si otterrà di fatto dividendo il numero di centri ottenuti per il numero di blocchi presenti nella blockchain fino a quel momento)
4) ora abbiamo ottenuto una stima di pi greco, e il fatto notevole è che ogni punto è stato generato usando un seed diverso (l'hash del blocco corrispondente)

Ogni nuovo blocco "genera" un nuovo punto nel quadrato (con la limitazione che può essere sempre solo uno di quei k^2 punti). Bella idea!

quando ho lanciato il programmino che ho fatto ho pensato anche io ad una moneta che ha come sistema di minig qualcosa collegato al numero pi greco, secondo me qualcuno ci ha gia' pensato ... se riesco provo a cercare ...  non sarebbe male ...

Questa è la parte che mi intriga di più, la difficoltà sta nell'ideare un'operazione collegata ai blocchi difficile da effettuare in un senso ma facile da verificare nell'altro 

[arulbero]

- quando ho lanciato il programmino che ho fatto ho pensato anche io ad una moneta che ha come sistema di minig qualcosa collegato al numero pi greco, secondo me qualcuno ci ha gia' pensato ... se riesco provo a cercare ...  non sarebbe male ...

Un'idea potrebbe essere :
Difficoltà = numero di cifre del pigreco da "indovinare" (tipo 15 o 20)
Parametro n = numero massimo di punti che si possono generare (tipo 10000) per ottenere una stima entro tale margine di errore

A questo punto si genera l'hash di un blocco, che è il seed, e utilizzando una funzione random (uguale per tutti) si generano fino a 10000 punti. Se non si trova un'approssimazione di pi greco alla 15^ cifra, si modifica il blocco (come succede adesso), si ottiene un nuovo hash, a questo punto si prova la nuova serie (al massimo 10000 lanci) e così via.

In questo modo sarebbe molto dispendioso trovare la soluzione, ma molto facile verificarla.


EDIT: mi sono accorto che ormai l'argomento del thread è cambiato, ho chiesto a HostFat di spostare questo thread per non perdere i contributi di chi vi ha partecipato da una parte, e non utilizzare uno spazio inappropriato in quanto dedicato ai "Servizi" dall'altra

[picchio]

- ha senso parlare di convergenza del algoritmo parlando di numeri casuali? Al massimo si parla di probabilità di commettere un errore minore di x dopo n lanci. Un pochettino come il chi quadro ...

L'algoritmo dal mio punto di vista converge quasi come fosse un limite, da un certo punto in poi l'errore è "sempre" (con "sempre" intendo con probabilità 1) minore di un certo valore e così via, potremmo dire che la successione di stime di pi greco che si aggiorna dopo ogni lancio è una successione di Cauchy (fino al punto in cui subentrano gli errori dovuti alla precisione finita della macchina) che converge a pi greco.

Hai dei riferimenti teorici in merito? Io non riesco a concepire se non una probabilità che sia "minore di" e non vedo come una sequenza casuale possa garantire che la successione sia convergente al 100%. Infatti, se uscissero infinite coppie (1, 1) stimeremmo pi con valore 0 e la sequenza con tutte coppie (1, 1) ha la stessa probabilità della sequenza casuale che usi ... allo stesso modo nessuno puo' impedire che si presenti una successione che per ad un certo punto presenti una serie di centri eccessiva che porterebbe il valore della stima fuori dal termine epsylon che ti sei prefisso a priori (anche qui' spero di essermi spiegato). Ossia: con il casuale non credo si possa ragionare come con l'analitico, che poi di veramente casuale non c'è modo di simularlo e che prima interviene la precisione delle macchine son d'accordo. Ma dal punto di vista teorico sei sicuro ci sia una dimostrazione matematiche che garantisce la convergenza?

[picchio]

(...)

- riflettevo anche su pi greco e blockchain e potrebbe essere interessante studiare un sistema che usa come generatore casuale gli hash dei blocchi e dia come risultato la stima di pi greco della chain. Si potrebbe applicare una griglia al quadrato 1*1 di k*k linee che danno luogo a k^2 punti nel quadrato, poi si conta dal primo a sinistra in basso verso destra salendo una volta arrivato alla x>=1 (non so se mi son spiegato ...), in sostanza si ottiene un intero per ciascuo degli k^2 punti. SI prende il primo hash della chain, si fa modulo k^2 e si determina il primo estratto. Questo e' il primo lancio. Poi si procede come al solito. Ogni blocco abbiamo un aggiornamento del valore.
La stima dipenderà ovviamente anche dal valore di k. Se ci sono idee su come sceglierlo, magari usando qualcosa legato alla difficoltà...

Se ho capito, riassumendo:
1) dividi il quadrato 1x1 in una griglia regolare di k^2 punti
2) si prende l'hash di ciascun blocco (modulo k^2) e si ottiene così quale è il punto estratto (che corrisponde a uno dei vertici di questa griglia e solo a uno di questi, ad esempio il numero 7512 che corrisponde a una certa posizione nel quadrato)
3) alla fine di tutti i blocchi si calcola la stima di pi greco (che si otterrà di fatto dividendo il numero di centri ottenuti per il numero di blocchi presenti nella blockchain fino a quel momento)
4) ora abbiamo ottenuto una stima di pi greco, e il fatto notevole è che ogni punto è stato generato usando un seed diverso (l'hash del blocco corrispondente)

Ogni nuovo blocco "genera" un nuovo punto nel quadrato (con la limitazione che può essere sempre solo uno di quei k^2 punti). Bella idea!

(...)

Si, hai capito la stessa cosa alla quale pensavo. Aggiunta: al fine di non favorire i numeri bassi bisognerebbe iniziare a contare dall'ultimo estratto.
Non bisogna esagerare con il valore di k (per dare modo all'hash di fare "qualche giro") e per ogni valore di k si otterrebbe una stima (potenzialmente) differente del valore di pi.
Lotterie basate sull'hash in realtà calcolano l'sha512 dell'hash e dividono quello e non l'hash stesso in modo da avere numeri piu' grandi e non soggetti a riduzioni eccessive causate dall'aumento dela difficoltà (alla fine generano numeri sempre piu' piccoli).
Potenzialmente si potrebbero estrarre piu' numeri casuali dallo stesso hash dividendo il quoziente per k^2 ed iterando la procedura fino ad ottenere quoziente nullo. Esattamente come fare la trasformazione di base in base k^2.
Rimane il problema di come si puo' determinare k in modo "coerente" ... si potrebbe legare sia al numero di blocchi che alla difficoltà ed eventualmente si cambia ogni 2016 blocchi, oppure si vede come cambiano le stime per diversi valori di k. Qui' non ho avuto idee in merito.

[picchio]

- quando ho lanciato il programmino che ho fatto ho pensato anche io ad una moneta che ha come sistema di minig qualcosa collegato al numero pi greco, secondo me qualcuno ci ha gia' pensato ... se riesco provo a cercare ...  non sarebbe male ...

Un'idea potrebbe essere :
Difficoltà = numero di cifre del pigreco da "indovinare" (tipo 15 o 20)
Parametro n = numero massimo di punti che si possono generare (tipo 10000) per ottenere una stima entro tale margine di errore

A questo punto si genera l'hash di un blocco, che è il seed, e utilizzando una funzione random (uguale per tutti) si generano fino a 10000 punti. Se non si trova un'approssimazione di pi greco alla 15^ cifra, si modifica il blocco (come succede adesso), si ottiene un nuovo hash, a questo punto si prova la nuova serie (al massimo 10000 lanci) e così via.

In questo modo sarebbe molto dispendioso trovare la soluzione, ma molto facile verificarla.

A pelle i pow non mi convincono molto, non ho le idee ben chiare e ritengo interessante un dialogo, il sistema che hai descritto mi convince (simile a come l'avevo pensato anche io) ma non so quanto sia dispendioso generare la sequenza.
Tenderei ad aggiungere l'indirizzo BTC del minatore in modo che ciascuno abbia probabilità legate al proprio address e forse si distribuirebbe la probabilità di minare anche a chi non ha macchine performanti, temo che una procedura del genere avrebbe come controindicazione una proliferazione di indirizzi al fine di minare ...

Ad esempio (idee alla rinfusa ...): mina il blocco chi ha hash(address) piu' "vicino" ad hash("qualcosa legato al blocco precedente+seed/nonce") e forse si potrebbe inserire il pi greco ... eventualmente si potrebbe far aumentare la distanza consentita qualora dopo 10 minuti non venga generato il blocco (ma credo sia un casino ...)

EDIT: mi sono accorto che ormai l'argomento del thread è cambiato, ho chiesto a HostFat di spostare questo thread per non perdere i contributi di chi vi ha partecipato da una parte, e non utilizzare uno spazio inappropriato in quanto dedicato ai "Servizi" dall'altra

In caso cambia anche subject :-)

[arulbero]

- ha senso parlare di convergenza del algoritmo parlando di numeri casuali? Al massimo si parla di probabilità di commettere un errore minore di x dopo n lanci. Un pochettino come il chi quadro ...

L'algoritmo dal mio punto di vista converge quasi come fosse un limite, da un certo punto in poi l'errore è "sempre" (con "sempre" intendo con probabilità 1) minore di un certo valore e così via, potremmo dire che la successione di stime di pi greco che si aggiorna dopo ogni lancio è una successione di Cauchy (fino al punto in cui subentrano gli errori dovuti alla precisione finita della macchina) che converge a pi greco.

Hai dei riferimenti teorici in merito? Io non riesco a concepire se non una probabilità che sia "minore di" e non vedo come una sequenza casuale possa garantire che la successione sia convergente al 100%. Infatti, se uscissero infinite coppie (1, 1) stimeremmo pi con valore 0 e la sequenza con tutte coppie (1, 1) ha la stessa probabilità della sequenza casuale che usi ... allo stesso modo nessuno puo' impedire che si presenti una successione che per ad un certo punto presenti una serie di centri eccessiva che porterebbe il valore della stima fuori dal termine epsylon che ti sei prefisso a priori (anche qui' spero di essermi spiegato). Ossia: con il casuale non credo si possa ragionare come con l'analitico, che poi di veramente casuale non c'è modo di simularlo e che prima interviene la precisione delle macchine son d'accordo. Ma dal punto di vista teorico sei sicuro ci sia una dimostrazione matematiche che garantisce la convergenza?

Allora cerco di spiegare meglio qual è il mio pensiero.
Sicuramente la probabilità che esca una sequenza di infiniti (1,1) è uguale alla probabilità che esca una qualsiasi specifica altra sequenza casuale: questa probabilità è 0 (il che non vuol dire che non possa accadere).  Quello che succede però è che la probabilità che esca una sequenza dall'insieme delle sequenze la cui proprietà è quella di convergere a pi greco è molto più alta (a occhio direi è una probabilità = 1, il che non vuol dire certezza assoluta ma quasi) della probabilità che esca una sequenza dall'insieme delle sequenze che convergono a 0. In altre parole se genero in modo casuale e uniforme miliardi e miliardi di punti con coordinate tra -1 e 1, appare evidente che i punti "dovrebbero" distribuirsi uniformemente sul quadrato e nel cerchio generando la proporzione di 3,14, mentre non avrebbe senso che tutti i punti andassero ad addensarsi in un angolo fuori dal cerchio generando il valore 0.

Provo con un esempio più classico: se simulo il lancio di una moneta, all'aumentare dei lanci mi aspetto che la frequenza relativa di uscita della "testa" converga a 0,50 (cioè alla sua probabilità di uscita a ogni lancio come prevede la definizione frequentista di probabilità). Questo dice la teoria, non mi aspetto certo che la frequenza di uscita sia 0 perchè escono infinite "croci". In questo senso si dice un po' impropriamente che ha probabilità 0 la sequenza di sole "croci", poichè ha una proprietà (il tendere al valore di 0 teste) che va contro la definizione di probabilità (e infatti ce l'ha solo lei quella proprietà), mentre una sequenza che presenta un numero di "teste" e "croci" più equilibrate ha una "probabilità di uscita molto maggiore" - anche qui un po' impropriamente - semplicemente perchè è quella proprietà che è più probabile (nel senso che quest'ultima sequenza condivide questa proprietà con molte altre sequenze).  
E se uscissero improvvisamente 20000 croci di seguito? La teoria dice che potrebbero benissimo uscire, ma con una probabilità così bassa (1 volta ogni 2^20000 casi) che con ogni probabilità (quindi probabilità 1) questo accadrebbe solo dopo aver generato talmente tanti miliardi di punti, che questa sottosequenza speciale di uscite non sposterebbe di una virgola il dato complessivo.

Sono invece d'accordo sul fatto che qui non si tratta di una convergenza proprio come quella dell'analisi, nel senso che non è possibile definire a priori, data una certa epsilon, un valore N della successione oltre al quale tutti i valori della successione sono localizzati in un intorno di raggio epsilon del valore limite.

Immagina per finire di non conoscere il valore vero di pi greco: come faresti a stimarlo? Genereresti miliardi e miliardi di punti, i quali porterebbero a una successione di stime di pi greco che oscillerebbero (con oscillazioni sempre meno ampie) intorno a un valore limite, una specie di asintoto orizzontale che sarebbe per te il valore di pi greco. Più punti generi più ti avvicini (a meno di qualche ovvia oscillazione ma di decrescente ampiezza, come fanno anche le successioni dell'analisi peraltro) al valore limite. In questo senso intendo dire che l'algoritmo converge da qualche parte, perchè è proprio così, e più lo fai girare meglio è (con ogni probabilità )

[picchio]

(...)
Sono invece d'accordo sul fatto che qui non si tratta di una convergenza proprio come quella dell'analisi, nel senso che non è possibile definire a priori, data una certa epsilon, un valore N della successione oltre al quale tutti i valori della successione sono localizzati in un intorno di raggio epsilon del valore limite.

Perfetto. Su questo ci siamo ...

Immagina per finire di non conoscere il valore vero di pi greco: come faresti a stimarlo?
(...)

Secondo me il metodo Monte Carlo è solo una specie di "gioco" che non puo' servire a dire con certezza quale sia l'ennesima cifra di pi greco (neanche se n=1) in quanto nessuno puo' escludere che prima o poi, andando oltre con i punti, la stima ottenuta con tale metodo non cambi tale cifra (per poi rientrare ma come fai ad essere sicuro?). Anzi, mi aspetto che all'infinito ci sia una sequenza tale che possa cambiare il valore della cifra che hai scelto di stimare.
Ma credo che non se ne possa uscire facilmente, fior fiore di matematici hanno parlato di infinitesimi e hanno dato vita all'analisi matematica ... bisognerebbe capire se con la definizione assiomatica di probabilità https://it.wikipedia.org/wiki/Probabilit%C3%A0#Definizione_assiomatica si può arrivare a qualcosa di "certo" ma io non ho sicuramente le competenze per approfondire tale argomento.

[arulbero]

Certo al 100% forse no, ma con probabilità 1 sì  
Tu dici che all'infinito potrebbe accadere che si presenti una successione che sconvolga il dato complessivo, io dico che più si va avanti più é improbabile che questo accada, e per improbabile intendo che é più facile indovinare una chiave privata da una chiave pubblica che dopo una successione di 1000 miliardi di punti ti trovi una stima di pi greco di 2,5!

[picchio]

Certo al 100% forse no, ma con probabilità 1 sì  
(...)

100% è esattamente p(E)=1. Comunque siamo OT, ci vorrebbe un forum di matematici e se ne potrebbero vedere delle belle, rimanendo in topic potremmo approfondire gli altri aspetti ...
Un giorno, se sapro' leggere la chain con qualche software,  provo a stimare pi con gli hash casuali della chain con griglia k*k, magari sarebbe bello trovare una funziona f(k, blocco) e vedere come si comporta ...
E un algoritmo pow/pos o prova di esistenza che coinvolga pi greco non sarebbe male.

[arulbero]

Certo al 100% forse no, ma con probabilità 1 sì  
(...)

100% è esattamente p(E)=1.

Sì, 100% corrisponde a p(E)=1, ma io preferisco utilizzare quest'ultima notazione perchè mi sembra che quando si dice 100% lo si usi come sinonimo di "certo, sicuro" il che non è corretto.
Se un evento non può accadare allora sicuramente ha probabilità 0, viceversa se un evento ha probabilità 0 non è detto che non possa verificarsi. Analogamente, se un evento accadrà sicuramente allora ha probabilità 1, ma se un evento ha probabilità 1 non è detto che si verifichi sicuramente.

Nel nostro caso, in che senso la nostra successione di stime di pi greco converge con probabilità 1 a pi greco? Nel senso che fissato un epsilon piccolo a piacere, da un certo valore N in poi l'insieme dei valori della successione per cui la stima di pi greco esce dall'intorno di raggio epsilon di pi greco ha misura 0, cioè può benissimo capitare che per qualche valore dopo N punti la successione si discosti dalla sua direzione principale (direzione che la teoria ci assicura esistere e verso la quale la nostra successione deve puntare), ma il numero di questi valori è trascurabile rispetto agli infiniti altri valori per i quali la successione starà in quell'intorno di pi greco.

Soprattutto quello che importa è che la nostra successione mostra chiaramente di localizzare in intervalli sempre più ristretti il suo "obiettivo", per cui è chiaro che se a un certo punto dovesse accadere (e ripeto, questo fatto può accadere solo con probabilità 0) che per qualche punto la successione smetta di convergere ed inizi a oscillare a caso, questo fenomeno sarebbe facilmente riconoscibile ed eliminabile, essendo il suo trend principale facilmente individuabile.
 

[picchio]

A quale definizione di probabilità fai riferimento?
Per come capisco direi quella soggettiva che, pur piacendomi, non ho mai approfondito a dovere, a pelle direi che e' quella che potrebbe dare maggiori soddisfazioni.
Mi fa strano pensare ad un evento che ha probabilità 0 (zero) ma si puo' verificare.

[arulbero]

A quale definizione di probabilità fai riferimento?
Per come capisco direi quella soggettiva che, pur piacendomi, non ho mai approfondito a dovere, a pelle direi che e' quella che potrebbe dare maggiori soddisfazioni.
Mi fa strano pensare ad un evento che ha probabilità 0 (zero) ma si puo' verificare.

In probabilità si parla di evento quasi certo quando esso accade con probabilitá 1, di evento certo se esso accade sempre, sicuramente, e per gli eventi contrari vale lo stesso concetto.

Esempio del tipo 1: se hai un generatore di una distribuzione uniforme di numeri reali tra 0 e 1, la probabilità che esca un numero qualsiasi, per esempio 0,458 é 0, nel senso che é minore di una qualsiasi altra probabilitá positiva ( é minore di 0,1, di 0,00001, di 0,00000000001 ... semplicemente perché c'é un solo caso favorevole su infiniti possibili ) ma non é certo impossibile che esca; quindi si dice che l'evento "esce 0,458" é un evento che quasi certamente non accadrá ( o che accadrá con probabilitá 0 )

Esempio del tipo 2: se lancio un dado l'evento "esce un numero maggiore di 6" é un evento che certamente non accadrá.

Qui si sta usando la probabilitá in senso assiomatico, e in particolare si inquadra nel contesto della teoria della misura. I problemi nascono quando devi confrontare uno spazio degli eventi favorevoli discreto e finito con uno spazio degli eventi possibili infinito e/o continuo, oppure due spazi infiniti di diverse dimensioni. Di solito nel caso dell'esempio 1 non si calcola mai la probabilitá di un evento "0-dimensionale" se sei in uno spazio degli eventi 1-dimensionale ( il segmento ) ma si parla di densitá di probabilitá oppure di probabilitá che esca un valore all'interno di un certo intervallo.

Dai un'occhiata qui
https://it.m.wikipedia.org/wiki/Quasi_certamente
EDIT: ti ricorda qualcosa il bersaglio circolare? 

[bertani]

Ops, mi ero perso il thread  

Nostalgia! Cinque anni fa avevo scritto un programmino per fare proprio questo (senza multithreading, in asm, per un microcontrollore a 8 bit, pic16f628a); se qualcuno vuole farsi 2 risate, ecco il sorgente: https://github.com/bertani/piProject/blob/master/pi_project.asm  

[picchio]

Ops, mi ero perso il thread  

Nostalgia! Cinque anni fa avevo scritto un programmino per fare proprio questo (senza multithreading, in asm, per un microcontrollore a 8 bit, pic16f628a); se qualcuno vuole farsi 2 risate, ecco il sorgente: https://github.com/bertani/piProject/blob/master/pi_project.asm  

Carino l'oggetto :-), non capendo di assembler ti chiedo, come generavi i numeri casuali?