In general, computer simulation involving random numbers (lets say to simulate a fair deck of playing cards so $1$ thru $52$) runs fast if you only pick a few cards. However, as you pick more and more, the algorithm slows because of "collisions", meaning, the random number generator will very likely repeat a card and then we will have to try again to resolve it. As we get closer and closer to exhausting the deck (like we picked $45$ cards and still want more), the algorithm "crawls" (by comparison to when we pick only a few cards) since there are mostly collisions as the available cards dwindle (using the flag method of already seen cards).
So I am wondering what a good way is to alleviate this problem for simulation of games where we need a variable # of random numbers from about $25$% to $90$% of all possible. Perhaps we can just concentrate on $50$% for the sake of comparing speeds. For example, to pick $26$ of $52$ cards randomly using the flag method, we would need on average $1.38 * 26 = 36$ random numbers which is very reasonable and quite fast but can we do better as far as speed?
Also, would it be fair to say that if we choose a random number (let's say from $1$ to $52$ representing the cards in a deck), and we get a collision, that just picking the next higher not yet chosen card still maintains good randomness because each previously chosen card has an equal chance of a collision? For example, if we choose $2, 37, 51, 15, 44, 37$, we would then make the 2nd $37$ a $38$ because $38$ has not been chosen yet.
No comments:
Post a Comment