Problema di efficenza e probabilità combinata

[Lexander]

Billy scava in miniera variando il tempo che impiega ad ogni scavo per risparmiare tempo secondo la sequenza ciclica di 48secondi, 20secondi e poi 20secondi. Scavando 70 volte avrebbe una probabilità del 100% di trovare un diamante e, ad ogni scavo fallito la probabilità di trovarlo aumenta dell' 1.43% (100%/70). Solo lo scavo da 48 secondi permette di raccogliere il diamante, quelli da 20 secondi no.

In realtà, Billy, quando ha iniziato a scavare in quella miniera per la prima volta, aveva il 100% di probabilità di trovare un diamante al primo scavo. Ogni volta che trovava un diamante, il numero di scavi che doveva eseguire per avere una probabilità di riuscita del 100% era n+1 in cui cui "n" è il numero di diamanti già trovati [esempio: nel primo scavo del secondo tentativo, aveva il 50% mentre al secondo il 100% di trovare un diamante, quindi ad ogni scavo aumenta secondo la forumla (100%/n+1)]

billy ripete sistematicamente la sequenza 48,20,20,48,20,20,48,20,20..... e così via.

La domanda è: sarebbe più efficente la sequenza 48+20+20, 48+20+20+20 oppure altre con meno o più scavi da 20 secondi?
-Vorrei conoscere la sequenza migliore da usare per tutti gli scavi dal primo diamante al 70esimo ponendo che Billy debba cominciare a scavare un'altra miniera a cui si applicano le stesse regole sopra citate.
-Dato che sarebbe più efficente cambiare la sequenza man mano che i diamanti vengono trovati aggiungendo alla sequenza, dopo un certo numero di diamanti, uno scavo da 20 secondi (48+20+20+20), vorrei sapere quando aggiungere (dopo quanti diamanti trovati) lo scavo da 20 secondi alla sequenza.

-per efficente intendo 'arrivare al diamante in meno tempo possibile'.

Ho cercato di contestualizzare il problema, abbiate pietà.
Ho provato a pensare alla media in secondi di ogni sequenza e alla variazione di percentuale in ognuna, ma non riesco a dimostrare numericamente quale sarebbe quella più efficente.

Ho modificato la richiesta

ghira

[ghira]

Perché Billy comincina con uno scavo da 48 secondi? Non sarebbe meglio cominciare con alcuni scavi da 20 secondi e poi passare a quelli da 48 quando la probabilità di successo è più alta?

Vuoi la soluzione solo per $n=69$ o ogni $n$? Dovendolo fare per un solo valore, lo farei numericamente.

[Lexander]

Perché Billy comincina con uno scavo da 48 secondi? Non sarebbe meglio cominciare con alcuni scavi da 20 secondi e poi passare a quelli da 48 quando la probabilità di successo è più alta?

Vuoi la soluzione solo per $n=69$ o ogni $n$? Dovendolo fare per un solo valore, lo farei numericamente.

-Vorrei che la sequenza in questione sia composta da un massimo di 6 scavi

[ghira]

-Vorrei che la sequenza in questione sia composta da un massimo di 6 scavi

Perché?

Faccio 20,20,20,20,20,48, non trovo niente, vado a casa?

[Lexander]

-Vorrei che la sequenza in questione sia composta da un massimo di 6 scavi

Perché?

Faccio 20,20,20,20,20,48, non trovo niente, vado a casa?

la sequenza è ciclica

[ghira]

Ho provato a farlo numericamente. Ho ignorato la parte sul ciclo di lunghezza 6.

Siamo in stato $i$ se abbiamo una probabilità di $i/n$ di trovare il diamante adesso.

Sia $v(i)$ il costo medio continuando da $i$. $v(n)=48$, ovviamente. Altrimenti possiamo scegliere fra
$20+v(i+1)$ e $48\frac{i}{n}+frac{n-i}{n}(48+v(i+1))$. Scegliamo il minore di questi. Cominciamo in stato $1$.

Ecco un tentativo:

Codice:

#!/usr/bin/perl

$n=shift;
$v[$n]=48;
$a[$n]=48;
sub min {
my $a=shift;
my $b=shift;
if ($a<$b) {
return $a;
} else {
return $b;
}
}

sub v {
my $i=shift;

if (defined $v[$i]) {
return $v[$i];
}
my $v0=20+v($i+1);
my $v1=$i/$n*48+($n-$i)/$n*(48+v($i+1));
#print "$i $v0 $v1\n";
if ($v0<$v1) {
$a[$i]=20;
} else {
$a[$i]=48;
}
$v[$i]=min($v0,$v1);
return $v[$i];
}

$i=$n;
while ($i>0) {
$v=v($i);
print "$i $v $a[$i]\n";
$i--;
}


Per $n=70$ dice:

70 48 48
69 48.6857142857143 48
68 49.3910204081633 48
67 50.1167580174927 48
66 50.8638147438567 48
65 51.6331296245612 48
64 52.4256968249624 48
63 53.2425696824962 48
62 54.084865106571 48
61 54.9537683708448 48
60 55.8505383386921 48
59 56.7765131675088 48
58 57.7331165430015 48
57 58.7218645008431 48
56 59.7443729001686 48
55 60.8023656214647 48
54 61.8976835706205 48
53 63.0322945814364 48
52 64.2083043209408 48
51 65.4279683156839 48
50 66.6937052330526 48
49 68.0081115699158 48
48 69.3739779219735 48
47 70.7943070315056 48
46 72.2723338393733 48
45 73.8115477997762 48
44 75.4157177542026 48
43 77.0889197051924 48
42 78.835567882077 48
41 80.6604495511462 48
40 82.5687640933483 48
39 84.5661669556257 48
38 86.6588191797146 48
37 88.8534433275798 48
36 91.1573867591102 48
35 93.5786933795551 48
34 96.1261851666283 48
33 98.8095550166464 48
32 101.639472723322 48
31 104.627706231565 48
30 107.787260703752 48
29 111.132538412197 48
28 114.679523047318 48
27 118.445992729067 48
26 122.451766858271 48
25 126.718992980317 48
24 131.272481101351 48
23 136.140094453764 48
22 141.353207625438 48
21 146.947245337807 48
20 152.962318098433 48
19 159.443974614573 48
18 166.444095427968 48
17 174.02195796689 48
16 182.245510431601 48
15 191.192901053401 48
14 200.954320842721 48
13 211.634232686215 48
12 223.354078511436 48
11 236.255580459639 48
10 250.504783251119 48
9 266.297025404546 48
8 283.863079644027 48
7 303.476771679624 48
6 323.476771679624 20
5 343.476771679624 20
4 363.476771679624 20
3 383.476771679624 20
2 403.476771679624 20
1 423.476771679624 20

Sembra ovvio che la nostra azione debba essere "20" per valori bassi di $i$ e poi "48" oltre una certa soglia.

Mi aspettavo più "20". Magari vedo se ho toppato e/o provo a farlo analiticamente. Qualche volta non è realistico ma in questo caso forse si può fare e poter paragonare i risultati con la soluzione numerica è utile.

[Lexander]

devo essere sincero, non ho capito tutto ciò che hai scritto (neanche i dati), ma guardando i dati credo tu non abbia capito il problema.
billy ripete come un computer una sequenza composta da uno scavo da 48 secondi, uno da 20 secondi e poi un ultimo da 20 secondi. Chiedo quando dovrebbe cambiare la sequenza ipotizzando che parta da un'altra miniera fino a trovare 70 diamanti, non solo lo step del settantesimo diamante
Se mi sbaglio, fammelo presente.

Poi, che linguaggio di programmazione è quello?
un'altra domanda come si chiama quella cosa che hai fatto con quel codice?

[ghira]

Chiedo quando dovrebbe cambiare la sequenza ipotizzando che parta da un'altra miniera fino a trovare 70 diamanti, non solo lo step del settantesimo diamante

Ho capito. Ho mostrato cosa fare per il 70esimo. Se vuoi partire dal primo esegui il programma 70 volte per valori di $n$ diversi e sommi i risultati. O cambi il programma in modo che ecc. ecc. Insomma.

Il comportamento di Billy è irragionevole. Potrebbe fare uno scavo da 20 secondi quando è già a 100% di probabilità di trovare un diamante. Palesemente assurdo. E partire con uno scavo da 48 secondi è spesso sbagliato. ("Spesso" vuol dire quando $n>1$)

Se calcoli la soluzione migliore puoi eventualmente paragonare i tempi per il comportamento sbagliato di Billy se vuoi.

Il linguaggio di programmazione è il Perl.

Ho usato la programmazione dinamica stocastica, https://en.wikipedia.org/wiki/Stochasti ... rogramming

Almeno, spero. È una cosa che faccio assai raramente.

[ghira]

Sto scrivendo un programma per cacolare il tempo medio per il tuo metodo, anche quando Billy fa 2 scavi di 20 secondi inutilmente perché ha 100% di probabilità di trovare un diamante. Qui basta una catena di Markov, ma il mio programma per adesso sta dicendo cose chiaramente impossibili quindi i risultati non sono pronti.

[ghira]

Per il tuo metodo ottengo un tempo medio di 23310.0016686485 secondi per trovare 70 diamanti.

Per il mio ottengo un tempo medio di 19869.2388921697 secondi.

Per il tuo ho usato una catena di Markov.

Gli stati sono $(n,i,j)$ dove $n$ è il numero del diamante che stiamo cercando, $i$ è la probabilità (in $n$-esimi) di trovare il prossimo diamante se facciamo uno scavo di 48 secondi adesso, e $j$ è la posizione nel ciclo degli scavi. $j$ può essere 0, 1 o 2. Quando è 0 facciamo uno scavo da 48 secondi.

Cominciamo in stato $(1,1,0)$. Vogliamo sapere quanto costa mediamente arrivare in uno degli stati $(71,1,0)$, $(71,1,1)$ o $(71,1,2)$. I costi partendo da questi tre stati sono 0.

Per gli altri stati:

$c(n,i,j)=48+c(n+1,1,j+1 mod 3)$ se $i=n$ e $j=0$
$c(n,i,j)=48+\frac{i}{n}c(n+1,1,j+1 mod 3)+\frac{n-i}{i}c(n,i+1,j+1 mod 3)$ se $j=0$ e $i<n$
$c(n,i,j)=20+c(n,i,j+1 mod 3)$ se $j=1$ o $2$ e $i=n$
$c(n,i,j)=20+c(n,i+1,j+1 mod 3)$ se $j=1$ o $2$ e $i<n$.

Puoi confermare che tutto questo è quello che intendi?

Il mio programma per calcolare il costo $c(1,1,0)$ è:

Codice:

#!/usr/bin/perl
#ciclo 48,20,20
#stato iniziale 1,1,0
$c[71][1][0]=0;
$c[71][1][1]=0;
$c[71][1][2]=0;
#prossimo diamante, prob in n-esimi, ciclo, old/new
#esattamente tot iterazioni - tutti i fallimenti possibili
while (1) {
for ($n=70;$n>0;$n--) {
#print $n."\n";
for ($i=$n;$i>0;$i--) {
#print $i."\n";
for $j (0..2) {
#print $j."\n";
$j2=($j+1)%3;
if ($j==0) {
if ($i==$n) {
$c[$n][$i][$j]=48+$c[$n+1][1][$j2];
} else {
$c[$n][$i][$j]=48+$i/$n*$c[$n+1][1][$j2]+($n-$i)/$n*$c[$n][$i+1][$j2];
}

} else {
if ($i<$n) {
$i2=$i+1;
} else {
$i2=$i;
}
$c[$n][$i][$j]=20+$c[$n][$i2][$j2];
}
#print "$n $i $j $c[$n][$i][$j]\n";
}
}
}

print $c[1][1][0]."\n";
}

e dice

23310.0016686485

ma il programma potrebbe non essere perfetto.

Almeno il metodo che sto provando ad usare è quello che descrivi tu? Billy fa scavi inutili da 20 secondi quando potrebbe trovare il diamante con probabilità 1 facendo uno scavo da 48 secondi?

Per il mio metodo eseguo il mio programma (visto qualche messaggio fa) per tutti i valori di $n$ da 1 a 70:
(modificato per stampare solo il costo partendo dallo stato $1$ per ogni diamante).

Codice:

#!/usr/bin/perl

for (1..70) {
system "perl diamanti.p $_";
}

e sommo i risultati.

Codice:

#!/usr/bin/perl

while (<>) {
chomp;
$t+=$_;
}
print "$t\n";

Codice:

~/matematicamente$ ./diamantiloop.p | ./summer.p

19869.2388921697

Se vuoi che Billy faccia altre cose puoi modificare il programma o scriverne uno migliore ovviamente. La mia soluzione dovrebbe essere quella col tempo medio più basso.