Results 1 to 6 of 6
Like Tree1Thanks
  • 1 Post By chiro

Math Help - The average number of tries

  1. #1
    Newbie
    Joined
    Apr 2012
    From
    Rio de Janeiro, Brazil
    Posts
    13

    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 arent 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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,607
    Thanks
    591

    Re: The average number of tries

    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2012
    From
    Rio de Janeiro, Brazil
    Posts
    13

    Re: The average number of tries

    Thank you very much, chiro.

    I dont have a clue how to build a probability density function for this case.

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

    So even if we consider a continuous space of sizes ss ranging inside [1,+infinity), where for size s the probability is 1/(2^s), we wont get a uniform distribution. The probability density function wont 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_is and ks.

    I also guess I dont have enough background to see how to blend ranking with this.


    If you or someone could help me, I will very appreciate.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,607
    Thanks
    591

    Re: The average number of tries

    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.
    Thanks from FelipeAbraham
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2012
    From
    Rio de Janeiro, Brazil
    Posts
    13

    Re: The average number of tries

    Hi, Chiro.

    Sorry didnt 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 krafts inequality.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,607
    Thanks
    591

    Re: The average number of tries

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Average number, combinatorics
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 30th 2012, 02:17 AM
  2. Average employee number
    Posted in the Algebra Forum
    Replies: 5
    Last Post: August 5th 2010, 09:28 AM
  3. 'Average' number
    Posted in the Statistics Forum
    Replies: 1
    Last Post: July 29th 2010, 01:38 PM
  4. Average Value of a Number
    Posted in the Calculus Forum
    Replies: 3
    Last Post: May 6th 2010, 08:05 AM
  5. Average number of divisors of a certain type
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 18th 2009, 10:17 AM

Search Tags


/mathhelpforum @mathhelpforum