Author |
Topic: randomness (Read 4515 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
Re: randomness
« Reply #25 on: Mar 17th, 2008, 12:47pm » |
 Quote  Modify
|
on Mar 17th, 2008, 8:42am, BenVitale wrote:| "Note that the largest possible value for the area of the smallest triangle is > 1/(8n^2), because taking a prime p between n and 2n, no three of the p points (x,x^2) mod p are collinear." |
|
Suppose (x,x2), (y,y2), and (z,z2) are collinear mod p. This gives
det [ [ y-x, y2-x2 ] , [ z-x, z2-x2 ] ] = 0 mod p.
But as a function of z, this is a degree 2 polynomial, so over the field  /p, has at most 2 solutions. These solutions must be z=x and z=y. So there is no third point.
Now pick n < p < 2n (Bertrand), and form a pxp grid. From the determinant form (or Pick's theorem), any triangle formed by three points on an integral grid has area a multiple of 1/2. So for the points (1,1), (2,4), (3,9), ..., (n,n2) mod p, each triangle has area at least 1/2, since none have area 0. Scaling the whole thing down to fit in a unit square, each triangle has area at least 1/2*1/p2  1/8n2.
|
|
 IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: randomness
« Reply #26 on: Mar 17th, 2008, 4:15pm » |
Quote Modify
|
Suppose (x,x^2), (y,y^2), and (z,z^2) are collinear mod p. This gives det [ [ y-x, y^2-x^2 ] , [ z-x, z^2-x^2 ] ] = 0 mod p
Can you give an example of this? I think there are some concepts here which I'm unfamiliar with.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: randomness
« Reply #27 on: Mar 17th, 2008, 4:58pm » |
Quote Modify
|
Three point A,B,C in the plane are collinear iff the vectors B-A, C-A are linearly dependent, which happens iff the matrix whose rows are (B-A) and (C-A) has determinant 0.
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: randomness
« Reply #28 on: Apr 10th, 2008, 8:47pm » |
Quote Modify
|
I have a new problem, and i would appreciate your insights:
Lut u(n) be the mobius function and let M(x)=sum(n less than x) u(n). It can be shown that the claim that M(x)=O(x^(1/2 +e)) for every e greater than 0 is equivalent to the Riemann Hypothesis.
See wiki under "Growth rate of Mobius function" for more details
http://en.wikipedia.org/wiki/Riemann_hypothesis
Now it can be shown that if K(x) represents the sum of heads minus the sum of tails obtained
from a coin that is flipped x number of times, then we also have K(x)=O(O(x^(1/2 +e))
for every e greater than 0. Unfortunately, the proof for this case requires us assuming
that the coin flips are random. This raises the following interesting questions.
1. Is there a fundamental difference between the Riemann Hypothesis, and the coin flipping problem?
2. Do we have to prove some sort of randomness condition for the primes numbers in order to prove the Riemann Hypothesis?
3. Is such a proof even possible?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: randomness
« Reply #29 on: Apr 11th, 2008, 11:34am » |
Quote Modify
|
We know that Georg Riemann found a vital clue. He discovered that the secrets of the primes are locked inside something called the zeta function.
And, Riemann Riemann worked out that if the zeros really do lie on the critical line, then the primes stray from the 1/ln(x) distribution exactly as much as a bunch of coin tosses stray from the 50:50 distribution law. This is a startling conclusion. The primes aren't just unpredictable, they really do behave as if each prime number is picked at random, with the probability 1/ln(x) -- almost as if they were chosen with a weighted coin. So to some extent the primes are tamed, because we can make statistical predictions about them, just as we can about coin tosses.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: randomness
« Reply #30 on: Apr 29th, 2008, 12:31pm » |
Quote Modify
|
Can we develop a test to determine the randomness of certain observationly deterministic random sequences, i.e. can we test Sequence x_n generated by x_n=(x_(n-1))^2 mod(k) where x_0 is fixed and k is the product of two very large prime numbers? (known as Blum-Blum-Shub generators -- It is supposed to be a kind of deterministic random number generator.)
- Can deterministic random sequences really exist?
- Is there a fundamental difference between deterministic and non-deterministic random sequences?
- If deterministic random sequences are possible, then is it possible to ask math questions associated with such sequences which have non-deterministic answers (ie there is no 'yes or no' solution to the question)?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: randomness
« Reply #31 on: Apr 29th, 2008, 1:06pm » |
Quote Modify
|
on Apr 29th, 2008, 12:31pm, BenVitale wrote:| - Can deterministic random sequences really exist? |
|
As such, no. If you know all the variables involved, then the next value is known with complete certainty. However, if underlying variables are unknown, it may be impossible to tell where in the sequence you are, or indeed if it matches any deterministic function at all.
There is no randomness, but there is a lack of knowledge that makes predictions about the sequence equally infeasible.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: randomness
« Reply #32 on: Apr 29th, 2008, 2:29pm » |
Quote Modify
|
Thanks for answering to my first question.
What do you think of the following claim:
Quote:| Claim: Pseudorandom numbers are not really random at all. They are the result of deterministic mathematical formulae. |
|
I don't agree with the claim that just because a sequence is given by some formula it must necessarily be non-random. Consider the following example:
Suppose we a have two sets A and B. Now let us suppose that an integer N is in set A if it satisfies property X and that an integer M is in set B if it satisfies property Y. Now let us define a sequence by the following rule.
Let X_n represent the n^th positive integer that is in both sets A and B. That is, the n^th positive integer possessing both properties X and Y.
Question: If there is no relationship between the integers that satisfy property X and the integers that satisfy property Y, then will X_n necessarily have to be a random sequence?
Most pseudo-random sequences generated cannot be exactly described using the above scenario, however the reason they may be random is due to something similar. For example, the Mobius function could be a deterministically random sequence because there is no relationship between the size of n and whether or not n is the product of an odd or even number of prime factors.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: randomness
« Reply #33 on: Apr 30th, 2008, 1:51am » |
Quote Modify
|
on Apr 29th, 2008, 2:29pm, BenVitale wrote:What do you think of the following claim:
"Claim: Pseudorandom numbers are not really random at all. They are the result of deterministic mathematical formulae."
I don't agree with the claim that just because a sequence is given by some formula it must necessarily be non-random. |
|
Anything that's 'given' is non-random. Given complete knowledge of the current state, you know with complete certainty the next state; there is nothing random about it. For there to be randomness, there must be multiple states you can reach given the current state, without complete certainty as to which you will end up in.
Quote:Consider the following example:
Suppose we a have two sets A and B. Now let us suppose that an integer N is in set A if it satisfies property X and that an integer M is in set B if it satisfies property Y. Now let us define a sequence by the following rule.
Let X_n represent the n^th positive integer that is in both sets A and B. That is, the n^th positive integer possessing both properties X and Y.
Question: If there is no relationship between the integers that satisfy property X and the integers that satisfy property Y, then will X_n necessarily have to be a random sequence? |
|
No. There is nothing random about it; every X_n is set in stone from the moment X and Y are defined, for all n, for all eternity. If you don't know X and Y the sequence may seem random, but appearances aren't everything in life.
A random process is never perfectly predictable; deterministic processes are, given complete knowledge. Randomness and determinism are by definition antithetical.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: randomness
« Reply #34 on: Apr 30th, 2008, 8:04pm » |
Quote Modify
|
Let us hypothetically suppose that there do exist high-quality PRNG (pseudorandom number generators ) that are indistinguishable from a truly random sequence when the algorithms that generate them are unknown. If we compare this sequence to say a sequence that was determined by the flipping of a coin that had already taken place, then what exactly can we say is the difference between the two if indeed there is no mathematical difference?
To me it makes no sense that we still must consider them as different just because one of them could be predicted if only we had the right information?
PS: This debate sorta feels like the one Einstein had with Borh back when they where debating the validity of Quantum Physics, and Einstein was arguing that just because we lack information regarding the photon, doesn't mean that the photon doesn't have that information, and thus QM must be a deterministic process.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: randomness
« Reply #35 on: May 1st, 2008, 1:07am » |
Quote Modify
|
on Apr 30th, 2008, 8:04pm, BenVitale wrote:| Let us hypothetically suppose that there do exist high-quality PRNG (pseudorandom number generators ) that are indistinguishable from a truly random sequence when the algorithms that generate them are unknown. If we compare this sequence to say a sequence that was determined by the flipping of a coin that had already taken place, then what exactly can we say is the difference between the two if indeed there is no mathematical difference? |
|
Here we come to the distinctions that it's really processes that are random, and not sequences.
Any sequence may have been generated by a random process. If you write it as binary number and concatenate them all together; say you K bits, then flipping a coin had 1/2K probability of generating that same sequence. Of course, from that point onwards the sequences have a high probability of diverging if either generating process is random.
Quote:| To me it makes no sense that we still must consider them as different just because one of them could be predicted if only we had the right information? |
|
They're distinct logical possibilities.
And as far as PRNG on computers go, due to limited resources they inevitably repeat themselves with a fix period (which may be unimaginably long, but still). And if you start them from the same seed, they always give the same sequence.
Quote:PS: This debate sorta feels like the one Einstein had with Bohr back when they where debating the validity of Quantum Physics, and Einstein was arguing that just because we lack information regarding the photon, doesn't mean that the photon doesn't have that information, and thus QM must be a deterministic process.
|
|
The EPR experiment is generally considered to have busted the theory of hidden variables.
However, if QM was really deterministic after all, then quantum computing would be bust. You couldn't use superposition to calculate on all possibilities at once, because in reality you'd only work through one possibility.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: randomness
« Reply #36 on: May 9th, 2008, 9:04am » |
Quote Modify
|
I visited "Exploring RANDOMNESS ,G J Chaitin, IBM Research"
http://www.cs.auckland.ac.nz/~.....index.html
does Chatin really consider that many problems in mathematics (eg Riemann Hypothesis) are just probabilistic accidents and don't have any proofs?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: randomness
« Reply #37 on: May 9th, 2008, 10:24am » |
Quote Modify
|
If we consider the sequence 0, 1, 0, 1, 0, 1, ... (0 at even places, 1 at odd ones).
Is it random? It does have one property of a random sequence of 0 and 1: as N -> oo the proportion of 0's in the first N terms approaches 50%.
But now you may say: no, this sequence is not random, because if we consider consecutive pairs of terms, the pairs 0,0 and 1,1 never appear, but in a random sequence each should appear in a 25% proportion.
The same objection can be raised to the mobius sequence: although the prime number theorem does tell us that the proportion of 1's is equal to the number of -1's, if you consider pairs of terms of the form Mu(n), Mu(2n), then they can never be equal. In a truely random sequence assuming finitely many values (e.g. 0, 1, -1), the terms a(n) and a(2n) should be equal infinitely many times (i.e. the probability of this event is 1).
A similar objection can be raised against any pseudorandom sequence. Some randomness properties hold and others don't. A truely random sequence must satisfy every property you would expect from a random sequence.
Of course when it comes to finite sequences, there is no mathematical distinction between random and pseudorandom, unless you consider infinite families of finite sequences.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: randomness
« Reply #38 on: May 9th, 2008, 11:19am » |
Quote Modify
|
I have "randomness" on my mind. Sorry for posting these different messages w/o waiting for a reply first. My next questions are:
What properties of randomness must a sequence have in order for a math question regarding that sequence can be considered non-deterministic? Or perhaps more generally, is it possible to ask questions regarding sequences that aren't completely random which will have non-deterministic answers?
what conditions need to be met in order for a math problem to be considered non-deterministic?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: randomness
« Reply #39 on: May 20th, 2008, 11:09am » |
Quote Modify
|
Suppose we have a sequence of numbers where X% of the numbers are randomly generated, while
(1-X)% of them are not randomly generated (eg. they are determined by some specific formula).
Without trying to figure out what this formula is, is there a way to determine X?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: randomness
« Reply #40 on: May 20th, 2008, 2:28pm » |
Quote Modify
|
on May 20th, 2008, 11:09am, BenVitale wrote:Suppose we have a sequence of numbers where X% of the numbers are randomly generated, while
(1-X)% of them are not randomly generated (eg. they are determined by some specific formula).
Without trying to figure out what this formula is, is there a way to determine X? |
|
I'd answer no.
From the point of view of someone who only observes the sequence, isn't a number coming from some unknown (and probably intricate) deterministic process pretty much the same as a number coming from some random process? If yes, how are we going to tell these numbers apart?
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: randomness
« Reply #41 on: May 21st, 2008, 4:56am » |
Quote Modify
|
If you know what the formula is (or rather what values it would produce for each entry), then you can derive an approximate value for X - either assuming that the match values are all generated by the formula (suitable when there's a large range of possible numbers, so a low probability of a coincidence) or by assuming that the non-match values represent (1-N)/N of the random values, and calculating X on that basis
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print