It seems when I posted here so long ago I was unfamiliar with some of the literature. The great De Moivre a friend of Newton knocked this off a long time ago.
Thanks to him we have another approach. I will use it for:
n = 10000
H = 10
running it off I get 0.9925838943865506 which agrees nicely with the other methods.
]]>Wait, we are not done yet!
I don't think so.
Since A in this case is a 10 x 10 matrix if we had 10 different eigenvalues we could diagonalize A. But this is not the case. Also some of the eigenvalues are complex so we cannot diagonalize A over the reals.
I am relying on the theorem that says If A is an n x n matrix and A has n real and different eigenvalues then A is diagonalizable.
I have not proven that it is not diagonalizable over C. Trouble is in the examples in my reference books and notes, I never came across a diagonalizable matrix that didn't conform to the theorem above. Unfortunately, this page is muddying up the waters.
http://www.ltcconline.net/greenl/course … zation.htm
I have a strong feeling it is not diagonalizable because when I computed P^-1 * A * P using a method much like this page:
http://www.ma.iup.edu/projects/CalcDEMma/JCF/jcf2.html
I did not get a diagonal matrix.
You guys are having some interesting thoughts about these problems, how about posting your guesses as well as your conclusions. I would like to see them, if I may.
]]>Would there be any special significance in knowing that this matrix IS or ISN'T diagonalizable?
Yes, If you could diagonalize A then A^10000 would be easy to compute.
Is the matrix listed in post #5 DIAGONALIZABLE?
I don't think so.
Since A in this case is a 10 x 10 matrix if we had 10 different eigenvalues we could diagonalize A. But this is not the case. Also some of the eigenvalues are complex so we cannot diagonalize A over the reals.
2) Does the fact that this is the 'transistion' or 'state' matrix for an absorbing Markov Chain tell us anything about whether it IS or ISN"T Diagonalizable?
I would think, no. At least I am not aware of any relationship between a transition matrix and whether or not it is possible to have
P^-1 * A * P = D
]]>the other two related questions are:
2) Does the fact that this is the 'transistion' or 'state' matrix for an absorbing Markov Chain tell us anything about whether it IS or ISN"T Diagonalizable?
and
3) (again taking into consideration the context -- that this is a 'transistion' or 'state' matrix for an absorbing Markov Chain). Would there be any special significance in knowing that this matrix IS or ISN'T diagonalizable?
Hope this helps.
Thanks much!!
]]>Since A in this case is a 10 x 10 matrix if we get 10 different eigenvalues we can diagonalize the matrix. But this is not the case. Also some of the eigenvalues are complex so we cannot diagonalize A over the reals but it may be diagonalizable over C.
]]>I'm way out of my field with this question. Thanks so much for your help!
]]>Also, what's the probability that I will flip 10 heads in a row once or more if I flip the coin 10,000 times?
I have come up with a better way to do this recurrence:
Based on a method by Uspensky:
This is a little easier to compute and much easier on the eyes but not easier to get a closed form for.
Running the recurrence forward we of course get. .992583, same as above.
]]>If you get to see this:
I've been talking my friends through the first two methods, and they get them, but then ask: "can't you just do it with BINOMIALS, or nCr, or Pascal's triangle.....
I don't think about this set of problems often but looking around I came across a forum with a similar problem. WARNING - similar problems does not imply similar solutions. I don't think they can get very far with those approaches. But there is an interesting idea there.
]]>FANTASTIC!
Thanks, but not true. All solved problems are trivial and the ones solved by me beyond trivial.
Get the 9th edition! I picked mine up at a library sale for 50 cents. Mine is only the 4th ed. and it is the business and social science version so it is not as advanced as it could be.
I've been talking my friends through the first two methods, and they get them, but then ask: "can't you just do it with BINOMIALS, or nCr, or Pascal's triangle.....or something simple like that". I tell them that my sense of Probability is that it gets DIFFICULT QUICKLY, and that while this problem is SIMPLE TO POSE it's a little harder to crack than some High-School level Probability questions that might seem somewhat similar on the surface.
I don't think there is any simple way to do any part of that problem. Don't get me wrong, I am sure that someone like Feller,Wilf, Zeilberger, Riordan etc. could dust it off easily. That is only because they know deeper math. Intermediate Counting & Probability by David Patrick says that if an answer isn't simple then the problem probably doesn't have an simple binomial solution.
the method in post #8 I trust, but to my eyes right now, it looks UGLY.
Don't trust it! Verify it for yourself! There is no place in math for trust or faith. Check everything by everybody.
The formula by Feller is derived by deep concepts. The generating function and the recurrence are of necessity long. There beauty is that they are amenable to computer solution. To me the changing of a probability or combinatorics problem to a mere matrix multiplication or the expansion of a rational functional or polynomial is beautiful.
As problems grow in length and complexity (beyond book problems) you will find that the generic approach is to think of formulating them in terms of sums, integrals, trees,graphs, generating functions, markov chains, random walks, lattices and recurrences. This is because all of those are well implemented in computer algebra systems. In other words computer methods not hand methods. It is a tremendous advantage for your computer to be able to assist you.
Also, could you tell me which vol. of the Feller has the 24 pages I'm looking for?
Yes, volume 1 Chapter 13 Recurrent Events p 312. It is extremely difficult. As far as I can tell the formula for x is a truncation of 4.11 or 7.11, I am not sure.
The x here is just an approximation. It is the truncated form of some series. I don't even know what the next terms are. I could only surmise what they are. Fortunately, you don't have to understand a formula to use it!
]]>I didn't have any experience with the methods you used in post #3 and #5. I sat down with them both in a morning, and made sense of each. I find them both kinda elegant. the method in post #8 I trust, but to my eyes right now, it looks UGLY.
I've been talking my friends through the first two methods, and they get them, but then ask: "can't you just do it with BINOMIALS, or nCr, or Pascal's triangle.....or something simple like that". I tell them that my sense of Probability is that it gets DIFFICULT QUICKLY, and that while this problem is SIMPLE TO POSE it's a little harder to crack than some High-School level Probability questions that might seem somewhat similar on the surface.
.....but here's my question: would you use any of these terms:
>> BINOMIALS, or nCr, or Pascal's triangle
in connection with what you've done in Post #8?
And.....is there any way to "talk around" the idea of what x represents/relates to in this formula?
Also, could you tell me which vol. of the Feller has the 24 pages I'm looking for?
Thanks, bobbym!
NPI = No Pun Intended.
]]>NPI,
Please tell me what NPI means, I am stuck.
but I can't make Heads or Tails of the formula.
This is also a difficult part. It is supposedly from "An Introduction to Probability Theory and its Applications v1,v2 v3" by William Feller. He devoted 24 pages to the derivation of this formula. I am not totally through all 3 volumes. It is a tough read and probability and combinatorics are my favorites.
(or suggest a TEXT)
This is what I read to start.
My understanding of generating functions began with "Generatingfunctionology" , Herbert S. Wilf (The greatest all around mathematician alive). Also Riordans book on combinatorics.
The methods to create recurrence formulae from generating functions are covered in a Combinatorics book by the soviet, Villenkin.
Absorbing chains and stochastic matrices from "Finite Mathematics 4th ed.", by Mizrahi and Sullivan and the books by James T. Sandefur.
]]>Where I'm stuck is really at the beginning. Is there a TEXT or WEBPAGE that explores how this formula from Feller is derived?
Thanks a lot!
]]>Can you please indicate where you are stuck and I will try to help.
]]>I enjoyed the time I spent with the first two methods. I hadn't seen either of these techniques before I found this page while trying to answer a question similar to tongzilla's. I'm looking forward to understanding the post #8 method, but, for the moment, I'm stuck.
Thanks for your help!!
]]>