## 5186Re: [hackers-il] Algorithm for randomly choosing a question

Expand Messages
• Jul 6, 2012

I want the application to be able to select any question randomly, but
with different weights, so that:
- A question the user never saw has weight of (say) 0.5.
- A question the user answered wrongly has weight of 1 (i.e. such a
question is twice more likely to be presented than a question never
seen).
- A question the user answered correctly has weight of 0.005 (i.e. it is
100 times less likely to be seen again than a question never seen
before).

A brute force approach is as follows (actual probabilities may differ
from the given weights, due to the finite probability of choosing the
same i again; I am ignoring this complication for now).

1. Select a number randomly from range [1,N], call it i.
2. If the user answered question i wrongly, it is chosen.
3. If the user never saw question i, select randomly real x from range
[0,1].
If x <= 0.5, i is chosen.
Otherwise, go to 1.
real x from range [0,1].
If x <= 0.005, i is chosen.
Otherwise, go to 1.

My wish is to have an algorithm which requires only bounded number of
computations of random numbers (i.e. no loop) to accomplish the above.
Assume that N is large, so keeping lists of questions in memory is ruled
out.

You don't have to keep a list of questions, just a list of numbers where each number represent a question.
A question you want to appear twice as much as any other, put it twice in the list.
For a question you want to appear 100 times less then any other, use the algorithm you suggested.

--
Ori Idan

• Show all 7 messages in this topic