Barre di caricamento e probabilità

È nato completamente a caso, da una domanda innocente di un amico mentre eravamo in una chat vocale su Discord. Supponiamo di dover cercare un singolo elemento in un array non ordinato composto da $n$ elementi. Vorremmo che l’utente abbia una sorta di barra di caricamento in modo che, con alta probabilità, la barra di caricamento sia piena esattamente quando la ricerca è completata. Che tipo di relazione dovrebbe esistere tra la barra di caricamento e la ricerca?

L’intuizione che alcuni potrebbero avere è che la maggior parte delle volte l’elemento sarà stato individuato prima di iterare su tutto l’array, quindi la barra dovrebbe avvicinarsi al 100% ben prima della conclusione della ricerca. Ma è vero? Proviamo a scomodare le probabilità.

Iniziamo con qualche considerazione. Supponendo che l’elemento abbia la stessa probabilità di trovarsi in qualsiasi posizione dell’array, la probabilità che sia il primo elemento è $P(E^1_n) = \frac{1}{n}$. Quindi, la probabilità contraria (e cioè che il primo elemento non sia quello che cerchiamo) è $P(\neg E^1_n) = 1 - P(E^1_n) = 1 - \frac{1}{n} = \frac{n - 1}{n}$. Se siamo arrivati a considerare il secondo elemento della lista, dobbiamo assumere abbiamo fatto un buco nell’acqua con il primo. Quindi la probabilità per il secondo elemento diventa $P(E^2_n) = P(E^1_{n - 1} \wedge \neg E^1_n) = P(E^1_{n - 1} | \neg E^1_n) \cdot P(\neg E^1_n) = \frac{1}{n - 1} \cdot \frac{n - 1}{n} = \frac{1}{n}$. In altre parole, siamo tornati alla probabilità iniziale.

Ogni volta che incrementiamo l’indice dell’elemento che stiamo analizzando, abbiamo una probabilità di $\frac{1}{n}$ di trovare quello che stiamo cercando. Questo suggerisce che la barra di caricamento dovrebbe essere incrementata di $\frac{1}{n}$ ogni volta che incrementiamo l’indice dell’elemento che stiamo analizzando, creando una relazione 1:1 tra la ricerca e la barra di caricamento.

Sebbene ciò sembri corretto dal punto di vista matematico, potrebbe non essere la risposta giusta per l’esperienza utente. Parlando di questo problema con un collega, mi è stato suggerito che la barra di caricamento dovrebbe aumentare rapidamente all’inizio e rallentare pian piano, fino al suo completamento. Questo perché l’utente avrà l’impressione che l’operazione sia piuttosto veloce grazie al feedback immediato. Anche nello sfortunato caso in cui l’elemento si trovi alla fine, la barra di caricamento sembrerà già quasi piena, e per la fallacia dei costi irrecuperabili, l’utente sarà predisposto ad aspettare comunque che la ricerca si completi. Un interessante mix di matematica e psicologia.

Sommario