Any probability experts or users of markov chains

[vampsthevampyre]

Afternoon All,

Just been watching a video regarding probability of coin flips. The initial set up I can understand, how to create a state chart (see attached spreadsheet) of the chances of 7 heads in a row. But after this the video stated that to simulate the flipping a coin 200 times. the video states that if you raise the initial state matrix to the power of 200 you will then get the second matrix which shows the probability of getting 7 heads in a row raises to 0.54 or 54%.

I've tried searching for how to recreate this in excel but the maths goes way beyond my knowledge and the solutions also show markov chains and that really makes my head hurt. Is this possible to do in excel? and if so how.

Also how easy is it to change the number of flips and introduce a biased coin (i.e. 67% tails, 23% heads)

Any help would be appreciated

Regards

Ian

roulette.xlsx
	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V
3																	After 200 flips
4						Next State											Next State
5			0	1	2	3	4	5	6	7				0	1	2	3	4	5	6	7
6		0	0.5	0.5	0	0	0	0	0	0			0	0.23	0.11	0.06	0.03	0.01	0.01	0.004	0.54
7		1	0.5	0	0.5	0	0	0	0	0			1	0.23	0.11	0.06	0.03	0.01	0.01	0.004	0.55
8		2	0.5	0	0	0.5	0	0	0	0			2	0.22	0.11	0.06	0.03	0.01	0.01	0.004	0.55
9	Current	3	0.5	0	0	0	0.5	0	0	0		Current	3	0.22	0.11	0.05	0.03	0.01	0.01	0.003	0.57
10	State	4	0.5	0	0	0	0	0.5	0	0		State	4	0.2	0.1	0.05	0.03	0.01	0.01	0.003	0.6
11		5	0.5	0	0	0	0	0	0.5	0			5	0.17	0.09	0.04	0.02	0.01	0.01	0.003	0.66
12		6	0.5	0	0	0	0	0	0	0.5			6	0.11	0.06	0.03	0.02	0.01	0.003	0.002	0.77
13		7	0.5	0	0	0	0	0	0	1			7	0	0	0	0	0	0	0	1
Sheet10

 

[6StringJazzer]

It might be helpful to give us a link to the video so we understand what context you are in.

the video states that if you raise the initial state matrix to the power of 200 you will then get the second matrix which shows the probability of getting 7 heads in a row raises to 0.54 or 54%.

I had to read this a couple of times before I realized what you meant. If you flip a coin 7 times, the chances of all heads is 1/2^7 = 1/128 = 0.0078125. But you are talking about if you flip a coin 200 times, what is the probability that somewhere in those 200 flips is a run of 7 heads?

A coin flip is a Markov "chain" because the probability of the next event is not dependent on any past events. That is, the chances of getting heads on a coin flip is 50%; if you flip 6 straight heads, the chances of heads on the next flip is still 50%. (See also Gambler's Fallacy.)

I don't understand how you are trying to solve any of this in the Excel sheet you showed in your post. Determining the chances of 7 heads in 7 flips is analytical (as I showed above) and you do not need to enumerate the "states". You can to that understand how the probability works, but the problem is pretty simple.

To determine the chances of a run of 7 heads in 200 flips is more complicated. But I still don't see what you are trying to do on the Excel sheet. To model 200 coin flips exhaustively you would have to generate 2^200 = 1.61 x 10^60 possible sequences. I don't know if there is an analytical way to do this, that is, an expression you can solve. The way I would do this is a Monte Carlo simulation in VBA.

Once you have the method, it's not a big deal to change the fairness of the coin. It's still a binary variable.

 

[vampsthevampyre]

 

[JGordon11]

You need to raise the first matrix to the power of the number of flips. The answer will occur in the last column of the first row of the resulting matrix.
By the way the last entry in the first column of your starting matrix should be 0, not .5)

There's not a native way to raise a matrix to power that I know of, other than using MMULT n - 1 times. So that is not reasonable to do for large n by using a formula. A recursive lambda could be used but VBA is more straight-forward and isn't affected by the stack limit as the lambda would be for large number of flips.

Here is VBA function MatrixPower which can raise a square matrix to a power.

Function MatrixPower(m, n As Long)
    Dim i As Long, s, c
    s = m
    c = m
    For i = 2 To n
        s = Application.MMult(c, s)
    Next
    MatrixPower = s
End Function

So raising the first matrix to the 200th power yeilds the second one. The answer appears in the last cell of the first row.

Book2
	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R
1	0.5	0.5	0	0	0	0	0	0		0.229066	0.114995	0.05773	0.028981	0.014549	0.007304	0.003667	0.543708
2	0.5	0	0.5	0	0	0	0	0		0.227226	0.114071	0.057266	0.028748	0.014432	0.007245	0.003637	0.547375
3	0.5	0	0	0.5	0	0	0	0		0.223559	0.11223	0.056342	0.028284	0.014199	0.007128	0.003579	0.554678
4	0.5	0	0	0	0.5	0	0	0		0.216255	0.108564	0.054501	0.02736	0.013735	0.006895	0.003462	0.569228
5	0.5	0	0	0	0	0.5	0	0		0.201706	0.10126	0.050834	0.02552	0.012811	0.006431	0.003229	0.598209
6	0.5	0	0	0	0	0	0.5	0		0.172725	0.086711	0.04353	0.021853	0.010971	0.005507	0.002765	0.655938
7	0.5	0	0	0	0	0	0	0.5		0.114995	0.05773	0.028981	0.014549	0.007304	0.003667	0.001841	0.770934
8	0	0	0	0	0	0	0	1		0	0	0	0	0	0	0	1
9
10
11	Answer:	0.543708
12
Sheet2

Cell Formulas
Range	Formula
J1:Q8	J1	=MatrixPower(A1:H8,200)
B11	B11	=INDEX(J1#,1,8)
Dynamic array formulas.

To change the probability you would change all the .5 's in the first matrix to the new probability of heads.
To change the number of flips just change the power used in the MatrixPower function.
To change the number of heads in a row you are interested in, you would adjust the size of the first matrix maintaining the same pattern. If the run is 7 the matrix wil be 8x8, or in general if the run of interest is n the matrix will be (n+1)X(n+1).

 

[JGordon11]

Correction: To change the probability you would change all the .5 's in the first matrix (Column 2 and beyond) to the new probability of heads. Change all the .5 's in column 1 to (1 - the probability of heads).

Here's a Lambda that does all that using a call to the vba MatrixPower function.

LAMBDA(flips,probability,runlength, LET(m,TEXT(SEQUENCE(runlength, runlength,0,0) +SEQUENCE(runlength,,100,100) + SEQUENCE(1,runlength),"0000"), mm, IF(LEFT(m,2)=RIGHT(m,2),probability,0), mmm, HSTACK(SEQUENCE(runlength,,1-probability,0), mm), mmmm, VSTACK(mmm, HSTACK(SEQUENCE(1,runlength,0,0),1)), INDEX(MatrixPower(mmmm, flips),1,runlength+1)))

 

[Eric W]

There are online calculators for this kind of thing:

Coin Toss Streak Calculator

With this coin toss streak calculator, you will discover a very interesting problem in probability related to consecutive heads appearing in coin flips.

www.omnicalculator.com

 

[drpdrpdrp]

Correction: To change the probability you would change all the .5 's in the first matrix (Column 2 and beyond) to the new probability of heads. Change all the .5 's in column 1 to (1 - the probability of heads).

Here's a Lambda that does all that using a call to the vba MatrixPower function.

LAMBDA(flips,probability,runlength, LET(m,TEXT(SEQUENCE(runlength, runlength,0,0) +SEQUENCE(runlength,,100,100) + SEQUENCE(1,runlength),"0000"), mm, IF(LEFT(m,2)=RIGHT(m,2),probability,0), mmm, HSTACK(SEQUENCE(runlength,,1-probability,0), mm), mmmm, VSTACK(mmm, HSTACK(SEQUENCE(1,runlength,0,0),1)), INDEX(MatrixPower(mmmm, flips),1,runlength+1)))

@JGordon11 Honest question: why did you use LAMBDA here instead of VBA? What is the advantage that I am missing?

 

[StephenCrump]

There are online calculators for this kind of thing ....

Interesting link, thanks. I hadn't encountered the k-step Fibonacci method before.

You can get the result directly as 1 - (200th Heptanacci / 2^200)

= 1 - 7.332333E+59 / 1.606938E+60 = 0.543708 (as in the matrix approach above)

 

[JGordon11]

@JGordon11 Honest question: why did you use LAMBDA here instead of VBA? What is the advantage that I am missing?

VBA gets slow when using calls to the Application and requires saving the file as xlsm, so I'm just in the habit of using a lambda instead of when practical. So I will use a lambda if I need to use a lot of worksheet functions (here HSTACK, VSATCK, SEQUENCE, etc). In this case, the application calls would not be in a large loop so it wouldn't be too slow, so VBA would work fine. Since this lambda requires the MatrixPower VBA function, using VBA instead of a lambda would be a good choice.

 

[shg]

@StephenCrump, I make the 200th Heptanacci number as 5.8921171E+57, and so does the OEIS. What's the rationale for offsetting to H(207)? From the explanation in Wikipedia, "The sequence of the number of strings of 0s and 1s of length m that contain at most n consecutive 0s is also a Fibonacci sequence of order n."

The answer is certainly correct, just trying to understand.