Quante estrazioni mi servono?

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Pigkappa
Messaggi: 1209
Iscritto il: 24 feb 2005, 13:31
Località: Carrara, Pisa

Quante estrazioni mi servono?

Messaggio da Pigkappa »

Si supponga che R(n) un numero casuale tra 0 e n-1 (estremi inclusi). Continuo ad applicare R; R(R(n)) sara' un numero casuale tra 0 e R(n) - 1. Se parto da n = 2015, quante volte devo applicare R, in media, per arrivare a 0?
Saro00
Messaggi: 115
Iscritto il: 27 mag 2015, 10:52
Località: Provincia di Milano

Re: Quante estrazioni mi servono?

Messaggio da Saro00 »

Cosa intendi per "in media"?
Un giorno di questi mi metteranno in prigione per aver stuprato troppi problemi. 8)
Pigkappa
Messaggi: 1209
Iscritto il: 24 feb 2005, 13:31
Località: Carrara, Pisa

Re: Quante estrazioni mi servono?

Messaggio da Pigkappa »

Immagina di condurre questo "esperimento" molte volte (diciamo 10^100), e dimmi la media (somma i risultati e dividi per 10^100). Ci sono anche altri modi di intendere la media, che danno tutti lo stesso risultato.

Esempio: quante volte devo lanciare una moneta per ottenere testa, in media?
Se lancio una moneta, ho probabilità 1/2 di fare testa per la prima volta al primo colpo; 1/4 al secondo; 1/8 al terzo; 1/16 al quarto; la media di lanci e'
$ 1 \times 1/2 + 2 \times 1/4 + 3 \times 1/8 + 4 \times 1/16 + ... $
(si può semplificare questa espressione e dimostrare che questa somma fa 2, ma non c'entra nulla col mio problema)
mr96
Messaggi: 151
Iscritto il: 05 gen 2015, 01:07

Re: Quante estrazioni mi servono?

Messaggio da mr96 »

Sarebbe già buono dire "per quali k, dopo k applicazioni, ho più del 50% di probabilità di fare 0 all'k+1esima applicazione?"
Saro00
Messaggi: 115
Iscritto il: 27 mag 2015, 10:52
Località: Provincia di Milano

Re: Quante estrazioni mi servono?

Messaggio da Saro00 »

Ok, forse ho capito cosa significa "in media", io l'ho interpretato come il numero $ j $ tale che applicando $ R $ $ j $ volte, si ha la probabilità più alta di arrivare a $ 0 $. In spoiler c'è la soluzione.
Testo nascosto:
Definisco $ \mathbb{A} $ un insieme che contiene $ n-uple $ non ordinate con $ 2015 \le n \le 1 $, di numeri naturali $ k $ tali che $ 2014 \le k \le 0 $, tutti distinti, nei quali è presente sempre lo $ 0 $.
Esiste una corrispondenza biunivoca tra queste $ n-uple $ e la funzione $ R(R(...(R(n)..)) $ che finisce con $ 0 $.
Presa una sequenza di mosse che portano a $ 0 $ posso associare ad ogni passaggio (ad esempio il $ j-esimo $) della sequenza un numero, che indica il numero che si è formato iterando $ R(n) $ $ j $ volte, e una $ n-upla $ indica tutti i numeri della sequenza di mosse.
Al contrario, presa una $ n-upla $ posso creare una sequenza di mosse tale per cui esiste una sequenza di mosse che raggiunge tutti i numeri della $ n-upla $
Ora in questo insieme $ \mathbb{A} $ sono contenute tutte le possibili combinazioni di mosse che permettono di arrivare a $ 0 $, per calcolare quante applicazioni permettono di arrivare, con maggiore probabilità, a $ 0 $, basta che conto quante sono le $ n-uple $ con $ n $ elementi $ \forall n \in [1,2015] $ e vedere per quale $ n $ ci sono più $ n-uple $.
Le$ j-uple $ con $ j $ elementi sono $ \frac{2015!}{(2015-j)!(j)!}- \frac{2014!}{(2014-j)!(j)!} $, ovvero il numero di $ j-uple $ non ordinate con $ 2015 $ elementi meno il numero di $ j-uple $ non ordinate con $ 2014 $ elementi, ovvero quelle senza lo $ 0 $.
Il problema è diventato calcolare il valore di $ j $ che massimizza $ \frac{2015!}{(2015-j)!(j)!}- \frac{2014!}{(2014-j)!(j)!}=\frac{(2014)!}{(2015-j)!(j-1)!} $, il che equivale a dimostrare quando $ (2015-j)!(j-1)! $ è minimo, ovvero quando $ 2015-j=j-1 \iff j=1008 $, che è appunto la tesi.
Ultima modifica di Saro00 il 23 ott 2015, 20:27, modificato 1 volta in totale.
Un giorno di questi mi metteranno in prigione per aver stuprato troppi problemi. 8)
Pigkappa
Messaggi: 1209
Iscritto il: 24 feb 2005, 13:31
Località: Carrara, Pisa

Re: Quante estrazioni mi servono?

Messaggio da Pigkappa »

La tua interpretazione purtroppo non è equivalente alla media e il risultato é diverso (parecchio diverso)...
RiccardoKelso

Re: Quante estrazioni mi servono?

Messaggio da RiccardoKelso »

Testo nascosto:
$\displaystyle M_n=\frac {1}{n} \sum_{i=0}^{n-1} {(M_i+1)}=\frac {1}{n}(n+ \sum_{i=0}^{n-1} {M_i})=1+\frac {1}{n} \sum_{i=0}^{n-1} {M_i}$ (con $M_0=0$)
Ora pappa e poi sclero dietro alla chiusa, se non salta fuori che pure la ricorsiva è errata.
EvaristeG
Site Admin
Messaggi: 4896
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Quante estrazioni mi servono?

Messaggio da EvaristeG »

questa è necrofilia ... e nemmeno bella e buona, ma brutta e cattiva! Btw,la tua migliore speranza per avere un parere informato sul fatto che la formula che hai dato possa essere giusta è spiegare come ci sei arrivato :D
RiccardoKelso

Re: Quante estrazioni mi servono?

Messaggio da RiccardoKelso »

Questa è l'idea di fondo, insieme a un'ulteriore evoluzione della formula (senza però la soluzione finale :? )
Testo nascosto:
Consideriamo un caso generico in cui dobbiamo calcolare la media di passi per giungere a $0$ applicando $R$ a $n$. Al primo passo abbiamo una probabilità di $\frac {1}{n}$ di ottenere un particolare intero $n_1$, con $0\le n_1\le n-1$. Per ognuno di questi casi, abbiamo che la media del numero di passi che ancora manca è ovviamente la media di passi che mancherebbe dall'inizio se il numero $n_1$ fosse invece considerato l'iniziale; ma per arrivarci abbiamo fatto già un passo. A questo punto la prima forma della ricorsiva dovrebbe essere sufficientemente giustificata.

Se non sbaglio, si può proseguire con $M_n=\displaystyle \sum_{i=1}^{n}{\frac {1}{i}}$, per $n\neq 0$. La semplicità disarmante di questa espressione mi induce a pensare che DEBBA esserci un modo per chiuderla, ma apparentemente non sono abbastanza sveglio per trovarlo. :roll:
EvaristeG
Site Admin
Messaggi: 4896
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Quante estrazioni mi servono?

Messaggio da EvaristeG »

Beh, se vuoi una formula chiusa per la somma degli inversi degli interi, ti consiglieri di cercare Serie Armonica o Numeri Armonici su google e poi desistere.
Pigkappa
Messaggi: 1209
Iscritto il: 24 feb 2005, 13:31
Località: Carrara, Pisa

Re: Quante estrazioni mi servono?

Messaggio da Pigkappa »

Confermo che la risposta e soluzione sono uguali alle mie.

Adesso fatemi quello in matematica ricreativa che invece non mi è venuto :p
AlexThirty
Messaggi: 217
Iscritto il: 20 giu 2015, 20:58

Re: Quante estrazioni mi servono?

Messaggio da AlexThirty »

RiccardoKelso ha scritto:Questa è l'idea di fondo, insieme a un'ulteriore evoluzione della formula (senza però la soluzione finale :? )
Testo nascosto:
Consideriamo un caso generico in cui dobbiamo calcolare la media di passi per giungere a $0$ applicando $R$ a $n$. Al primo passo abbiamo una probabilità di $\frac {1}{n}$ di ottenere un particolare intero $n_1$, con $0\le n_1\le n-1$. Per ognuno di questi casi, abbiamo che la media del numero di passi che ancora manca è ovviamente la media di passi che mancherebbe dall'inizio se il numero $n_1$ fosse invece considerato l'iniziale; ma per arrivarci abbiamo fatto già un passo. A questo punto la prima forma della ricorsiva dovrebbe essere sufficientemente giustificata.

Se non sbaglio, si può proseguire con $M_n=\displaystyle \sum_{i=1}^{n}{\frac {1}{i}}$, per $n\neq 0$. La semplicità disarmante di questa espressione mi induce a pensare che DEBBA esserci un modo per chiuderla, ma apparentemente non sono abbastanza sveglio per trovarlo. :roll:

Scusa il disturbo ma potresti spiegami come arrivi alla formula perché salti il procedimento. Ho una mezza idea su come ci sei arrivato ma non mi è chiarissimo

Graziee
Un bresciano esportato nel cremonese

-"Dal palazzo di giustizia di Catania o esci con più soldi di prima, o non esci proprio"
-"Baroni uscirebbe con un Win - Win".
Tutti si mettono a ridere, e allora intuisco che non aveva detto "Weed - Win" come avevo capito.
RiccardoKelso

Re: Quante estrazioni mi servono?

Messaggio da RiccardoKelso »

Puoi farlo sia partendo da $M_1$ e salendo sia scendendo da $M_n$: noti che a denominatore si trova $n!$ mentre a numeratore trovi $n$ addendi tutti diversi con nessun fattore comune a tutti ma che possono essere ottenuti dividendo $n!$ per tutti i numeri da $1$ a $n$ (ogni addendo viene diviso per un numero diverso).
remat7
Messaggi: 21
Iscritto il: 21 feb 2014, 11:18

Re: Quante estrazioni mi servono?

Messaggio da remat7 »

Applichiamo $ R(n) $. Se è 0 ho vinto sennò dovrò applicare $ R(n-1) $.
La probabilità che sia $ 0 $ è ovviamente $ P_n(0)= \frac{1}{n} $, per cui la probabilità che dovrò applicare $ P(R(n-1)) = \frac {n-1}{n} $.
Ora applichiamo $ R(n-1) $: $ P_{n-1}(0)= \frac {n-1}{n} \frac{1}{n-1}=\frac{1}{n} $. La probabilità di dover applicare $ R(n-2) $ è $ P(R(n-2)) = \frac {n-1}{n} \frac {n-2}{n-1} =\frac {n-2}{n} $.
Capite bene che vale sempre $ P_i(0)= \frac {1}{n} $.
Ora per la definizione che hai dato di media il risultato dovrebbe essere $ M = \frac {1}{2015} + \frac {2}{2015} + ... + \frac {2014}{2015} + 1 $
$ M= \frac {1}{2015} \displaystyle \sum_{n=1}^{2015} n = 1008 $
Ma siccome hai già detto che è sbagliato, vorrei spiegassi meglio cosa significhi media in questo esercizio.
Pigkappa
Messaggi: 1209
Iscritto il: 24 feb 2005, 13:31
Località: Carrara, Pisa

Re: Quante estrazioni mi servono?

Messaggio da Pigkappa »

remat7 ha scritto:Applichiamo $ R(n) $. Se è 0 ho vinto sennò dovrò applicare $ R(n-1) $.
No; se e' 0 hai vinto, senno' devi applicare R(R(n)). E poi R(R(R(n))). E cosi' via. Penso che il fraintendimento derivasse da questo, piu' che dalla definizione di media...

Se il tuo numero casuale e' 255, ora prendi un altro numero casuale tra 0 e 255. Se questo e' 101, ora ne prendi uno tra 0 e 101. E cosi' via.
Rispondi