A Brain Burner

[firemeboy]

At least, it burns my brain.

Ok, so I have a little puzzle, that is fairly math heavy. In the interest of full disclosure, this is not just an academic exercise, I'm actually trying to build the drill and practice program that I describe below. So if you feel like you don't want to provide me free consulting, please ignore the puzzle.

Imagine you are building a drill and practice program. You want to present quetsions to students who will attempt to answer them. If they get the question right, then you want to present that question to them less frequently (because they likely know the content). If they get the question wrong, you want to present the question to them more frequently (so they can practice it).

So, imagine 100 questions. You give each question a value of 0. This represents that we don't know if the person knows the answer. If the person gets the answer wrong, the value decreases by 1. If they get it right, it goes up by one.

The new vaule of the question determines how frequently this question is going to come up again in the future. For each of these values, we're going to assign a different sided die. We'll do it based on the table below.

10 | 2
9 | 3
8 | 4
7 | 5
6 | 6
5 | 7
4 | 8
3 | 9
2 | 10
1 | 11
0 | 12
-1 | 13
-2 | 14
-3 | 15
-4 | 16
-5 | 17
-6 | 18
-7 | 19
-8 | 20
-9 | 21
-10 | 22

So a question with a value of 0 will roll a 12 sided die. A question with a value of negative 10 will roll a 22 sided die. And a question with a value of 9 will roll a 3 sided die.

The computer will then look at all the values and present the question with the highest die roll. So if the negative ten rolls a 22, by default it will be the question presented because none of the other numbers can roll higher.

This will make it so that higher values will be presented less, and lower values will be presented more, because it will be difficult for the lower values to beat the higher values.

However, the problem lies in the fact that in order for a question with a value of 10 to be presented, it would have to roll a 2, and all the other numbers would have to roll a one. This is a very small chance. But consider the following.

10 | 102
9 | 103
8 | 104
7 | 105
6 | 106
5 | 107
4 | 108
3 | 109
2 | 110
1 | 111
0 | 112
-1 | 113
-2 | 114
-3 | 115
-4 | 116
-5 | 117
-6 | 118
-7 | 119
-8 | 120
-9 | 121
-10 | 122

Now you have a much better chance for a 10+ to be presented. If it rolled a 102, it has a much higher chance of being presented than in the previous example.

So my question and puzzle is this. How do you determine the chance of a particular question being presented? What is the percentage in the first case of a 10 being presented, and what is the percentage in the second case? If you increased it to 1002, 1003, 1004, etc. What would the percentage be then?

I'm going to play around with this, but I'm sure some of the math wizards here can do it quicker.
_________________
The difference between myself and a madman is that I am not mad.

[JDTAY]

Chowder: "IT BURRRRRRRRRRRRRRRRRNS!!!!!!!!!!!!"
_________________
Prohibit nothing. Disclose everything.

[Zag]

You haven't said what you'll do in the event of ties, but if the lower score wins, then the first one is easy to calculate, it is 1 / 21!. After that, it gets harder. Of course, the scores for the questions won't be evenly distributed from 10 to -10 like that.

But I wouldn't use that algorithm at all, if I were you. I'd start all questions at a weighting of, say, 4. A correct answer and that question's weighting goes down one, an incorrect answer and it goes up one. For each question you ask, choose a question based on the weighted chances. Here's an example with 4 questions (abcd), and starting at a weighting of 2.

a=2, b=2, c=2, d=2. Total is 8, so roll a d8. Let's say you get a 5, subtract until you get zero or negative, which happens at c, so ask question c. Let's say he gets it right, so now you have

a=2, b=2, c=1, d=2. Total is 7, so roll a d7. You roll 2, so ask question a. He gets it wrong, so you have

a=3, b=2, c=1, d=2. Total is 8, so roll a d8. You roll a 7, question d, and he gets it wrong

a=3, b=2, c=1, d=3. Total is 9, so roll a d9. You roll a 6, question c again. He gets it right again,

a=3, b=2, c=0, d=3. So now you'll never ask question c again. By getting it right N times (or, right N times more than he got it wrong), he gets to eliminate it from coming up.

It's very easy to implement with a computer, and I think it provides closer to the behavior you want. At least, it is a lot more predictable.

[Thok]

Run a Monte Carlo simulation to get some heuristics. That will be more efficient then trying to come up with an exact formula.

[firemeboy]

Zag, very interesting.

Here is a question. One of the things I want to do is if a question is answered incorrectly, I want to present it again fairly soon. That way the person can see the answer again before they forget. If there were, say, 500 questions, your method wouldn't necessarily do this, would it? There is a slightly higher chance, but when you have that many questions, you'd still be looking at a long shot.

Of course you could just work it so that if they got it wrong, it's placed 10 spots down in the queue.
I'm going to have to think about this some more.
_________________
The difference between myself and a madman is that I am not mad.

[firemeboy]

OK, this is bizarre. I copied my text above to put it in another forum (a family site we use). The smiley face was replaced with a sentence. It said, "Revenge most foul!"

What is up with that?
_________________
The difference between myself and a madman is that I am not mad.

[Antrax]

Zag's method is what I would have done as well. If you want to add the complication that within n turns you'd ask a question that was gotten wrong again, you'd need to hold a side list of "questions to be asked soon" and every round select from it (and not with the usual die method) with probability 1 / n (if you just want something that works) or 1 / 2 ⁿ (if you want the expected number of turns to really be n).
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[firemeboy]

Ok, so going with Zag's method, is there a way to optimize the chances of you getting the question again? For example, if you had a 100 questions, and you gave each a value of 1. Then if a person got it wrong let's say it goes up in value to by 4 points (so it's now at 5). So now it has roughly a 1 in 20 chance of being picked again, right? And if we increase it to 10 if answered wrong again, it now has a 1 in 10 chance.

I would assume it would also be quicker for the computer, because instead of generating 100 numbers (a die roll for each question), you're just generating one. Although with computing speeds, maybe it doesn't make that much of a difference.

I like it! Thanks, guys.
_________________
The difference between myself and a madman is that I am not mad.

[PuzzleScot]

I'm not sure if it will help if you change your tack a little.
Instead of ensuring that every selection produces a question, be prepared to throw away selections.

eg, if every question was rated for the individual between -10 and 10 (based on previous performance), then your procedure would select a random question, and a random value between -10 and 10.
Then, if the 2nd value was lower than the individual's rating for that question use it. Otherwise, pick a new random question and value. Repeat until a question is chosen.

I had to use this technique to put dots randomly in geographic polygons once upon a time. We selected random points in the enclosing rectangle until the point was inside the polygon, and repeated until we had all the points we needed. We threw a lot away, but it didn't matter in the end.

Hope that helps.

[Jack_Ian]

[lostdummy]

I think that instead of starting with some algorithm and then trying to see how it will impact your practice program, you should first define how you want practice program to behave, and then it is easy to correctly set up probabilities of questions.

This problem can be split in two separate problems:
1) how positive/negative answers should influence frequency of each question ("how you want practice program to behave")
2) how to select question when those frequencies are given

For #1, imagine that each of 100 questions start at 1.00% chance to be asked (so equal chance). How high are you willing to let that chance be if question is answered wrongly many times? Up to 100% (so only that question is asked)? Or more probably set some limit and say question should never be asked more than 10% chance (about 10x more often than "normal" questions) ?

Same goes for bottom limit - allow questions that are answered correctly many times to be never asked ( "never" is similar to those 1/21! chance)? Or also set limit and say that it still should be asked for example at least once in 1000 (so ~0.1%)?

Once you set limits (if any), then you need to decide how fast/slow you want positive/negative answers to approach those limits. For example, should limit of 10% be reached in about 10 wrong questions? And do you want it to approach with constant speed or faster at start and slower after many wrong questions?

All of above questions are not related to how to program it but to how you want your practice to behave.

Lets assume limits given above (max around 10%, min 0.1% ) and that we want to approach those limits in about 10 wrong/right questions. That would be 'definition' for #1.

'Solution' for #1, given above definition, could have many forms, but here is easy one:
- average value AVG=1/N (N=num of questions, so 1% here)
- give each question starting weight VALUE= AVG
- step for change is: if VALUE<AVG then CHG= (AVG-Lower Limit)/10 else CHG=(Upper Limit - AVG)/10
- if correct answer, VALUE -= CHG else VALUE +=CHG
- if VALUE>UpperLimit then Value=UpperLimit ; if VALUE<LowerLimit then VALUE=LowerLimit

Above will set approximations of probabilities that each question will appear . It is 'approximation' since it will not add up to 1.00 for all questions - which was also easy to do but it is not needed since any positive 'weight' value is enough, as long as it has property that 2x value means 2x frequency of showing up.


Second part of problem (#2) should now just need to take list of N (=100) "weight values" from above, toss random number and select one. This also can be done in many ways, and probably easiest one is:
- sum all weight values (SUM=sum(value[1..N])
- x= random(SUM)
- n=1; while ( value[n] < x) do { x=x - value[n]; n++; }
- ask question number 'n'

Above will ensure that if question A has 2x weight value than question B, it will be asked 2x more frequently. That eliminate need to calculate probabilities if you know weights. Probability of each question to be asked is "weight value"/SUM

After wrong/right answer change weight value[n] according to #1 approach, and repeat.