Runs

[axpgn]

Consideriamo il numero $N=025865413989732$
A prima vista niente di particolare ma se lo scriviamo così

possiamo notare che ci sono delle "salite" e delle "discese" (che l'autore chiama per l'appunto "runs")
Nell'esempio abbiamo le salite $0258, 139, 89$ e le discese $86541, 98, 9732$.

Escludendo i numeri che contengono due cifre adiacenti uguali e ammettendo che lo zero possa essere la cifra iniziale, la domanda che sorge spontanea ( ) è:

Qual è il numero medio di "runs" contenuti in un numero di $n$ cifre? E quale la lunghezza media di un "run" in un numero di $n$ cifre?


Cordialmente, Alex

[axpgn]

C'è qualcuno?

[qualcuno4]

"axpgn":C'è qualcuno?

Eccomi

[axpgn]

Non ti vedo, dove sei?

[axpgn]

Nonostante il grande successo, ritengo sia ora di chiudere

Il numero di tali interi composti da $n$ cifre è $N=10*9^(n-1)$.

Il numero medio di "runs" per un numero di $n$ cifre è quindi il rapporto tra il numero totale $T$ di tutti i "runs" di tutti gli $N$ interi e $N$ stesso cioè $M=T/N$

Come calcolare $T$?
Un modo "semplice" è quello di sommare tutti i "runs" $r_1$ che iniziano alla prima posizione e poi sommarvi i "runs" $r_2$ che iniziano alla seconda posizione e poi sommarvi quelli che iniziano alla terza posizione e così via fino a sommarvi quelli che iniziano alla poszione $n$ cioè $T=r_1+r_2+r_3+...+r_n$, perciò la media diventa $M=(r_1+r_2+r_3+...+r_n)/N=sum_(i=1)^n r_i/N$
Chiaramente $r_i/N$ è la probabilità che un numero scelto a caso dagli $N$ numeri abbia un "run" che inizia alla $i$-esima posizione; chiamando $p_1$ questa media diventa $M=sum_(i=1)^n=p_i$.

Adesso come calcolare $p_1$?
Chiaramente $p_1=1$ e $p_n=0$, ma le altre?
Consideriamo, per ogni posizione $i$ (diversa dalla prima e l'ultima), anche la cifra precedente la $i$-esima e quella successiva alla $i$-esima.
Possiamo avere quattro casi:
1) tre cifre ascendenti
2) tre cifre discendenti
3) l'$i$-esima cifra è il massimo delle tre
4) l'$i$-esima cifra è il minimo delle tre
Ovvero la $i$-esima cifra inizia un "run" solo e certamentente nei casi 3) e 4) e $p_1=prob[3]+prob[4]$ ed equivalentemente $p_1=1-(prob[1]+prob[2])=1-2*prob[1]$
Ora tre cifre ascendenti possano essere scelte in $((10),(3))$ modi mentre tre cifre consecutive del nostro numero di $n$ cifre possono essere scelte in $10*9^2$ modi.
Mettendo insieme il tutto otteniamo $p_i=1-2*(((10),(3)))/(10*9^2)=1-(2*10*9*8)/(3*2*10*9*9)=1-8/27=19/27$ e in definitiva la nostra media è $M=sum_(i=1)^n p_1 = 1+(n-2)p_1+0=1+19/27(n-2)$

E voilà!

Cordialmente, Alex