Ho guardato una lezione del MIT su Skip List. Nel complesso, capisco il materiale, ma una cosa. Che cosè “ad alta probabilità”? Non lo capisco affatto. Ho visto gli dispense ma ancora non li ho ricevuti.
ha detto, “Levento $ E $ si verifica con alta probabilità (whp) se, per qualsiasi $ \ alpha \ geq1 $, cè una scelta appropriata di costanti per cui $ E $ si verifica con probabilità almeno $ 1 – O (1 / n ^ \ alpha) $ “.
Qualcosa di algoritmist.com ” non ha aiutato.
Che cosè $ \ alpha $ e cosè $ 1 – O (1 / n ^ \ alpha) $? Non capire questa cosa mi confonde sullanalisi del perché “Con alta probabilità, ogni ricerca in una lista da saltare $ n $ -elemento costa $ O (\ lg n) $”.
Commenti
- Nota che gli algoritmi randomizzati e probabilistici non sono la stessa cosa .
Risposta
Un evento accade con alta probabilità rispetto a un parametro $ n $ se accade con probabilità $ p_n $ e $ \ lim_ {n \ to \ infty} p_n = 1 $. Di solito il parametro $ n $ è chiaro dal contesto. In questo caso, ad esempio, è probabilmente il numero di elementi nellelenco.
La definizione di “con alta probabilità” nelle dispense è ancora più specifica, specificando quanto velocemente $ p_n $ dovrebbe convergere a $ 1 $: un evento accade con alta probabilità se accade con probabilità $ p_n \ geq C / n ^ \ alpha $ per alcuni $ C, \ alpha > 0 $. Ad esempio, se scegli un numero casuale da $ \ {0, \ ldots, n \} $, allora è diverso da zero con alta probabilità poiché la probabilità che sia diverso da zero è $ 1-1 / (n + 1) \ geq 1-1 / n $ (quindi in questo caso $ C = \ alpha = 1 $).
Commenti
- Il criterio del limite è chiamato anche " quasi sicuramente ". Ho visto " alta probabilità " utilizzata principalmente quando ci si riferisce a probabilità che si avvicinano a una con tasso esponenziale.
- Quando ho vedi " whp " di solito è sinonimo di " quasi sicuramente ", e quando lo uso (senza definirlo) questo è sempre il significato a cui mi riferisco. Ma più in generale " whp " potrebbe significare avvicinarsi a 1, avvicinarsi a 1 in modo polinomiale veloce o avvicinarsi a 1 in modo esponenziale. Se lo usi in uno qualsiasi di questi ultimi, assicurati di definirlo esplicitamente.
- Davvero, ' d chiamare $ p_n = 1 – \ frac { 1} {\ log ^ * n} $ " con alta probabilità "? 😉 Ma sì: per sicurezza, definisci in ogni caso cosa intendi nel tuo contesto.
- Che cosè un riferimento standard (ad es. Libri di testo) che definisce formalmente WHP? Ho provato a scrivere un articolo su WHP in wikipedia en.wikipedia.org/wiki/With_high_probability ma è stato suggerito per leliminazione perché non ci sono fonti, quindi sono alla ricerca di fonti ..
- Puoi controllare la complessità standard e gli algoritmi dei libri di testo. Ma anche se trovi un riferimento, ' è solo quel particolare ' uso del termine da parte di un libro di testo. ' è probabilmente meglio definirla esplicitamente come definizione comune senza alcuna " prova ".