Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number of Possible Outcomes w/ Restrictions (Coin Toss)

  1. Aug 8, 2013 #1
    Hey guys,

    I am currently working on a personal project, and I've run into a dilemma.

    I need to determine the total number of possible outcomes for a coin toss type system, ie two possible outcomes each generation, for N generations. The problem however comes in with the restrictions I have to deal with, these being.

    1) Outcome one cannot occur x more times than outcome two.
    2) Outcome two cannot occur y more times than outcome one.

    Any "branch" of the probability tree that contains such a case needs to be eliminated.

    I have no idea how to solve this, besides some form of excel type model with each branch manually calculated, but that looks terribly daunting when the system is allowed to run for many generations.

    Any help would be appreciated.
  2. jcsd
  3. Aug 8, 2013 #2


    User Avatar
    2017 Award

    Staff: Mentor

    You can sum over the number of "heads", this needs ~N calculations for N coin tosses. Some of those summands are forbidden by your rules, so you can set them to zero.
  4. Aug 8, 2013 #3
    Apologies as I'm pretty uneducated in this field and I'm not quite sure what you mean.

    Would you mind elaborating?
  5. Aug 8, 2013 #4


    User Avatar
    2017 Award

    Staff: Mentor

    Let's consider an example: x=y=2, N=60, and I'll call the two outcomes "heads" and "tails".

    How many heads can we have?
    0? No, we have 60 times tails, that is more than twice the number of heads.
    1? No.
    20? Still not possible, tails would occur twice as often as heads.
    21? That is possible
    39? Possible
    40? Not possible, heads would occur twice as often as tails.
    60? Not possible.

    How many ways do we have to get 21 heads in 60 trials? -> Binomial coefficients
    How many ways do we have to get 22 heads in 60 trials? -> Binomial coefficients
    Sum all, and you get the total number.

    For large N, it might be useful to find some approximations to simplify the calculation.
  6. Aug 8, 2013 #5

    Stephen Tashi

    User Avatar
    Science Advisor

    I haven't worked on the problem, but the result may follow from manipulating the Chebyshev inequality. Try using the fact that the variance of N tosses of a fair coin has mean N/2 and variance N(p)(1-p) and that you can establish some inequality between 1/x^2 and e^(-x).
  7. Aug 8, 2013 #6

    Thank you very much, that makes a lot of sense.

    I have a further query.

    Say if we were to repeat the experiment, flipping coins, and each time we add one or subtract one from a start value, of say a 100, dependent on whether we get heads or tails. Is there a way to find the amount of possible outcomes wherein which the value never reached 200 or 0, throughout the entire process, not just at the end of the run of N coin tosses.

    Thanks again.
  8. Aug 8, 2013 #7


    User Avatar
    2017 Award

    Staff: Mentor

    That is a discrete random walk with absorption.
    I found this paper, your problem looks like a special case of that.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook