Talk:Algorithmically random sequence
RAND is Sigma^0_2
It is correct to say that RAND is Sigma^0_2, because there is a Sigma^0_2 formula that defines the class of 1-random real numbers. It is not true that every random real is itself Sigma^0_2; there are 1-random reals of arbitrarily high Turing degree. CMummert 23:41, 23 June 2006 (UTC)
Here are some comments on the changes I made today
- It is not NPOV to describe some things are very technical and describe other things as very easy. My impressions of easy and hard are in fact the opposite of the opinions the article used to have. In any event, there is no reason to lecture the reader about how hard some idea is. I removed all such comments.
- I rewrote the Martin-Löf definition in topological language, which should be more clear.
- I made other small changes.
CMummert 14:00, 24 June 2006 (UTC)
I don't think it's proper to call the measure of a cylinder Lebesgue measure. A cylinder isn't a subset of R^n. It's not internally consistent even with Wikipedia's current definition of Lebesgue measure. ~~
- I rephrased it to say fair coin measure. Everyone can edit, so you can make changes like that yourself to save time. CMummert 14:58, 27 July 2006 (UTC)
- I think calling it Lebesgue measure is pretty standard. People often don't distinguish between a subset of natural numbers, an infinite binary sequence, and the real number with said sequence as it's binary expansion. So Lebesgue measure on cantor space is really Lebesgue measure on the interval under suitable blurring of definitions. There is a slight issue of the fact that .1000...=.0111..., but such things have measure 0 anyways.
Complexity is prefix-free
I noticed that the article made no mention that the Kolmogorov complexity definition of randomness made no mention that the complexity used is prefix-free complexity, not plain complexity. This is important, since if you used plain complexity for the definition, there would be no resulting random sequences, because you can use a trick to get some extra compression by using the length of your input program as additional information. On the other hand, I worry that I may have made the article harder to understand for a non-mathematician reader. If you are reading this and have any thoughts, feel free to change or revert if you think added precision is not worth the tradeoff. Althai 00:37, 30 April 2007 (UTC)
About universality of martingale
There is a universal constructive martingale d. This martingale is universal in the sense that, given any constructive martingale d, there is some constant λ>0 so that for any string σ,
This is the definition of optimal martingale and no c.e. martingale is optimal, see "Algorithmic randomness and complexity". —Preceding unsigned comment added by コドボル (talk • contribs) 09:23, 26 May 2010 (UTC)
Martin-Löf randomness has since been shown to admit...random sequences should be incompressible, they should pass statistical tests for randomness, and it should be difficult to make money betting on them.
The nature of the randomness has no relevance to how easy it is to make money betting on them. This needs to be clearer to be true. I am not going to edit as it is 15 years since I did any algorithmic computer science, but these days, doing finance, i know that statement is untrue.
It is dificult to make money betting on the precise value of a sequence, but a sequence can fall within bounds, bounds that can be discovered and exploited in the sense of gambling, and still the values of the sequence can be random from the POV I understand it (Chaitin: The sequence is un-compressible.)
Gambling strategies are every bit as evolved, sophisticated and complex as AIT these days. So the language needs to be moderated. It may indeed be very easy to make money by betting on a random sequence.
Worik (talk) 20:46, 2 November 2010 (UTC)