pacomartin
Joined: Jan 14, 2010
• Posts: 7895
March 24th, 2011 at 6:47:32 PM permalink
Thanks to Guido for pointing out this Ask the Wizard column.

As we all know the Wizard is nearly perfect, but on occasion he makes a minor slip up. In Ask The Wizard #253 he defined a transition matrix for a stochastic process that is not square. As everyone knows you can only take a square matrix to an arbitrary power.

Instead of simply pointing out a small error, let me take this opportunity to generalize the problem a little. The wizard defined the problem as the probability of getting a run of at least 7 "heads or tails" (either one is acceptable) out of 100 coin tosses.

Generalize to to allow for weighted coin (or a streak of 7 losses) with a given house edge.

The same problem can be answered by taking the following matrix to the 101st power. I have defined the probability of the casino winning as 20/38 as in roulette. However, note that it is a 9 by 9 matrix which can be taken to an arbitrary power. Replace the values 10/19 and 9/19 with 1/2 for the coin toss problem.

`0      	 1      0      	0      	0      	0      	0      	0      	0      0      	 9/19	10/19	0      	0      	0      	0      	0      	0      0      	 9/19	0    10/19	0      	0      	0      	0      	0      0      	 9/19	0      	0    10/19	0      	0      	0      	0      0      	 9/19	0      	0      	0     10/19	0      	0      	0      0      	 9/19	0      	0      	0      	0     10/19	0      	0      0      	 9/19	0      	0      	0      	0      	0     10/19	0      0      	 9/19	0      	0      	0      	0      	0      	0     10/190      	 0      0      	0      	0      	0      	0      	0      	1      `

There is more than one way to define the matrix (this is not the only matrix), but the answer must be correct.

The Wizard has the correct solution of 31.7520%.
Now if we add the house edge for roulette, the probability of losing 7 in a row out of 100 plays is now 40.8143%. We must simply change the percentages in the spreadsheet.

You can add your own house edge for whatever game you like. It's a good opportunity to learn the MMULT function in EXCEL.

By the way, EXCEL is an awkward way to do matrix manipulation as it is very time consuming. The process can be simplified if you change the question to determining k losses out of 63, 127, 255, 511, 1023 plays in a row (one less than a power of 2).If you need to do the extra work, you can do the problem recursively, or you can add all the extra steps, or you can learn a scientific software package (Guido suggested the free "Winmat" from Phillips Exeter Academy ).

`0.000%	28.191%	14.919%	7.896%	4.179%	2.211%	1.170%	0.619%	40.814%  <---------0.000%	28.035%	14.837%	7.852%	4.156%	2.199%	1.164%	0.616%	41.140%0.000%	27.742%	14.682%	7.770%	4.112%	2.176%	1.152%	0.610%	41.756%0.000%	27.188%	14.388%	7.615%	4.030%	2.133%	1.129%	0.597%	42.920%0.000%	26.140%	13.834%	7.321%	3.875%	2.051%	1.085%	0.574%	45.120%0.000%	24.161%	12.787%	6.767%	3.581%	1.895%	1.003%	0.531%	49.275%0.000%	20.420%	10.807%	5.719%	3.027%	1.602%	0.848%	0.449%	57.128%0.000%	13.353%	7.067%	3.740%	1.979%	1.048%	0.554%	0.293%	71.965%0.000%	0.000%	0.000%	0.000%	0.000%	0.000%	0.000%	0.000%	100.000%0.000%	34.262%	17.200%	8.635%	4.335%	2.176%	1.092%	0.548%	31.752% <---------0.000%	34.124%	17.131%	8.600%	4.317%	2.167%	1.088%	0.546%	32.026%0.000%	33.850%	16.993%	8.531%	4.283%	2.150%	1.079%	0.542%	32.572%0.000%	33.304%	16.719%	8.393%	4.214%	2.115%	1.062%	0.533%	33.661%0.000%	32.215%	16.173%	8.119%	4.076%	2.046%	1.027%	0.516%	35.828%0.000%	30.048%	15.085%	7.573%	3.802%	1.908%	0.958%	0.481%	40.145%0.000%	25.731%	12.917%	6.485%	3.255%	1.634%	0.820%	0.412%	48.745%0.000%	17.131%	8.600%	4.317%	2.167%	1.088%	0.546%	0.274%	65.876%0.000%	0.000%	0.000%	0.000%	0.000%	0.000%	0.000%	0.000%	100.000%`

The matrices are sometimes easier to develop than the recursive formulas. In the same column the Wizard develops a recursive formula to get to the same answer for coin tossing. It is somewhat difficult to generalize.

BTW: The Wizard points out that he does not know an explicit formula to answer this question. There is none, and it is possible to prove that there is no algebraic formula with mathematical analysis.

However, there is a closed form expression using k-step Fibonacci sequences, where the standard Fibonacci sequence is defined as a 2 step Fibonacci sequence. The extension of the concept is natural. But there are two problems, (1) the calculation is unstable for large numbers, (2) Fibonacci sequences are calculated recursively, so there is no avoiding the recursion. Mark Nelson describes the solution in his column , but he got it from the online guide to Mathematica here .

odiousgambit
Joined: Nov 9, 2009
• Posts: 8706
March 25th, 2011 at 3:03:44 AM permalink
Quote: pacomartin

...he defined a transition matrix for a stochastic process that is not square. As everyone knows you can only take a square matrix to an arbitrary power... a small error...]

a small error? Well, I guess! GEEEZ! !

And how about Einstein goofing on that Dark Energy prediction? Everybody knows that!
the next time Dame Fortune toys with your heart, your soul and your wallet, raise your glass and praise her thus: Thanks for nothing, you cold-hearted, evil, damnable, nefarious, low-life, malicious monster from Hell! She is, after all, stone deaf. ... Arnold Snyder
buzzpaff
Joined: Mar 8, 2011
• Posts: 5328
March 25th, 2011 at 8:05:47 AM permalink
Quote: pacomartin
...he defined a transition matrix for a stochastic process that is not square. As everyone knows you can only take a square matrix to an arbitrary power... a small error...]

Am I the only one here who has not idea what this means ?? Just curious, that's all. No disrespect meant.
DJTeddyBear
Joined: Nov 2, 2009
• Posts: 10586
March 25th, 2011 at 8:19:30 AM permalink
I was afraid to admit that I have no idea what he's even referring to when he says "as everyone knows...."
I invented a few casino games. Info: http://www.DaveMillerGaming.com/  Superstitions are silly, childish, irrational rituals, born out of fear of the unknown. But how much does it cost to knock on wood? 😁
buzzpaff
Joined: Mar 8, 2011
• Posts: 5328
March 25th, 2011 at 8:30:33 AM permalink
Quote: DJTeddyBear

I was afraid to admit that I have no idea what he's even referring to when he says "as everyone knows...."

Gee, now I feel less dumb Thanks
Wizard

Joined: Oct 14, 2009
• Posts: 23733
March 25th, 2011 at 9:03:38 AM permalink
You're right, thanks for that correction. My spreadsheet on that question has the right matrix, I just expressed it incorrectly for the column.
It's not whether you win or lose; it's whether or not you had a good bet.
guido111
Joined: Sep 16, 2010
• Posts: 707
March 25th, 2011 at 9:46:48 AM permalink
Quote: pacomartin

Thanks to Guido for pointing out this Ask the Wizard column.

As we all know the Wizard is nearly perfect, but on occasion he makes a minor slip up. In Ask The Wizard #253 he defined a transition matrix for a stochastic process that is not square. As everyone knows you can only take a square matrix to an arbitrary power.

In the same column the Wizard develops a recursive formula to get to the same answer for coin tossing. It is somewhat difficult to generalize.

The Wizard's formula in his column IMO is simple and elegant. Excellent work Wizard!
I expanded his formula to accept any value of p. And I was surprised that it returns exact results since The Wizard made no mention of that in his column, since he was answering a fair coin toss question, but he did spell out his formula in easy to understand English, for me at least.

NBA player Steve Nash has a lifetime .904 free throw percentage while attempting 3,100. What is the probability that he has made at least 50 or more in a row one time in his career?
How about a streak of 75? or 100?
(His personal record is 74 straight)

Another popular run question would be: What is the probability of tossing 5 or more heads in a row in 20 coin tosses with a fair coin?
Also, A basketball player shoots free throws with a 50% success rate. What are the chances (s)he makes 5 or more in a row in 20 consecutive attempts?
One can see the answer below.
Here is a snap shot of my Excel worksheet.

D4=(\$B\$2*D3)+(\$B\$1*\$B\$2*D2)+(\$B\$1)^2
E5=(\$B\$2*E4)+(\$B\$1*\$B\$2*E3)+((\$B\$1)^2*(\$B\$2)*E2)+(\$B\$1)^3
F6=(\$B\$2*F5)+(\$B\$1*\$B\$2*F4)+((\$B\$1)^2*(\$B\$2)*F3)+((\$B\$1)^3*(\$B\$2)*F2)+(\$B\$1)^4
G7=(\$B\$2*G6)+(\$B\$1*\$B\$2*G5)+((\$B\$1)^2*(\$B\$2)*G4)+((\$B\$1)^3*(\$B\$2)*G3)+((\$B\$1)^4*(\$B\$2)*G2)+(\$B\$1)^5

Formula can be entered into the cell and filled down to whatever trial row you like.
Each new column just adds 1 term before the final term and both last terms need to be adjusted. I think one can see the pattern.

I hope this helps someone in the future. it has with me.

pacomartin gave me a great lesson for Markov Matrices, that I am still learning. Thank you for that.

I have uploaded 2 Excel files if you want to download them. To change the value of p, just enter a new value in cell B1 and in a few seconds the complete sheet is updated. Default value p=.5
The first is for Excel 2007 HERE size 5.3mb
The second for Excel 2003 and earlier HERE size 17mb

In 2008 and 09 there was a lot of net activity about calculating runs (streaks). I wonder what started it all.
A handy JavaScript streak calculator can be found HERE
Enjoy
pacomartin
Joined: Jan 14, 2010
• Posts: 7895
March 25th, 2011 at 12:05:12 PM permalink
Quote: DJTeddyBear

I was afraid to admit that I have no idea what he's even referring to when he says "as everyone knows...."

My attempt at sarcasm seems to have fallen flat. I know that most people don't get to matrix manipulation. It is not regularly taught until after Calculus in college. Some kids in high school are taught them at top notch schools (if Guido's son is at Phillip's Exeter they probably teach them in some courses).

Matrices came into more widespread use in the mid 19th century as routine way to solve common mathematical problems. In the 20th century the Russian mathematician developed transition matrices to solve stochastic problems.

I was simply showing one, of several possible ways to extend the concept of a streak at coin tossing, to calculating a streak of losses (or wins).

Every problem solvable matrix algebra is also solvable by a set of recursion formulas, by definition. Matrices are often easier to set up, while recursion formulas are sometimes difficult to develop.

A past problem which is easily solvable by a Markov matrix is, " What is the probability of a woman rolling 154 times in craps?"
Time Magazine incorrectly reported the odds as 1 in 1.56 trillion.

Ask the Wizard craps solves the problem with recursive formula. The correct answer is
1 in 5,590,264,072 which is line 153 in the calculation. The reason it is line 153 and not line 154 is because the first roll in craps is always followed by a second roll. There are only 153 times you could 7-out in a streak of 154 rolls of the dice.

I'll post the matrix solution without explanation. A detailed explanation including how to develop the matrix is on Michael's webpage Problem #204.
It will be a good exercise for Guido's son (or anyone else)
A 4 by 4 square matrix to describe the transitions in a pass line bet in craps follows (where blanks are filled with zeros):
`12	3	4	56	27		8		26	10			25`

Define the above matrix by the letter A

Calculate (A/36)^153

Multiply by the following 4 by 1 vector
`1000`

If you multiply a 4 by 4 matrix by a 4 by 1 vector you will get a 4 by 1 vector.

Sum the entries in the final 4 by 1 vector and you will get 1 / 5,590,264,072 .
buzzpaff
Joined: Mar 8, 2011
• Posts: 5328
March 25th, 2011 at 12:14:55 PM permalink
My attempt at sarcasm seems to have fallen flat. I know that most people don't get to matrix manipulation. It is not regularly taught until after Calculus in college. Some kids in high school are taught them at top notch schools (if Guido's son is at Phillip's Exeter they probably teach them in some courses).

No, we all know it was sarcasm. Just that those of us who are now struggling with filing our 2010 tax forms feel like our head is in a vice. And would like to escape to the matrix.
guido111
Joined: Sep 16, 2010
• Posts: 707
March 25th, 2011 at 12:57:42 PM permalink
Quote: buzzpaff

My attempt at sarcasm seems to have fallen flat. I know that most people don't get to matrix manipulation. It is not regularly taught until after Calculus in college. Some kids in high school are taught them at top notch schools (if Guido's son is at Phillip's Exeter they probably teach them in some courses).

No, we all know it was sarcasm. Just that those of us who are now struggling with filing our 2010 tax forms feel like our head is in a vice. And would like to escape to the matrix.

Amen.

My son is 19 and knows everything. His problem is when trying to explain things that are simple to him to others like me in a way I can understand.
It must be a talent.
pacomartin is good
The Wizard is excellent.
He must have been a good teacher somewhere in his life's journey.