Number of Possible Outcomes w/ Restrictions (Coin Toss)

[ProbQ]

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.

 

[mfb]

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.

 

[ProbQ]

Apologies as I'm pretty uneducated in this field and I'm not quite sure what you mean.

Would you mind elaborating?

 

[mfb]

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.

 

[Stephen Tashi]

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).

 

[ProbQ]

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.

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.

 

[mfb]

That is a discrete random walk with absorption.
I found this paper, your problem looks like a special case of that.