The average number of sequences of programs.

Hi.

This thread is related with another one I already posted:

http://mathhelpforum.com/advanced-st...tml#post773654

And Chiro helped me.

Now I have another problem to solve.

Given a space of algorithmic probabilities - see the previous thread - one can calculate the probability of a arbitrary sequence of programs. It came from multiplying each probability of each program.

Well, given that probability P of a sequence of programs, we can say that the average number of sequences one must try to happen the desired sequence above is 1/P.

Now the problems come.

**I would like to know how many tries one should expect to happen this desired sequence.**

Note that each T tries gives us a T size sequence of programs. In T tries one should expect to get a certain amount of possible (likely) sequences of programs. The problem is to estimate this amount. Making the usual exponentiation ("number of possible programs")^T won´t work. The number of programs are infinite. However, the sum of all probabilities of each program is 1 due to kraft´s inequality.

Solved this estimation, it is easy make it equal to 1/P and find the minimum T that satisfy this equation. Note that average number of tries is different from average number of sequences.

Thanks.

Re: The average number of sequences of programs.

Hey FelipeAbraham.

Hint: Consider the inverse of a probability where probability of event = p and inverse = 1/p.

Remember that one interpretation of a probability is #Times_Event_Happens/#Total_Number_Of_Trials = N_p/N_total where N_total is total number of events and N_p is number times events event p happened.

If you invert this you get #Total_Events/#Events_for_p which means that you get the number of times an event happens within some period.

If you expect all events to be random from the distribution, then 1/p will tell you the expected number of trials you need to wait before that event actually happens. The lower the probability, the longer you have to wait on average and that should make intuitive sense. If p = 1, 1/p = 1 and if p=1/30, then 1/p = 30.