Thread: The average number of tries

Hi


Well, I have a problem here I need help to solve. Probability theory is not my field.
If someone knows how to solve it or knows where I can find tools for it, please contact me or just reply this thread as you please.


Take the definition:

Let A_1,A_2,…, and A_k be elementary events with probability P_1,P_2,…,P_k, respectively.
We say t is an average number of tries to occur any desired event about A_1,A_2,…, and A_k iff t is the minimum number that the probability P(t,P_1,P_2,…,P_k) of the desired event happen in t tries is >=1-(1-(P))^(1/P), where P=min{P_1,P_2,…,P_k}.


Notes: 1-(1-x)^1/x is a decrescent function, so 1-(1-(1/P))^(P), where P=min{P_1,P_2,…,P_k}, is maximum.
1-(1-n)^1/x is a crescent function for any fixed value of n.


Given fixed values of P_1,P_2,…,P_k, one can calculate numerically the average time of any event, however, when these values aren´t fixed things may become more complicated when we try to stablish some general formula (or an lower and upper bound) for the average time t.


For example:
We can prove that the average number of tries to occur A_1 with probability P_1 is 1/P_1. (this is the trivial case that satisfies the definition above)
We can prove the average number of tries t to occur A_1 or A_2, respectively, with probability P_1 and P_2 is >=ln((1+(1-1/2^|P|)^(2^|P|)))/(ln((1-1/(2^|P|)))) (which is a lower bound) and =< 1/(P_1 + P_2) (which is a upper bound), where P=min{P_1,P_2}

Following that right spirit, I do the question:

What is the average number of tries (or an non trivial upper bound and non trivial lower bound) to occur the subsequence A_1,A_2,…, and A_k, in that right ordering and non necessarilly one next to another, each elementary event with probabilities P_1,P_2,…,P_k, respectively. Note that k, P_1,P_2,… and P_k are free variables.


The answer will likely come as t being limited by an upper and lower bound to the desired average number of tries, where these bounds are functions from (P,P´,k) to a natural number (where P=min{P_1,P_2,… and P_k} and P´=max{P_1,P_2,… and P_k}).
Obviously, trying to find the exact function that gives our average time could be herculean and worthless to what we desire. The result comes from a combination and the combination formulas change for different values of k.
Just a non trivial lower bound would be quite good.




Thank you very much.

Hey FelipeAbraham.

Have you come across order statistics (not just minimum and maximum, but general ranked distributions)?

Ranking - Wikipedia, the free encyclopedia

Order statistic - Wikipedia, the free encyclopedia

Thank you very much, chiro.

I don´t have a clue how to build a probability density function for this case.

In fact, I´m working with algorithmic probabilities. It follows the kraft´s tree rules. the probability of a program with size s happens is 1/(2^s). The space of all programs is countable but kraft´s tree gives us that the sum of all probabilities is =<1.

So even if we consider a continuous space of sizes s´s ranging inside [1,+infinity), where for size s the probability is 1/(2^s), we won´t get a uniform distribution. The probability density function won´t give us a gaussian. I believe first one need to define where is the uniform distribution in this problem.

Another problem I cannot solve is how to build a p.d.f. encompassing all cases of P_i´s and k´s.

I also guess I don´t have enough background to see how to blend ranking with this.


If you or someone could help me, I will very appreciate.

With the order statistics you can form a PDF for getting say a < b < c < d < ... < z using the formula.


If you know the underlying PDF for P(X = x) or P(X < x) then you can use this to get a PDF of the sandwiched values above.

Basically the extreme order statistics are the minimum and the maximum distribution of a value and the one above is a special case of a completely ordered set.

Basically the wiki link provides a formula to calculate it so you don't have to derive it, but if you have questions about using the order statistic then I'll do my best to answer them.

Just outline what your distribution is specifically if you need more help.

Hi, Chiro.

Sorry didn´t reply before, I was working on another subject for my thesis.

I would summarize the problem we have like this: "Estimate the average number of tries to occur the subsequence A_1,A_2,…, and A_k, in that right ordering and non necessarilly one next to another, in which each elementary event has probability P_1,P_2,…,P_k, respectively. Note that k, P_1,P_2,… and P_k are free variables"


Naively, the notion of average number of tries is the one that makes sense to say the average number of tries to occur an event A_1 with probability P_1 is 1/P_1. This is the trivial case I described in the first post.


About the distribution, we are using algorithmic probabilities as I said. Avoiding some concepts from this field the distribution of probabilities is in fact of this form: 1/(2^(n_1)), 1/(2^(n_2)), ..., 1/(2^(n_k)),...

The set {n_1, n_2, ..., n_k,...} is countable.

The sum of all 1/(2^(n_i))´s is always =<1 due to kraft´s inequality.

I'd recommend that you get the probability with the order statistic distribution and then invert the probability like you did for the one sample case.

In a proper random sample, this should be the expected number of times you would wait to get the said event.