Ottimizzare la scelta

[kobeilprofeta]

E' un problema credo noto.

Il tuo scopo è trovare il legnetto più lungo e tenerlo. Ci sono 100 legni in tutto e tu non hai idea delle lunghezze che possono avere, ad esempio uno può essere lungo 100 metri e un altro 2 cm; l'unica cosa che sai è che non ci sono due bastoni lunghi uguali.
Ti viene presentato un bastone alla volta e tu hai due possibilità: scartarlo (e in tal caso la decisione è definitiva, nel senso che non potrai più tornare indietro a sceglierlo) o tenerlo (e in tal caso il gioco finisce lì con quel bastone). Se hai scelto il bastone più lungo vinci, altrimenti perdi.
Supponi di avere memoria "infinita", cioè appeni vedi un nuovo bastone sai se è o no più lungo dei precedenti che hai già visto.

Che strategia devi adottare per massimizzare la probabilità di trovare il bastone più lungo?


esempi:

Se decido di tenere il primo ho $1/100$ di prob che sia il più lungo.
Se decido di guardarli tutti sarò costretto a prendere l'ultimo, e quindi ancora $1/100$.

Esempio con tre bastoni (1: il più lungo, 3: il più corto)
le possibili combinazioni sono
a 1 2 3
b 1 3 2
c 2 1 3
d 2 3 1
e 3 1 2
f 3 2 1
Se prendo il primo vinco 2 su 6, $1/3$.
Se scarto il primo e guardo il secondo vinco nei casi c,d,e , cioè $1/2$.

[axpgn]

"kobeilprofeta":Esempi:

Esempio con tre bastoni (1: il più lungo, 3: il più corto)
le possibili combinazioni sono
a 1 2 3
b 1 3 2
c 2 1 3
d 2 3 1
e 3 1 2
f 3 2 1
Se prendo il primo vinco 2 su 6, $1/3$.
Se scarto il primo e guardo il secondo vinco nei casi c,d,e , cioè $1/2$.

L'ultimo ragionamento non mi pare corretto ... io la vedo così ... se scarti il primo hai $1/3$ di probabilità di perdere, negli altri quattro casi il $d$ lo scarti (perché sai che è più corto del primo) quindi devi decidere sugli altri tre, se lo tieni vinci in due casi ($c$, $e$) su tre; quindi moltiplicando $2/3$ (la probabilità che ti è andata bene al primo colpo) per $2/3$ (la probabilità che ti vada bene tenendo il secondo) avresti una probabilità complessiva di $4/9$ maggiore dell'$1/3$ iniziale.
Io proverei su questa strada ...

Cordialmente, Alex

[kobeilprofeta]

se ne scarto zero (quindi tengo il primo) vinco in a,b.

se scarto il primo: in a,b perdo chiaramente. in c,e vinco perchè ne trovo uno subito piú lungo. in f perdo perchè il 2 lo vedo piú lungo del 3 ma in realtà non è il migliore. in d vinco perchè il secondo non lo prendo (infatti 3 è piú corto di due) e vado a prendere il terzo che è effettivamente vincente

[axpgn]

Provo a spiegarlo in altro modo ...

Se accetto il primo legno ho una possibilità su tre di vincere, se lo scarto e vado avanti ho una possibilità su tre di perdere (e quindi due su tre di vincere).
Al secondo legno, nella metà dei casi NON devo scegliere perché mi limiterò a scartare, negli altri tre casi se accetto ho due probabilità su tre di vincere.
Riassumendo, se accetto il secondo bastone ho quattro possibilità su nove di scegliere quello più lungo.

Per me, questa è la strategia migliore ...

[orsoulx]

Con $ n $ legnetti, la semplice strategia: scelgo, fra i successivi, il primo che superi in lunghezza il più lungo che ho osservato fra i primi $ x $; porta ad una probabilità di vittoria che, pur diminuendo al crescere di $ n $, tende a $ 1/e $; a patto di utilizzare $ x=|__ n/e +0.5 __| $, valore che rende massima tale probabilità. Non è vero: il valore che rende massima la probabilità o è $ |__ n/e __| $ o è $ |__ n/e__|+1 $, ma scegliere fra i due non è così banale .

Ciao
B.

[kobeilprofeta]

@orsoulx
se riesci posta il procedimento

[orsoulx]

"kobeilprofeta":se riesci posta il procedimento

Sì, capo!

Con la strategia già descritta: osserviamo x legnetti e poi prendiamo, se esiste, il primo che abbia una lunghezza maggiore del più lungo che abbiamo visto; otteniamo il legnetto $ L $ di maggior lunghezza sse. il più lungo fra quelli che ci vengono presentati prima è uno dei primi $ x $. Se $ t+1 $ è la posizione di $ L $, la probabilità di ottenerlo è allora $ p(x)= x/n \sum_{t=x}^{n-1} 1/t $. Modificato per correggere l'estremo inferiore della sommatoria in cui avevo scritto un "+1" di troppo.
Approssimando la nostra distribuzione discreta con una continua nell'intervallo [0,1] abbiamo $ p(x)=x\int_x^1 dt/t =-xlnx $, che ha il massimo in $ M(1/e;1/e) $.
Tra l'altro mi sono accorto di aver scritto una muccata: nel caso discreto il miglior valore di $ x $ è sicuramente o l'approssimazione per difetto di $ n/e $ o quella per eccesso, ma non è affatto detto che sia l'arrotondamento di questo valore.
Vado a correggere.

Ciao
B.

[kobeilprofeta]

orsoulx

[orsoulx]

@kobell
Avevo dimenticato di aggiustare l'estremo inferiore della sommatoria: deve iniziare col valore $ 1/x $, che moltiplicato per $ x $ corrisponde alla certezza di beccare il bastoncino più lungo se questo è il primo dopo quelli osservati. .
Ciao
B.

[kobeilprofeta]

"kobeilprofeta":orsoulx