3

We are given two coins: A and B with probability of obtaining heads being: $\alpha$ and $\beta$ respectively. The following sampling rule is used for i=1,2,...: If the $i^{\text{th}}$ toss results in heads, stick to the same coin for the $(i+1)^{\text{th}}$ toss, while if the $i^{\text{th}}$ toss results in tails, switch to the other coin for the $(i+1)^{\text{th}}$ toss. For the first toss choose A or B randomly.
a) What is the probability of obtaining heads at the $(i+1)^{\text{th}}$ toss (call that $p_{i+1}$) as a function of obtaining heads at the $i^{\text{th}}$ toss ($p_i$)?
b) What is the probability of obtaining heads as the number of tosses go to infinity:$lim_{i\to\infty} p_i$ ?
Progress so far: Define a Markov chain with four states indicating the coin and the outcome during the $i^{\text{th}}$ toss : $\{A_H, A_T, B_H, B_T\}$ with the following transition matrix $P$
\begin{bmatrix} \alpha & 1-\alpha & 0 & 0 \\ 0 & 0 & \beta & 1-\beta \\ 0 & 0 & \beta & 1-\beta \\ \alpha & 1-\alpha & 0 & 0 \\ \end{bmatrix} I expect a first step analysis can be done to connect $p_i$ to $p_{i+1}$, but I can't quite get it yet.
EDIT: Alternatively, part b) can be solved by finding the stationary distribution of the Markov Chain. This can be written as follows
$\mathbf{\pi} = \begin{bmatrix} \frac{\alpha(1-\beta)}{2-(\alpha+\beta)} &\frac{(1-\alpha)(1-\beta)}{2-(\alpha+\beta)} & \frac{(1-\alpha)(1-\beta)}{2-(\alpha+\beta)} & \frac{(1-\alpha)\beta}{2-(\alpha+\beta)} \end{bmatrix} $
The probability of heads as $i$ goes to infinity can be obtained by adding the first and fourth element. Also, interestingly $\pi_{A_T}=\pi_{B_T}$. I don't think that helps with part a) though

Final Answer: I know the final answer will have the following form:
$ p_{i+1}=(\alpha + \beta-1)p_i + (\alpha + \beta -2 \alpha \beta)$
$p_i =(\alpha+\beta1-1)^{i-1}(p_1-\frac{\alpha + \beta -2 \alpha \beta}{2-(\alpha+\beta)})+\frac{\alpha + \beta -2 \alpha \beta}{2-(\alpha+\beta)}$
$lim_{i\to\infty} p_i = \frac{\alpha + \beta -2 \alpha \beta}{2-(\alpha+\beta)}$

selz
  • 33
  • Are you wedded to the approach? To me, it seems much more natural to first compute the (limiting) probability that the $i^{th}$ coin tossed is $A$. that gets you your $p_{\infty}$ fairly quickly. – lulu Mar 14 '16 at 17:31
  • Thank you ! Already did that to solve b), here's the vector of stationary distributions $ \mathbf{r} = \begin{bmatrix} \frac{\alpha(1-\beta)}{2-(\alpha+\beta)}& \frac{(1-\alpha)(1-\beta)}{2-(\alpha+\beta)} & \frac{(1-\alpha)(1-\beta)}{2-(\alpha+\beta)} & \frac{(1-\alpha) \beta}{2-(\alpha+\beta)} \end{bmatrix} $ . Interestingly, $\pi_{A_t}=\pi_{B_T}$ and b) can be solved by adding the first and last elements of the vector. I think it doesn't help with part a) though. – selz Mar 14 '16 at 18:10
  • Sorry I messed the comment up. Anyway this indeed solves part b). I edited the question accordingly. Thanks ! – selz Mar 14 '16 at 18:24
  • Can't read your comment (for whatever reason, it isn't compiling correctly on my computer). Are you saying that in the limit there is an equal chance that a given toss has $A$ or $B$? But that isn't so...if, say, $A$ is fair but $B$ can only throw $H$ then in the end you are sure to have $B$. I see $A_{\infty}=\frac {1-\beta}{2-(\alpha+\beta)}$ as the limiting probability that you have $A$. But perhaps you were saying something different. – lulu Mar 14 '16 at 18:25
  • Ah, now I see your edit. Makes sense. Funny, I don't see a natural way to get $p_i$ even recursively. – lulu Mar 14 '16 at 18:30

1 Answers1

1

Ok, here's how to do part a. (Note: I still don't like it much)

Let $p_i$ denote the probability of getting $H$ on the $i^{th}$ toss. Let $A_i$ denote the probability that you are dealing with coin $A$ on the $i^{th}$ toss.

Note: starting from the $(i-1)^{st}$ toss there are four ways to get $H$ on the $i^{th}$. (starting with either $A$ or $B$ you get $HH,TH$). A little algebra then yields:

$$p_i=A_{i-1}\left(\alpha^2+(1-\alpha)\beta\right)+\beta^2+(1-\beta)\alpha$$

But it is easy to see that $$p_{i-1}=A_{i-1}\alpha+(1-A_{i-1})\beta\implies A_{i-1}=\frac {p_{i-1}-\beta}{\alpha-\beta}$$ (the case $\alpha =\beta$ is trivial) Plugging this expression for $A_{i-1}$ into the expression for $p_i$ (and manipulating the resulting mess) yields the desired result.

lulu
  • 70,402
  • Ha ! yeah that indeed solves it. I went into a wild goose chase trying to solve it as a M.C with rewards and taking expectations but I couldn't get anywhere. Anyways thank you very much I'll redo it thoroughly but I get the idea – selz Mar 14 '16 at 20:05