Re: Estrazioni casuali
 

Quel che segue piacerà a Nino I ;)

Costruisco una tabella A di n righe ed n colonne –e quindi una matrice quadrata di n^2 elementi che chiamo A(h, k) – nel modo seguente.
• La prima riga, che però considero la numero 0, ha tutti gli elementi uguali ad 1
1)
A(0, k) = 1 per ogni k per cui 0 ≤ k ≤ n.
• Le righe successive incominciano sempre con 1 e ogni successivo elemento è la somma del precedente e dell'elemento che sta nella stessa colonna della riga precedente
2)
• A(h, k) = A(h, k–1) + A(h–1, k) per ogni h e per ogni k tra 1 ed n inclusi.
Con queste regole viene una tabella così:NB. La proprietà con cui la tabella è definita equivale a quest'altra:
• Un elemento qualsiasi è la somma degli elementi della riga precedente dall'inizio fino a quello sulla sua stessa colonna inclusa.
3)
A(h+1, k) = A(h, 0) + A(h, 1) + A(h, 2) + ... + A(h, k) per ogni h e ogni k tra 0 ed n inclusi

Mandiamo a memoria questa proprietà!
Ci servirà per stabilire che la probabilità di non “sballare” dopo k sorteggi vale 1/k!

Uno sguardo a questa tabella ... e si nota subito che se si scambiano le righe con le colonne non cambia niente. E' una matrice simmetrica (rispetto alla diagonale discendente da sinistra a destra), cioè uguale alla sua trasposta.
4)
A(h, k) = A (k, h)
Ma c'è di più: se si prendono per righe le linee ascendenti da sinistra a destra si nota subito che gli elementi sono i coefficienti binomiali C(r, m) del "Triangolo di Tartaglia".
1
1 2 1
1 3 3 1
1 4 6 4 1
---
Deve essere così perché la proprietà 2) che definisce la matrice, rispetto alle linee oblique ascendenti da sinistra a destra è la stessa proprietà caratteristica dei coefficienti binomiali:
C(r+1,m) = C(r, m–1) + C(r, m).
In sostanza, gli elementi della tabella valgono
5)
A(h, k) = A(k, h) = C(h+k, h) = C(h+k, k)
Ciò permette di calcolare direttamente (senza ricorrenza) gli elementi della tabella essendo notoriamente:
6)
C(n+k, k) = (n+k)!/(n! k!) = [(n+1)(n+2) ·... ·(n+k)]/k!

Tornando al quiz, in luogo di considerare la distribuzione uniforme e continua sull’intervallo 0 ≤ x ≤ 1, consideriamo la distribuzione “discreta” di n razionali – con n grande a piacere – equispaziati su questo intervallo con la legge Xr = (2r + 1)/(2n) per r intero da 0 ad n–1. Il numero T(k, n) di k–tuple sorteggiabili è allora n^k. Se le k–tuple sono tutte equiprobabili, la probabilità di non “sballare” dopo k sorteggi è il rapporto tra il numero di k-tuple la somma dei cui elementi non supera 1 ed il numero totale di k-tuple sorteggiabili n^k.

Se k = 1, evidentemente non si sballa mai.
Siamo allora nella situazione della riga numero 0 della tabella di sopra arrestata per k = h = n.
Il numero di numeri sorteggiabili è in tutto n. Tutti i numeri sono minori di 1: T(n, 1) = n. Ricordando i simboli A(h, k) della tabella di sopra abbiamo dunque:
T(n, 1) = A(n, 1) = A(1, n) = n.

Passiamo al caso k = 2. Siano X1 ed X2 i numeri sorteggiati. Per non sballare deve essere X1 + X2 ≤ 1. Se il primo numero sorteggiato è X1 = (2r+1)/(2n) ed il secondo è (2s+1)/(2n), deve essere 2(r+s)+2 ≤ 2n, ossia s ≤ n–1. Dato X1, cioè r, di tali numeri X2 ce ne sono n–r.
Se dunque r vale n – 1 ce n’è uno solo, se r vale n–2 ce ne sono 2, ... se r vale 0 ce ne sono n. In tutto sono 1 + 2 + 3 + ... + n. Ci troviamo allora nell riga numero 1 della tabella e, per la proprietà caratteristica della tabella, avremo:
T(n, 2) = A(n, 2) = A(2, n) = A(1, 0) + A(1, 1) + A(1, 2)+... + A(1, n) =
= 1 + 2 + 3 + ... + n = n·(n+1)/2.

Passiamo al caso k = 3.
Detto X3 = (2r+1)/(2n), r può variare da 0 ad n – 1. Supponiamolo massimo: r = n–1. Se X1 ed X2 sono minimi, cioè X1 = X2 = 1/(2n) abbiamo X1 + X2 + X3 = [(2n–1)+2]/(2n) = 1+1/(2n) : la terna fa “sballare”.
Fissato r, il numero di coppie per le quali non si sballa è T(r, 2). Il numero di terne con le quali non si sballa è allora
T(n, 3) = T(0, 2) + T(1, 2) + ... +T(n–1, 2) = A(0, 2) + A(1, 2) +...+ A(n–1, 2) = A(n–1, 3) = A(3, n–1)

Supponiamo che per ogni k < m sia T(n, k) = A(n, k) .
[NB. Anche se qualche volta fosse invece T(n, k) = A(n –1, k), un tale errore non inficierebbe l'obiettivo finale perché non cambierebbe il limite di T(n, k)/n^k per n tendente all'infinito]
Per k = m, il numero di m-tuple con le quali non si sballa è allora:

T(n, m) = T(0, m–1) + T(1, m–1) + ... + T(n–1, m–1) =
= A(0, m–1) + A(1, m–1) + ... + A(n–1, m–1) = A(n–1, m) = A(m, n–1).

Tenendo conto della 6) abbiamo infine
T(n, k) = A(k, n–1) = C(n+k–1, k) = [n·(n+1)· ... ·(n+k–1)]/k!

Sicché la probabilità di non “sballare” dopo k sorteggi di un numero compreso tra 0 e 1 sorteggiato da un insieme di n numeri equiprobabili è
7)
T(n, k)/(n^k) = {[n·(n+1)· ... ·(n+k–1)]/(n^k)} · (1/k!).

E’ allora evidente che al tendere di n all’infinito T(n, k)/(n^k) tende a 1/k!
-----------------
:hello:

Re: Estrazioni casuali
 

La mia soluzione è questa:

1/4 indipendentemente dal numero degli alunni!

I 4 alunni menzionati (Mario, Claudia, Aldo e Giulio) potrebbero essere interrogati in 4! = 24 ordini diversi.

L'affermazione della Prof. ne invalida ben 16;
restano questi 8 casi:
M - C - A - G
M - C - G - A
M - A - C - G
M - A - G - C
M - G - A - C
M - G - C - A
G - M - C - A
G - M - A - C

Come si può vedere, solo due volte su 8 Giulio precede Mario.

E gli altri 25? Possono essere inseriti a piacere prima, dopo o tra i quattro menzionati.

:hello:

Re: Estrazioni casuali
 

Questo quiz l'ho sbagliato due volte. :D

Perchè avevo calcolato anche una probabilità del 50%, anche se mi sono accorto in tempo che era errata. Le simulazioni non sono sempre attendibili, perchè si può sbagliare ad impostarle.

In questo caso ad esempio, avevo imposto al programma che Claudia fosse interrogata sempre prima di Aldo, mentre questo non è vero.

Quindi attribuivo ad Aldo un valore random da 1 a 29, e dopo a Claudia un valore random tra 1 e Aldo, e questo faceva si che il valore di Claudia fosse mediamente più piccolo di quello che doveva essere.

La procedura corretta era invece quella di generare due valori random da 1 a 29.
In questo modo il valore più piccolo tra i due, non è cosi' piccolo come con il calcolo precedente.


:hello:

Re: Estrazioni casuali
 

:eek: :mmh:
---------------------
Secondo me, conviene andare il più ... pedissequamente possibile (infischiandosene dell'efficienza nei riguardi del tempo di esecuzione del programma).

Io la simulazione la farei dunque cosi:
A) Assegno a Giulio, Mario, Claudia e Aldo dei numeri precisi (per esempio rispettivamente i numeri 1, 2, 3 e 4).
Quindi continuo a ripetere il sorteggio completo dei numeri tra 1 e 29 e man mano che li genero li metto in ordine crescente su un array A di indice da 1 e 29.
sorteggio ultimato individuo in esso le posizioni degli elementi che valgono 2, 3 o 4 {che sono i nomi locali di Mario, Claudia e Aldo}.
Siano rispettivamente
A[h] = 2; {questo è il nome locale di Mario}
A[j] = 3; {questo è il nome locale di Claudia}
A[k] = 4; {questo è il nome locale di Aldo}
Quindi guardo se è verificata la prima proposizione:
« Mario sarà interrogato prima di Claudia e prima di Aldo»
che nel programma diventa
(*) h < j AND h < k
Se è verificata allora
• incremento di 1 il contatore N (con partenza da 0)
• individuo nell'array l'elemento che vale 1 e sia questo A[r] {A[r] è il nome locale di Giulio)
e controllo se è verificata la 2ª proposizione cioè
«Giulio interrogato prime di Mario»
che ora diventa
(**) r < h.
Se questa è verificata incremento di 1 un secondo contatore M.
Mi fermo quando N è grande quanto avevo previsto (un milione?).

La cercata probabilità é il rapporto M/N

---------------------
:hello:

Re: Estrazioni casuali
 

Si, hai ragione. In effetti mi ero confuso perchè avevo cominciato con il considerare che per M(Mario) la posizione nell'array potesse variare da 1 a 27, e per C(Claudia) e per A(Aldo), da 2 a 27, oppure da 3 a 28 a secondo di quale dei due fosse interrogato per prima.

No, non esageriamo, non hai bisogno di sorteggiare ogni volta tutte e 29 le posizioni degli studenti, ma solo quelle dei quattro studenti che vengono menzionati nel quiz.

La simulazione è molto più semplice.

Attribuisci dei valori casuali tra 1 e 29 ai tre studenti M, C, A.

Se C<>A and M<C and M<A allora questi valori sono validi, se invece una di queste condizioni non è rispettata, ripeti l'operazione fino a quando non ottieni dei valori che rispettino le condizioni date.

Una volta ottenuti questi valori M, C, A

Attribuisci un valore casuale tra 1 e 29 a G.

Se G è diverso dai valori M, C, A, è un valore valido, se non lo è, ripeti l'operazione finchè non ottieni un valore di G diverso da quello degli altri.

Se G<M incrementa un contatore (Punti) di una unità.

Ripeti questa procedura per un gran numero di Volte (ad es. un milione)

La Probabilità richiesta è data dal rapporto Punti/Volte.




volte=1000000

for v=1 to volte
Do
c= int(rnd *29) + 1
a= int(rnd *29) + 1
m= int(rnd *29) + 1
Loop until c<>a and m<a and m<c

Do
g= int(rnd * 29)+ 1
Loop until g<>m and g<>c and g<>a

if g<m then punti=punti+1
next

response.write("Probabilità=" & punti/volte)


:hello:

Re: Estrazioni casuali
 

Ma io non ho detto che è necessario fare così!
Ho espresso l'idea che, in questo modo "pedissequo" (se vuoi sprecone) la simulazione
1) è giusta
2) è la più facile da implementare (evitando tutti i ragionamenti con cui si possono dedurre – come vedo che fai tu – dall'AND delle due condizioni eventuali riduzioni di casi da esaminare ).

Siccome in antico non c'erano né i computer né le calcolatrici meccaniche o elettromeccaniche, a parte casi elementari, la simulazione era intrattabile al pari dell'esame esaustivo di tutti i casi possibili. Allora il ragionare e applicare i teoremi della teoria della probabilità era fondamentale!
Con l'avvento del calcolo automatico, più veloce è questo meno importante è ridurre il numero di cose da fare; cioè: meno importante è il complicare le cose da fare al fine di ridurne il numero.
Per esempio, tu dici che devi variare in tutti i modi possibili le posizioni di soli 4 elementi su 29.
Vedi che allora devi condizionare il tuo generatore random tra 1 e 29 tranne la prima volta.
[La seconda volta devi fargli evitare la posizione uscita la prima volta, la terza volta fargli evitare le due posizioni già uscite, la quarta volta fargli evitare le tre posizioni già uscite.
Mi dirai: «Mi costa molto poco perché basta ripetere fino a che il numero che esce è diverso da quelli già usciti!»
E' vero: ma è pur sempre il risultato di un ragionamento deduttivo, è quindi una complicazione in più sul programma, E tu mi insegni (anche in questo caso) che a volte si sbagliano le conclusioni diel ragionamento!

Insomma: se non ci sono problemi sul tempo di esecuzione, quando si fa simulazione conviene andare il più terra-terra possibile.

Puoi anche metterla così:
a) Le permutazioni di 29 elementi sono 29! (ventinove fattoriale). Le faccio tutte.
b) Seleziono da esse quelle che rispettano la 1ª condizione. Siano queste N.
c) Da queste N seleziono quelle che rispettano la 2ª condizione. Siano esse M.
d) La probabilità richiesta è M/N.
---------------------
Ma il fare tutte le 29! permutazioni è ... più complicato che il non farle!
Siccome 29! è un numero enorme (più di 2·10^46) ci basterà esaminare un suo campione molto numeroso ma ancora enormemente più piccolo di 29! purché ogni elemento del campione abbia la stessa probabilità (di essere cascato nel campione) di ogni altro.

Non c'è nemmeno bisogno che le singole permutazioni siano tutte distinte una dalle altre se il generatore random è "abbastanza" uniforme" non già sul singolo numero estratto ma proprio sulle singole permutazioni.
[E' questa la pulce che una volta ho messo nell'orecchio di Miza. Lui, poco dopo, mi rispose che aveva controllato e che il suo generatore random andava bene anche nell'estrarre liste di k numeri (diciamoli "vettori ai k dimensioni"). Ma proprio perché mi ha risposto poco dopo, vuol dire che il controllo non gli è costato tempi lunghissimi, ossia che 'sto controllo l'ha fatto per un numero massimo di dimensioni ancora piccoletto (qualche decina?).]

Supponiamo che le permutazioni generate siano equiprobabili.
Ecco allora che il punto a) del programma diventa:
a) Prendo un fottìo di permutazioni scelte a caso tra le 29! possibili.
mentre restano inalterati i punti b), c) e d).

Naturalmente non c'è bisogno di registrare le permutazioni prima di esaminarle. C'è bisogno solo di contare quante sono che soddisfano la prima condizione e, tra queste, quante sono che soddisfano la seconda. Il conteggio lo posso fare man mano che genero le permutazioni.
Mi servono allora tre contatori. Uno che conta le permutazioni generate in modo che il programma termini quando è raggiunto il fottìo voluto; uno che cresce di un'unità quando è verificata la 1ª condizione ed un terzo che cresce di 1 quando, essendo già verificata la 1ª condizione, è verificata anche la seconda.Il programma può essere ..." filosoficamente " interpretato così:
• Fin che no so niente l'interrogazione può avvenire con ordine qualsiasi. :D
• Venuto a sapere che l'ordine rispetterà due condizioni
• • Scarto le disposizioni con ordine tale da non rispettare la prima condizione e conto le rimanenti.
• • Fra quelle non scartate guardo quante rispettano anche la seconda e le conto.

--------------
:hello:

P.S.
Se fai anche il rapporto N/F, individui pure la probabilità che venga rispettata la prima condizione ;)

Re: Estrazioni casuali
 

Se lo scopo è quello di evitare degli errori, il tuo "sistema" ha un effetto contrario, perchè introduce un calcolo in più, che potrebbe contenere degli errori.

Generare delle permutazioni di 29 elementi si può fare in diversi modi.

Un metodo potrebbe essere quello di generare 29 numeri casuali, e se questi numeri risultano tutti diversi tra loro, convalidare il risultato.

Questo metodo è estremamente pesante in termini di lavoro del processore, perchè le probabilità che questi numeri siano tutti diversi tra loro sono pochissime.

Questo metodo è basato sullo stesso principio che ho adottato nel mio programma, solo che funziona bene se gli elementi in gioco sono pochi, ma malissimo se sono 29.

Un'altra possibilità sarebbe quella di generare queste permutazioni casuali di 29 elementi, e di scartare i doppioni, mano a mano che si presentano. Ma questo metodo risulta laborioso perchè ogni volta bisognerebbe confrontare un nuovo numero estratto con quelli estratti in precedenza per accertarsi che sia diverso.

In realtà esiste un altro metodo per generare delle permutazioni casuali di 29 elementi, senza sprechi ed in modo veloce ed efficiente. Lo avevo illustrato su questo forum, qualche tempo fa.

Credo che non ho impostato la simulazione nel modo che suggerisci, perchè non avevo l'algoritmo che genera delle permutazioni casuali a portata di mano, ma c'ho pensato anch'io. :)

Solo che nel nostro problema non ci interessa nulla della posizione di tutti e 29 elementi, ma solo quella dei quattro elementi citati.

Quindi per quale ragione agiresti in modo pedissequo?

Se nel generare i quattro valori casuali mi accerto che siano tutti diversi, faccio la stessa cosa che farei se volessi generare delle permutazioni casuali di 29 elementi.

Ma che mi frega di sapere in che ordine sono stati interrogati Guendalina, Francesca, Roberto ecc. se non vengono citati nel problema?

Il mio programma fa le stesse cose che farebbe il programma immaginato da te, ossia genera delle posizioni casuali per i quattro studenti, accertandosi che non ci siano doppioni, e verifica che sia rispettata la condizione imposta, ossia che m<a and m<c

Il tuo programma fa le stesse cose che fa il mio, aggiungendovi delle altre cose che però sono perfettamente inutili.

Il bello è che tu queste cose le capisci perfettamente, ma allora qual è il tuo punto?

La verità è che quel diavolo di Aspesi c'ha "fregati" a tutti e due, perchè il suo quiz non richiedeva una simulazione, ma era sufficiente verificare quante delle possibili permutazioni di quattro elementi, soddisfavano le condizioni poste.

:D

Re: Estrazioni casuali
 

:confused:Vorrei ben vedere...
Questa probabilità è 3,44*10^(-12) tre ogni millle miliardi di prove....


Ehehe...:rolleyes::D

Ciao

Re: Estrazioni casuali
 

1234 4231 1432 1243 3214 4213 3412 3241 1324 4321
1423 1342 2134 4132 2431 2143 3124 4123 3421 3142
2314 4312 2413 2341

GMAC CMAG GCAM GMCA AMGC CMGA ACGM AMCG GAMC CAMG
GCMA GACM MGAC CGAM MCAG MGCA AGMC CGMA ACMG AGCM
MAGC CAGM MCGA MACG

GMAC CMAG GCAM GMCA AMGC CMGA ACGM AMCG GAMC CAMG
GCMA GACM MGAC CGAM MCAG MGCA AGMC CGMA ACMG AGCM
MAGC CAGM MCGA MACG

La probabilità è 1/3.

Re: Estrazioni casuali
 

Non mi pare che sia troppo laborioso accertare che un numero random tra 1 e 29 sia distinto da quelli già precedentemente prodotti.

In pascal mi ricordo che c'era il tipo set (= insieme) di elementi di qualsiasi tipo. L'appartenenza o meno di x all'insieme S era espressa dalla seguente funzione booleana predefinita (tramite la parola riservata in):
x in S.
L'unione di due insiemi si esprimeva col " + "
Supposto che Random(1, N) fosse una precedente routine function che producesse un intero casuale tra 1 ed N inclusi, l'aggiunta ad S di un nuovo elemento casuale non ancora presente in S poteva essere ottenuta con le istruzioni:
k:=Random(1, N);
while k in S do k:=Random(1, N);
S:= S + [k]:

Ma anche senza disporre di una tanto comodo iinguaggio, si può sempre procedere (per esempio) ... come è spiegato qua sotto.

a) Numero random tra 1 e N
Possiedo un generatore random di reali tra 0 e 1.
Un numero intero casuale k tra 1 ed N inclusi è questo: {
k:=int(N*random) + 1; {dove int(x) significa <parte intera del reale x>}
if k=N+1 then k:=k–1;
Un altro modo potrebbe essere quello di costruire un intero tra 1 e 2^c, dove c è l'esponente intero tale che 2^(c–1) < N ≤ 2^c con la routine seguente B) Permutazione random degli N interi tra 1 ed N inclusi
Suppongo di possedere un generatore random di numeri interi tra 1 ed N compresi (prodotti, per esempio, con uno dei due metodi di sopra), ossia una funzione – che chiamo random(1, N) – per la quale con l'istruzione [size=3]
k:=random(1, N)[/size]
ottengo un numero intero k casuale tra 1 ed N.
Allora:
• Assumo una variabile A di tipo array unidimensionale di N interi tra 1 ed N inclusi e azzero tutti i suoi N elementi.
• Produco il primo k casuale tra 1 e 29 e lo carico al primo posto dell'array A
• Continuo a produrre k casuali tra 1 e N. Se il nuovo k casuale non è già presente nell'array A lo carico nel posto successivo a quelli già occupati. Se era già presente ripeto la produzione fino a che ne trovo uno non ancora presente (e carico questo nel prossimo posto non ancora occupato). Arrivato ad averne caricati N–1, potrei anche cercare quale numero k è ancora assente e schiaffarlo all'N-esimo posto. La routine della ricerca di questo numero k ancora assente potrebbe essere la seguente:Chiamo Last(A, N) una routine come questa che mi completa la permutazione casuale degli N interi tra 1 ed N caricati sull'arrey A una volta che A sia stato caricato fino all'(N–1)-esimo elemento.
L'algoritmo della produzione random potrebbe essere questo.Ciao, ciao
:hello:

Re: Estrazioni casuali
 

Alt, frena!
Chi t'ha detto che aspesi ha fregato anche me?

Certo: aspesi è un mago, un drago del calcolo combinatorio, un mefistofele del quiz

M'ha fregato (si fa per dire, eh!) già tante altre volte.
Ma questa volta ... non ho fatto in tempo a farmi fregare! :D

Io mi sono interessato a questo quiz quando ormai ... tu avevi già fatto il mattatore e aspesi aveva già dato la "sua" soluzione.
Sono intervenuto solo per dire che, prima che uno sapesse (o scoprisse da sé) che la probabilità è indipendente dal numero di allievi (maggiore o uguale a 4), poteva fare una simulazione terra terra, la più facile che si può.

Poi, siccome mi hai provocato col dirmi che è troppo laborioso produrre permutazioni casuali di 29 elementi, eccomi a completare [col precedente chilometrico 'post' che spiega pedissequamente :D come si possono produrre disposizioni casuali senza troppa laboriosità] quell'algoritmo di simulazione terra-terra che tu criticavi perché "controproducente" (secondo te) rispetto all'obiettivo di fare una simulazione il più lontana possibile da conoscenze specifiche di teoria della probabilitià.

Ciao ciao
--------------

Re: Estrazioni casuali
 

Questo è un po' più complicato (con la forza bruta, non saprei...:mmh:)

Un sacchetto contiene 90 biglietti, numerati da 1 a 90.
I 90 biglietti vengono pescati tutti con 50 estrazioni successive, senza restituzione (quindi, ogni estrazione può pescare uno o più biglietti, fino a 41).
Qual è la probabilità che l'ultima estrazione sia del solo numero 1?

E, in generale: qual è la probabilità che l'ultima estrazione sia solo del numero 1 se il sacchetto contiene N biglietti (numerati da 1 a N) e si eseguono K estrazioni fino ad esaurimento degli N biglietti?

:hello:

Re: Estrazioni casuali
 

Non capisco...

Chi decide quanti biglietti verranno estratti in una specifica estrazione?

Il caso?

L'unica condizione posta è che con la cinquantesima estrazione devono terminare i 90 biglietti?

:confused:

Re: Estrazioni casuali
 

Sì, si devono esaminare tutte le possibili partizioni, supposte equiprobabili.
L'unica condizione è che con le cinquanta estrazioni, terminano tutti i 90 biglietti.

:hello:

Re: Estrazioni casuali
 

Soluzione: 0.004952 fine

:hello:

Re: Estrazioni casuali
 

Non mi pare corretto (almeno, la soluzione con la formula che ho tirato fuori, è diversa di ben il 19%)

:hello:

Re: Estrazioni casuali
 

<%
Server.ScriptTimeOut= 60000 'Concede più secondi all'esecuzione del programma

Dim volte as integer=10000 'Totale del numero dei tentativi, da incrementare per una maggiore precisione
Dim v as integer

Dim b as integer=90 'Biglietti
Dim e as integer=50 'Estrazioni
Dim p(b-e) as integer 'Posizioni dei biglietti estratti (da 1 a E)


Dim n as integer
Dim no as integer 'Nell'ultima estrazione viene estratto più di un biglietto
Dim si as integer 'Nell'ultima estrazione viene estratto un solo biglietto
Dim TotNo as integer 'Totale dei no


b= b - e


for v=1 to volte
no=0

for n=1 to B
P(n)= int(RND * e) + 1
if P(n)= e then no=1
next
TotNo= TotNo + no
next



si=volte-Totno
response.write("si=" & si &"<br>")
response.write("si/volte=" & si/volte &"<br>")
response.write("(si/volte)/90=" & (si/volte)/90 &"<br>")
%>



Ho ragionato in questo modo:

Il quiz prevede che per ogni estrazione venga estratto almeno un biglietto.

Prendo quindi i miei 90 biglietti e ne metto 1 in ciascuna delle 50 estrazioni.

Me ne rimangono 40 (b-e).

Prendo una alla volta ciascuno di questi 40 biglietti, e li metto in modo casuale in una delle 50 estrazioni.

Vado a vedere cosa succede nella cinquantesima estrazione.
Se almeno uno di questi 40 biglietti è finito in questa posizione, ho sballato.
Il quiz vuole infatti che ci sia solo un biglietto in questa posizione, ed un biglietto ce l'avevo già messo all'inizio.

Ripeto questa operazione per un gran numero di volte tenendo conto del numero di volte che sballo(no) e delle volte che non sballo(si).

Il numero dei non-sballi (si) diviso il numero delle volte, mi da la probabilità che nell'ultima estrazione venga estratto un solo biglietto.

Divido questa probabilità per 90 ed ottengo la probabilità che in questa unica estrazione venga estratto un biglietto specifico dei 90, nel nostro caso il biglietto su cui c'è scritto un "1".

:mmh: Ho sbagliato qualcosa?

Re: Estrazioni casuali
 

Non lo so...:mmh:

Però, potresti fare questa prova (verificandone il risultato).

Supponi che i biglietti siano 10 e che le estrazioni siano 2.
I casi possibili sono (i due numeri indicano l'insieme dei biglietti delle due estrazioni):
1 - 9
2 - 8
3 - 7
4 - 6
5 - 5
6 - 4
7 - 3
8 - 2
9 - 1

Quindi, 9 partizioni totali e solo 1 con l'ultima estrazione costituita da un solo numero.

La probabilità in questo caso è quindi 1/9 moltiplicato per 1/10 perché il residuo deve essere un numero specifico (0,01111...)

:hello:

Re: Estrazioni casuali
 

Biglietti=10
Estrazioni=2

mi viene:
si/volte=0,0039016
(si/volte)/b=0,00039016

:confused:

Re: Estrazioni casuali
 

Hai toppato!!! :D

Le tue combinazioni non sono mica equiprobabili.

La combinazione (1 - 9) non ha le stesse probabilità della combinazione (5 - 5).

:)

PS
Scusa, ho letto solo ora "supposte equiprobabili".

Ma perchè equiprobabili?

Questa cosa mi era sfuggita, forse avresti dovuto spiegare meglio che il gioco dipendeva dall'arbitrio di chi lo gestisce, e non dal caso come avevo capito io. :(


Io ti avevo chiesto:

E tu hai risposto:


La combinazione:

41,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 ,1,1,1,1,1,1 ecc.

Per CASO non uscirà mai, se poi il gestore del gioco decide di farla uscire è un'altro discorso.

Re: Estrazioni casuali
 

Io non ho parlato di combinazioni, ma di partizioni.
Il problema chiede di calcolare le possibili partizioni di N in K gruppi e tra queste verificare quante lasciano l'ultimo biglietto isolato.

In pratica, si deve supporre di disporre gli N biglietti in fila. Per dividerli in K gruppi, si può disporre di un certo numero (K-1) di separatori negli spazi tra i biglietti (il numero degli spazi è N-1)

Es.:
N = 5
K = 3
1 2 3 | 4 | 5
1 | 2 3 4 | 5
1 | 2 | 3 4 5
1 2 | 3 4 | 5
1 2 | 3 | 4 5
1 | 2 3 | 4 5
le partizioni sono 6

:hello:

Re: Estrazioni casuali
 

Se ci sono due contenitori in cui devo mettere in modo casuale 10 palline, è molto più probabile che alla fine trovo (5-5) piuttosto che (9-1).

Se devo inserire un separatore tra 10 elementi in modo casuale allora le probabilità di (5-5) e (9-1) sono le stesse.

A me pare che da come era formulato il problema non fosse molto comprensibile che bisognasse usare il secondo metodo.

Ok, vuol dire che ho risolto un quiz diverso. :D

:hello:

Re: Estrazioni casuali
 

Supponiamo che io sia capace di contare tutti i casi possibili e quelli favorevoli. Essendo i casi possibili equiprobabili, la probabilità è il rapporto tra il numero di casi favorevoli ed il numero totale di casi possibili.
Vediamo prima se ho capito giusto il tuo quiz
Ho un insieme di N elementi.
Conto (o calcoo) in quanti modi è ripartibile in K parti (nessuna vuota),
Questo numero sia A.
Prendo una parte di un solo elemento ... e la metto da parte! :D
L'insieme mi viene di N – 1 elementi.
Conto (o calcolo) in quanti modi questo è ripartibile in K – 1 parti.
Questo numero sia B.
Per ciascuno di questi B modi posso pensare che sia stato svuotato l'insieme di N elementi in K parti di cui una di un solo elemento.
Quindi il problema è ridotto a trovare la formula
M = F(N, K)
dove N è la cardinalità dell'insieme, K un assegnato numero di parti disgiunte la cui unione è l'insieme dato ed M (funzione di N e di K) è il numero di modi in cui posso rompere l'insieme di N elementi in K parti disgiunte.
Dopo di che la richiesta probabilità è
p = F(N–1, K–1) / F( N, K).

Dopo ci penso.
Prima dimmi se ho capito giusto il da farsi (cioè triovare quella funzione, almeno per N = 90 e K = 50)
:mmh:
Non capisco perché solo 6
Perché lasci in fila gli elementi?
Supponiamo che sia N = 4 e K = 2
Tu faresti
1 | 2 3 4
1 2 | 3 4
1 2 3 | 4
Diresti di avere 3 casi, di cui 1 solo favorevole => p= 1/3
Due obiezioni:
a) La parte del solo elemento 1 può uscire per prima o per seconda (che per K = 2 vuol dire ultima), mentre tu imponi nei dati che esca sempre per ultima.
b) la partizione in due parti di due elementi ciascuna non è una sola. Di due parti da 2 elementi ciascuna sono anche queste:
1 3 | 2 4
1 4 | 2 3
E in due parti con una parte di 1 solo elemento e l'altra di 3 elementi ci sono anche queste partizioni
2 ! 1 3 4
3 | 1 2 4

Quindi io conterei 2 partizioni in più nel caso di due parti da 2 elementi ciascuna; e 2 in più nel caso di due parti di cui una di 1 solo elemento e l'altra di 3 elementi.
7 distinte partizioni in 2 parti
I modi di fare 2 parti non sono equiprobabili al cambio di cardinalità delle parti!
Vedi che le coppie di coppie sono 3 [ed infatti C(4, 2) = 6]
E le coppie di 1 elemento e una Terna sono invece 4 (ed infatti C(4, 1) = 4).
Comunue, se i casi (come li conto io) sono 7, è imposibile avere p =1/3
--------------
Se prima, nel dire come ho capito il quiz, ho detto giusto, ho un solo modo di fare 1 parte di 3 elementi; e quindi ho
p = F(3, 1)/ F(4, 2) = 1/7 :p

Se ho detto sbagliato ... la colpa è tua che ti sei espresso da cani! :D
---------------
Ciao ciao

Re: Estrazioni casuali
 

Ricapitolando, la formula per calcolare la probabilità che nell'ultimo gruppo di estrazioni si trovi un'unica estrazione è:

P= (k-1) / (n-1)

e che venga estratto un numero specifico è:

P= (k-1) / (n*(n-1))

P= (50-1) / (90*(90-1))

P= 49 / (90*89)

P= 0.00611

Questo però è vero solo se si considerano equiprobabili tutte le possibili partizioni degli n elementi.

Però se consideriamo "fisse" le partizioni, e le riempiamo in modo casuale, le possibili partizioni non sono equiprobabili.

Secondo questa "logica" la probabilità che nell'ultima estrazione ci sia un solo numero e che questo numero sia "1", è quella che avevo calcolato in precedenza:

P= 0.004952

:hello:

Re: Estrazioni casuali
 

:ok::ok:

:hello:

Re: Estrazioni casuali
 

Ottimo!

:mad:
Perché nelle partizioni gli elementi sono indistinguibili.
Supponiamo che sia N = 4 e K = 2
Tu faresti
1 | 2 3 4
1 2 | 3 4
1 2 3 | 4
Diresti di avere 3 casi, di cui 1 solo favorevole => p= 1/3

Avrei dovuto dire:
1 | 1 1 1
1 1 | 1 1
1 1 1 | 1


Si può distinguere fra "partizioni ordinate" e "partizioni non ordinate"

Nel caso di partizioni ordinate, il discorso è complesso.
http://mathworld.wolfram.com/PartitionFunctionP.html
Lasciamo perdere...

Invece, qui parliamo di partizioni non ordinate, dove ad esempio, esaminando un mazzo di carte, per le 13 carte spettanti ad uno dei quattro giocatori:
13, 0, 0, 0 tutte le carte di cuori
0, 13, 0, 0 tutte le carte di quadri
sono da considerarsi "mani" differenti.

Nel caso si volesse contare tutte le partizioni di un intero N, il totale delle partizioni possibili è 2^(N-1)
Es. N=4
..4
..3 + 1
..1 + 3
..2 + 2
..2 + 1 + 1
..1 + 2 + 1
..1 + 1 + 2
..1 + 1 + 1 + 1

Nel quiz:
1 1 1 1 1 1 1 ....... 90 volte
Devo mettere 49 barrette spaziatrici
Ogni arrangement dei 49 separatori corrisponde ad una partizione.
Le 49 barrette negli 89 spazi danno luogo a C(89,49) combinazioni diverse.
(N-1)!/((K-1)!*(N-K)!)
Per calcolare le partizioni favorevoli, cioè quelle che lasciano l'ultimo biglietto isolato, si può supporre di bloccare l'ultimo separatore nella posizione fra il penultimo e l'ultimo biglietto; basta quindi sistemare i rimanenti separatori (K-2) negli spazi rimanenti (N-2) tra gli altri biglietti
Le partizioni favorevoli risultano C(88,48)
(N-2)!/((K-2)!*(N-K)!)

Il rapporto fra i due valori:
49/89 (come ha già scritto Astromauh :ok:)
cioè:
(K-1)/(N-1)
indica la probabilità che l'ultima estrazione peschi un solo biglietto

Dal momento che tutti i biglietti hanno pari opportunità, per avere la probabilità che l'ultima estrazione peschi il solo numero 1 occorre dividere per N
49/(89*90)
e in generale:
1/N * (K-1)/(N-1)

:hello:

Re: Estrazioni casuali
 

Non mi hai convinto!
In un insieme tutti gli elementi sono distinti uno dal'altro.
Dato un insieme I di cardinalità N, una sua parte P di cardinalità M > 0 è una combinazione [delle C(N, M) possibili] di M elementi distinti su N.
Quelle che tu duci "parti ordinate" sono le M! disposizioni di M elementi ad M ad M (dette anche permutazioni) di quella unica combinazione. E qui non c'entrano un fico!
Equiprobabili sono fra loro le combinazioni, e quindi le partizioni dello stesso tipo, nelle quali, cioè, ci sono non solo lo stesso numero di parti, ma anche gli stessi tipi parti.
Supponiamo, per esempio, che un insieme di 23 elementi sia ripartito in 8 parti di cui 3 sono di 2 elementi, 4 sono di 3 elementi ed una è di 5 elementi. Se diciamo {1, 2, ..., 23} l'insieme, una partizione come quella che ho detto è:Dico che è dello stesso tipo ogni partizione ottenuta da questa permutando arbitrariamente i 23 elementi. Per esempio:Non conta l'ordine all'interno di ogni parte né l'ordine delle parti. Queste due partizioni sono distinte perché diverse sono le parti; ma sono equiprobabili perché sono tutte uniche nell'insieme di tutte le partizioni in 7 parti di cui 3 di 2 elementi, 4 di 3 elementi ed 1 di 5 elementi.
Quante sono le partizioni di questo tipo?
Permutando in tutti i modi i 23 elementi ne ricavo 23! con le parti nello stesso ordine: ma non conta l'ordine degli elementi dentro ogni parte né l'ordine delle parti. Divido allora per il fattoriale del numero di elementi di ogni parte e per il fattoriale del numero di parti. Quelle di questo tipo sono dunque:
T1 = (23!)/ {[(2!)^3]·[(3!)^4]·[(5!)^1]·8!} ≈ 5,153445297·10^11.

Un diverso tipo di partizione sempre in 8 parti dell'insieme di 23 elementi è quello con 4 parti da 2 elementi, 3 parti da 3 elementi ed una parte da 6 elementi. Una partizione di questo tipo è la seguente:Quante sono le partizioni di questo tipo? Ecco qua:
T2 = (23!)/{[(2!)^4]·[(3!)^3]·[(6!)^1]·8!} ≈ 2,576226485·10^11.

Secondo i tuoi modelli, il tipo A) ed il tipo B) sarebbero rispettivamente:[code]
A) | •• | •• | •• | ••• | ••• | ••• | ••• | ••••• |
B) | •• | •• | •• | •• | ••• | ••• | ••• | •••••• |
Ma il tipo A) ed il tipo B) non sono equiprobabili in quanto, sull'intero numero di partizioni dell'insieme in 8 parti, il numero di quelle di tipo B) è (esattamente) la metà del numero di quelle di tipo A).

Insomma: non ho ancora capito come fai tu a pesare i singoli tipi di partizione quando calcoli la loro probabilità!
-----
Ciao ciao
:hello:

Re: Estrazioni casuali
 

http://it.wikipedia.org/wiki/Partizione_di_un_intero

http://it.wikipedia.org/wiki/Partizi..._degli_insiemi)

Io intendo le partizioni come gruppi di elementi indipendentemente dal loro contenuto.
Guardo cioè all'oggetto (nel quiz = biglietto), senza interessarmi a quello che c'è scritto dentro.

Nel sacchetto hai 90 pezzetti di carta uguali (facciamo, per capirci, finta che siano tutti bianchi e senza nessun numero scritto.
Se accetti questo punto di vista, ti puoi rendere conto che gli esempi di partizione che hai fatto nel tuo messaggio precedente sono perfettamente identici (contengono ugual numero di elementi).

Lo scopo è determinare la probabilità di avere un solo biglietto nell'ultima estrazione (partizione). Che, secondo me, è (K-1)/(N-1)

:hello:

Re: Estrazioni casuali
 

3.972.999.029.388 è il numero dei modi di partizionare 200 elementi:D

Re: Estrazioni casuali
 

@ aspesi.
Ma, scusa un momento! Questo è il tuo quiz originale:
Ho evidenziato col grassetto due precisi dati del quiz.
Adesso te lo mostro modificato variando le due informazioni offerte dalle parole in grassetto.
Secondo te, le modifiche sono insignificanti? Il quiz resta lo stesso?
--------------
Stamattina, dopo aver letto qualcosa tramite i tuoi link, mi viene il sospetto che il quiz, come l'intendi tu, è in realtà quello modificato da il correttore :D

Ciao ciao
–––––––––––––

Re: Estrazioni casuali
 

:eek:
:confused:
:mmh:

Re: Estrazioni casuali
 

:mmh: Cosa indicherebbe questo numero?:mmh:

:hello:

Re: Estrazioni casuali
 

Sì, secondo me è lo stesso.
Logicamente, il risultato di quello che tu chiami "il correttore" dovrà essere diviso per N (per avere la probabilità che il biglietto rimasto per ultimo sia uno degli N stabilito prima delle estrazioni)

:hello:

Re: Estrazioni casuali
 

• p (7) = 15
• p (8) = 22
• p (9) = 30
• p (10) = 42
• p (100) = 190 569 292
• p (200) = 3.972.999.029.388
• p (1000) = 24.061.467.864.032.622.473.692.149.727.991 ≈ 2,4 × 10 31

Non l'avevo c'è anche la partizione di 1000.
Ciao

Re: Estrazioni casuali
 

Ho capito.
Tu hai riportato il numero di partizioni ordinate.
Io invece parlavo (e l'ho più volte ripetuto) di partizioni NON ordinate.

Es.:
P_ordinate 4:
4
3 + 1
2 + 2
1 + 1 + 2
1 + 1 + 1 + 1
In totale sono 5

P_NON_ordinate 4:
4
3 + 1
1 + 3
2 + 2
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
1 + 1 + 1 + 1
In totale = 8 (come avevo scritto = 2^(N-1))

:hello:

Re: Estrazioni casuali
 

Roulette

Esaminiamo uno a uno i numeri usciti in 100 colpi alla roulette.


Contiamo i numeri che in questo ciclo risultano assenti + quelli usciti 1 volta + quelli usciti 2 volte (A).
Sommiamo poi quelli usciti 3 o più volte (B).
Come si sa, i numeri della roulette sono 0 - 1 - 2 - .... - 35, 36; quindi, A+B = 37

Puntiamo 100 euro.
Se A>B hai vinto tu, se B>A ho vinto io.
Ci state?

:hello:

Re: Estrazioni casuali
 

NO

Re: Estrazioni casuali
 

Perché hai fatto i conti o perché non ti piacciono i giochi d'azzardo? :D

(Però, devi riconoscere che rispetto agli altri biscazzieri, sono abbastanza onesto...;))

Re: Estrazioni casuali
 

Già, perchè B è appena un po' più probabile di A, su 1000 partite mediamente:

• A vince 491 volte
• B vince 509 volte

:hello:

Re: Estrazioni casuali
 

Sia X_n = numero di sortite del numero n in 100 colpi

La scommessa conviene se P(X_n<3)>50%
P(X_n<3) = P(X_n=0) + P(X_n=1) + P(X_n=2)

Se chiamiamo p=36/37 la probabilità che un dato numero non esca in un determinato turno, si avrà, dato che sostanzialmente siamo di fronte ad uno schema di prove ripetute (C(100,.) sono le diverse combinazioni di turni nei quali può uscire il numero n)

P(X_0<3) = p^100 + C(100,1)*p^99*(1-p) + C(100,2)*p^98*(1-p)^2 =
= p^100 + 100*p^99*(1-p) + 4950*p^98*(1-p)^2 =~ 0.49

:hello: