将N个球放入容积为K的袋子中,如何保证每个球仍然在袋子中的概率相同?
1.处理1-K号球时,直接放进袋子里;
2.处理第i号球时,以K/i的概率决定是否将第i号球放进袋子里。如果不决定将第i号球放进袋子里,直接扔掉第i号球;如果决定将第i号球放进袋子里,那么就从袋子里的K个球中随机选择一个扔掉,放入第i号球;
3.处理第i+1号球时,重复步骤1和2.