Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I toss $n$ coins whose probabilities are dependent on each other in the following sense. At toss $i$ I know the probability of getting a head is at least $p_i-x_i$ and at most $p_i$ where I know both $p_i$ and $x_i$. They are dependent because the exact probability depends on the outcomes of the previous coin tosses. Can you get tail bounds on the number of heads you get just by considering $n$ independent coin tosses with probability $ p_i$ to get an upper bound and $p_i-x_i$ to get a lower bound?

To be more concrete, is this true for example?

$$\prod_{i=1}^n (p_i-x_i) \leq P(n \text{ heads in a row})\leq \prod_{i=1}^n p_i$$

share|cite|improve this question
what exactly is $x_i$? Is this the outcome of the previous toss? It sounds like you are trying to get a recurrence relation in which you at least need initial condition $p_0$. Also, your outcome of coin tosses is generally denoted 0 for heads and 1 for tails, thus you will always end up with a negative probability for every heads you toss. I'm not sure what you are going for here. Define what $x_i$ is a little better. – Eleven-Eleven Mar 31 '13 at 12:50
up vote 1 down vote accepted


You could think of each coin having a three-state outcome, with $P[\mathrm{Heads}]=p_i-x_i$, of $P[\mathrm{Tails}]=1-p_i$ and $P[\mathrm{Other}]=x_i$, where the Other event could be either with some distribution determined by your previous tosses.

Then your probability of all Heads is at least $\prod (p_i-x_i)$, and your probability of at least one Tails is at least $1-\prod p_i$, establishing your bounds.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.