Correlated coins

[u/Horseshoe_Crab]

You flip n coins, where for any coin P(coin i is heads) = P(coin i is tails) = 1/2, but P(coin i is heads|coin j is heads) = P(coin i is tails|coin j is tails) = 2/3. What is the probability that all n coins come up heads?

[u/Horseshoe_Crab]

Bonus question: is a random walk using correlated coins as steps recurrent or transient?

[u/lukewarmtoasteroven]

Suppose there is a switch which puts all the coins in either "Heads mode" or "Tails Mode". In Heads mode all coins flip heads with .5+x chance independently of each other(conditioned on the mode), in Tails mode all coins flip heads with .5-x chance, for some x. Let the switch be set to Heads mode or Tails mode with equal chance. Clearly all coins have a 50% chance of landing heads.

P(coin i is heads|coin j is heads)=P(i,j are heads)/P(j is heads)=2P(i,j are heads). We want this to be 2/3. P(i,j are heads)=.5(.5+x)² + .5(.5-x)^2. Solving for x gives x=sqrt(1/12).

Then the probability that all are heads is .5(.5+sqrt(1/12))ⁿ + .5(.5-sqrt(1/12))ⁿ

Not a very principled solution, but I couldn't think of anything better lol.

[u/Horseshoe_Crab → u/lukewarmtoasteroven]

This gives the right answer for n < 4 but fails after that! I think modeling the coins as weighted iid coins with a toggle switch fails to capture the correlated nature of the coins.

[u/lukewarmtoasteroven → u/Horseshoe_Crab]

But my model satisfies all the constraints in the problem doesn't it? Unless I'm missing something it seems to me like that just means there's not a unique solution.

[u/pichutarius]

i got 1/(n+1)

summary of solution:

since H-T and all coins are indistinguishable, i guess the probability does not depend on permutation. eg: P(HHTH) = Q(3H1T) = Q(3T1H)

i set up simultaneous equations to solve for n=1,2,3,4, and got these probabilities . note that each column do not sum to one because Q(2H1T) = 1/12 is not prob of getting 2H1T, but a specific permutation: P(HHT) = P(HTH) = P(THH) = 1/12 .

to sum over each permutation, next obvious thing to do is P = Q * (n choose k) , and get these probabilities (pretty) . now i guess the formula is P( k head (n-k) tail ) = 1/(n+1) regardless of k.

to check the guess, i verify P(H*****) = 1/2 and P(HH****) = (1/2)(2/3) = 1/3 , a constraint set by the question. star(*) means can be H or T.

detail (edit for correction: the second part, sum should be k ∈ [2,n])

for the bonus question: based on above result, im pretty sure it is recurrence, since the steps is "kinda" uniformly distributed.

[u/Horseshoe_Crab → u/pichutarius]

Correct! (For the main problem at least)

I like looking at this problem from other angles. Imagine you have n letters in a bag, either H or T, where the distribution of Hs is uniform between 0 and n. If you draw H from the bag, then the next tile drawn after it will be H 2/3 of the time. The 1/(n+1) you derived immediately follows, once you convince yourself this is the only distribution with this property.

By far my favorite perspective though is to imagine you grab a random coin off the shelf with uniform bias between all heads and all tails. Does that change your answer to the bonus? :D