Randbenaderingen

Randbenaderingen verwijzen naar methoden die bij het oplossen van problemen gebruik maken van toeval. Ze omvatten zowel algoritmen die willekeurige keuzes maken tijdens de uitvoering als benaderingen die de verwachting of probabilistische eigenschappen van een probleem analyseren. In de literatuur worden randbenaderingen vaak onderverdeeld in gerandomiseerde algoritmen en probabilistische analyse van deterministische algoritmen. Gerandomiseerde algoritmen kunnen worden ingedeeld als Las Vegas-methoden (zij geven altijd een correcte oplossing, maar de uitvoeringstijd is random) en Monte Carlo-methoden (de uitvoeringstijd is meestal begrensd, maar de uitkomst kan met een bepaalde kans fout zijn).

Toepassingsgebieden omvatten berekeningen met grote datasets, numerieke simulaties, statistiek, machine learning en computergraphics. Voorbeelden zijn Monte Carlo-integratie, randomisierte lineaire algebra zoals randomized SVD en random projections (Johnson-Lindenstrauss lemmas) om grote matrices te comprimeren, en stochastic gradient descent voor stochastic optimization. Randbenaderingen worden ook gebruikt bij schattingen via sampling en bij approximate query processing.

Voordelen van randbenaderingen zijn onder meer schaalbaarheid naar grote datasets, eenvoudige implementatie en robuustheid bij ruis en incomplete informatie. Nadelen zijn onder meer toegenomen variatie in resultaten, mogelijke gebrek aan reproducibiliteit zonder vaste random seeds, en dat garanties vaak probabilistisch van aard zijn (verwachte fout of kans op fout).

Samengevat bieden randbenaderingen een krachtig alternatief of aanvulling op deterministische methoden, vooral wanneer snelheid en schaalbaarheid cruciaal zijn en probabilistische garanties acceptabel zijn.