Algorithm to get probability of reaching a goal

Question

Okay, I'm gonna be as detailed as possible here.

Imagine the user goes through a set of 'options' he can choose. Every time he chooses, he get, say, 4 different options. There are many more options that can appear in those 4 'slots'. Each of those has a certain definite and known probability of appearing. Not all options are equally probable to appear, and some options require others to have already been selected previously - in a complex interdependence tree. (this I have already defined)

When the user chooses one of the 4, he is presented another choice of 4 options. The pool of options is defined again and can depend on what the user has chosen previously.

Among all possible 'options' that can ever appear, there are a certain select few which are special, call them KEY options.

When the program starts, the user is presented the first 4 options. For every one of those 4, the program needs to compute the total probability that the user will 'achieve' all the KEY options in a period of (variable) N choices.

e.g. if there are 4 options altogether the probability of achieving any one of them is exactly 1 since all of them appear right at the beginning.

If anyone can advise me as to what logic i should start with, I'd be very grateful. I was thinking of counting all possible choice sequences, and counting the ones resulting in KEY options being chosen within N 'steps', but the problem is the probability is not uniform for all of them to appear, and also the pool of options changes as the user chooses and accumulates his options.

I'm having difficulty implementing the well defined probabilities and dependencies of the options into an algorithm that can give sensible total probability. So the user knows each time which of the 4 puts him in the best position to eventually acquire the KEY options.

Any ideas?

EDIT: here's an example:

say there are 7 options in the pool. option1, ..., option7 option7 requires option6; option6 requires option4 and option5; option1 thru 5 dont require anything and can appear immediately, with respective probabilities option1.p, ..., option5.p; the KEY option is, say, option7; user gets 4 randomly (but weighted) chosen options among 1-5, and the program needs to say something like: "if you choose (first), you have ##% chance of getting option7 in at most N tries." analogous for the other 3 options.

naturally, for some low N it is impossible to get option7, and for some large N it is certain. N can be chosen but is fixed.

EDIT: So, the point here is NOT the user chooses randomly. Point is - the program suggests which option to choose, as to maximize the probability that eventually, after N steps, the user will be offered all key options.

For the above example; say we choose N = 4. so the program needs to tell us which of the first 4 options that appeared (any 4 among option1-5), which one, when chosen, yields the best chance of obtaining option7. since for option7 you need option6, and for that you need option4 and option5, it is clear that you MUST select either option4 or option5 on the first set of choices. one of them is certain to appear, of course. Let's say we get this for the first choice {option3, option5, option2, option4}. The program then says: if you chose option3, you'll never get option7 in 4 steps. p = 0; if you chose option5, you might get option7, p=....; ... option2, p = 0; ... option4, p = ...;

Whatever we choose, for the next 4 options, the p's are re calculated. Clearly, if we chose option3 or option2, every further choice has exactly 0 probability of getting us to option7. But for option4 and option5, p > 0;

Is it clearer now? I don't know how to getting these probabilities p.

Answer 1

This sounds like a moderately fiddly Markov chain type problem. Create a node for every state; a state has no history, and is just dependent on the possible paths out of it (each weighted with some probability). You put a probability on each node, the chance that the user is in that state, so, for the first step, there will be a 1 his starting node, 0 everywhere else. Then, according to which nodes are adjacent and the chances of getting to them, you iterate to the next step by updating the probabilities on each vertex. So, you can calculate easily which states the user could land on in, say, 15 steps, and the associated probabilities. If you are interested in asymptotic behaviour (what would happen if he could play forever), you make a big pile of linear simultaneous equations and just solve them directly or using some tricks if your tree or graph has a neat form. You often end up with cyclical solutions, where the user could get stuck in a loop, and so on.

Answer 2

If you think the user selects the options at random, and he is always presented the same distribution of options at a node, you model this as a random walk on a graph. There was a recent nice post on calculating terminating probabilities of a particular random walks on the mathematica blog.