Irakli Koiava

Reservoir Sampling         მაგალითად გვაქვს ამოცანა. გვსურს n ელემენტიან მიმდევრობაში (x 0 , x 1 , ... x n)  ერთი ელემენტის შერჩევა შემთხვევითად, თანაბარი განაწილებით. როდესაც n-ის მნიშვნელობა ცნობილია ეს ამოცანა არის უმარტივესი. ჩვენ უბრალოდ შევარჩევთ ინდექსს j-ს 0-დან და n-მდე დიაპაზონში თანაბრად რაც ცალსახად მოგვცემს x j -ს ელემენტს მიმდევრობაში, რომლის შერჩევის ალბათობაც  იქნება 1/n. როგორ შეიძლება ეს ამოცანა ამოვხსნათ თუკი მიმდევრობაში ელემენტების რაოდენობა ცნობილი არ არის, თუკი ელემენტებს ვკითხულობთ როგორც ნაკადს და დროის ერთ მონაკვეთში მხოლოდ ერთ ელემენტზე გვაქვს წვდომა? ასეთ შემთხვევაში ცხადია მარტივი მეთოდი უკვე აღარ მუშაობს და პრობლემა სხვანაირად უნდა გადაიჭრას.          რეზერვუარის შერჩევა არის მეთოდი, რომელიც საშუალებას გვაძლებს შევარჩიოთ ელემენტი n ზომის ელემენტების ნაკადში სადაც n-ის მნიშვნელობა ცნობილი არ არის. მაგალითად შესაძლოა, რომ n ელემენტი მეხსიერებაში ერთად არ გვეტევა და ამისათვის ელემენტებს ნელ-ნელა ვტვირთავთ მეხსიერებაში ან უბრალოდ დროის მოცემული მომენტისათვის