Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

Geek Culture / Computer Cracks Erdős Puzzle

Author
Message
Derek Darkly
12
Years of Service
User Offline
Joined: 22nd Sep 2011
Location: Whats Our Vector, Victor?
Posted: 21st Feb 2014 22:56 Edited at: 21st Feb 2014 23:18
Link
Computer Cracks Erdős Puzzle

Quote: "“You have a sequence of 1s and -1s (for instance, generated by tossing a coin) and a constant C. One is looking for a finite subsequence long enough so that the sum of the elements of the subsequence is larger than C.”"


So, random ones and neg. ones are generated until the sum is larger than the constant... but if it's random, how can there be a definitive answer? And is the constant randomly chosen also?

Or am I not understanding the problem correctly?

Back to top
Profile PM
Indicium
15
Years of Service
User Offline
Joined: 26th May 2008
Location:
Posted: 21st Feb 2014 23:14
Link
Seems like a pointless problem.


They see me coding, they hating. http://indi-indicium.blogspot.co.uk/
Back to top
Profile PM
Derek Darkly
12
Years of Service
User Offline
Joined: 22nd Sep 2011
Location: Whats Our Vector, Victor?
Posted: 21st Feb 2014 23:20
Link
Quote: "Seems like a pointless problem."


That's what I'm thinking... how could this be "solved?"
Wouldn't it, in all probability, produce a different result every time?

Back to top
Profile PM
easter bunny
11
Years of Service
User Offline
Joined: 20th Nov 2012
Playing: Dota 2
Posted: 21st Feb 2014 23:20 Edited at: 21st Feb 2014 23:21
Link
Statistically it should never happen should it?

There should always be an average of 0


Using a computer is a bad way of doing it because computers can't form truly random numbers


Audacia Games - Facebook
Back to top
Profile PM Email
Indicium
15
Years of Service
User Offline
Joined: 26th May 2008
Location:
Posted: 22nd Feb 2014 01:22
Link
Quote: "There should always be an average of 0"


Over the entire set, yes. Over a subset, not necessarily.


They see me coding, they hating. http://indi-indicium.blogspot.co.uk/
Back to top
Profile PM
easter bunny
11
Years of Service
User Offline
Joined: 20th Nov 2012
Playing: Dota 2
Posted: 22nd Feb 2014 01:45 Edited at: 22nd Feb 2014 01:45
Link
ohhhhh, I get it.

They looking to the place along the infinite string of +1's and -1 where the total so far is larger than any number you care to name (even if it's 109845).

What I'd say the answer is this:
If you take the total from the start to position x, then the average will always be 0 (+- a bit). But with an infinitely long list of 1's and -1's, assuming it's completely random (and therefore non-repeating), you will be definitely able to find a substring that is larger than c.


Audacia Games - Facebook
Back to top
Profile PM Email
BMacZero
18
Years of Service
User Offline
Joined: 30th Dec 2005
Location: E:/ NA / USA
Posted: 22nd Feb 2014 08:55 Edited at: 22nd Feb 2014 08:56
Link
The researchers aren't actually trying to find the particular subsequence that works for a particular C - they're trying to prove mathematically that one must exist in an infinite sequence for an arbitrarily large C. It's a hypothesized property of infinite sequences.

It might make more sense if you could find the actual academic paper related to this. The news article says some weird things (for example, I can't imagine how a sequence of only 1161 +1s and -1s could take up 13GB).

Back to top
Profile PM Email Website
nonZero
12
Years of Service
User Offline
Joined: 10th Jul 2011
Location: Dark Empire HQ, Otherworld, Silent Hill
Posted: 22nd Feb 2014 09:15
Link
pseudo code:
rnd = rand()
pick = ((rnd * 1) + (rnd * -1))
answer = C * (pick * pick)

Notes: Multiplying the pick of -1s and 1s ensures no negative numbers and therefore the pick total is >=1. Multiply that by the constant, C, and it ensures your answer is >=C.
Essentially we're adding one step. Or am I missing some of the rules?

ver7.5
Back to top
Profile PM Email Website
BatVink
Moderator
21
Years of Service
User Offline
Joined: 4th Apr 2003
Location: Gods own County, UK
Posted: 24th Feb 2014 10:22
Link
Averages and probabilities are two different things. The average of a large sample of coin tosses will tend towards 50/50. But throwing 10 heads does not increase the probability of throwing a tail - it still has a 50% chance on the next throw. I guess this challenge is all about complex probability theory.

The challenge is about finding the outcome in a large sequence. It's like one of us playing tennis against Andy Murray. Most people would want to play "best of 5", but actually you should play "best of 1". Because he has a 95% chance of beating you, the probability is 95% in one game but across 5 games it's ~100%. Small sets of data produce the more extreme results and large sets tend towards the average.

It sounds like a variation on the Infinite number of Monkeys - if an infinite number of monkeys type, they will create the entire works of Shakespeare. Or as it was once played out...

Quote: "Harry, Harry, we've got something!

To be or not to be, that is the gzarnanplatz"


ten-net consulting limited
Back to top
Profile PM Email
Libervurto
17
Years of Service
User Offline
Joined: 30th Jun 2006
Location: On Toast
Posted: 26th Feb 2014 21:45 Edited at: 26th Feb 2014 21:47
Link
I don't see why this is something that needs to be proved. If we are looking for a particular sequence of results and the probability of heads/tails is equal then the probability of every possible sequence is also equal.

h = t = 0.5 = ½
hh = ht = th = tt = 0.5² = 0.25 = ¼
hhh = hht = hth = htt = thh = tht = tth = ttt = 0.5³ = 0.125 = ⅛
hhhttt = hththt = hhhhhh = tttttt = hhtthh = ... = 0.5⁶ = 0.0125625

okay... this forum doesn't like exponents or fractions? Let's try in a code box



Formerly OBese87.
Back to top
Profile PM Email
BatVink
Moderator
21
Years of Service
User Offline
Joined: 4th Apr 2003
Location: Gods own County, UK
Posted: 26th Feb 2014 22:03
Link
The Discrepancy theory isn't about the permutations. The quote in the original post is a bad explanation of the problem (the fault of the website I think).

The theory is best described with the current solution for C=2. It simply says: If you have a sequence of 1161 Heads/Tails, you will always get a value of at least 2. In other words, there will always be at least 2 more heads than tails.

The next stage would be to find out if there is a sequence length that will always give a solution for C=3

ten-net consulting limited
Back to top
Profile PM Email
Indicium
15
Years of Service
User Offline
Joined: 26th May 2008
Location:
Posted: 26th Feb 2014 22:06
Link
But surely there is no number for this, surely there can't be a sequence that will ALWAYS give C=2 if it's truly random - there's a possibility you could get 1161 tails! (An infinitely small one, I know.)


They see me coding, they hating. http://indi-indicium.blogspot.co.uk/
Back to top
Profile PM
Dark Java Dude 64
Community Leader
13
Years of Service
User Offline
Joined: 21st Sep 2010
Location: Neither here nor there nor anywhere
Posted: 27th Feb 2014 00:22
Link
This problem sparked an interesting question in my head. So say you have a random number generator, and it can generate any random real number, at all. Values infinitely negative to values infinitely positive may be generated by this random number generator. Now say you take the average of every single value this generator comes up with. After generating a lot of values, the average will be tending off to zero, I might assume. That makes sense.

Now, say we limited the random number generator. The generator is now only allowed to generate real numbers above zero, but that's its only limitation. Infinitely positive numbers are still possible. So what would happen to the average, now? Would it tend off to infinity as more values are generated? Surely not. The average would, in that case, be completely random and unpredictable, right?

Back to top
Profile PM Website
BatVink
Moderator
21
Years of Service
User Offline
Joined: 4th Apr 2003
Location: Gods own County, UK
Posted: 27th Feb 2014 00:46 Edited at: 27th Feb 2014 00:46
Link
Quote: "surely there can't be a sequence that will ALWAYS give C=2 if it's truly random - there's a possibility you could get 1161 tails!"


It's not C=2, it's C>=2 (my mistake earlier, sorry). 1161 Tails would fulfill this criteria, as C represents a difference in number of heads/tails flipped.

The scenario that would break this rule would be just one extra head or tail (e.g 580 heads, 581 tails). This would result in C=1.

What this theory is trying to prove (and it is not yet proven) is that there comes a point in a random sequence of events where you always get a discrepancy (C).

My head is blown, I don't see how this is possible given the definition of random as we know it.

ten-net consulting limited
Back to top
Profile PM Email
Libervurto
17
Years of Service
User Offline
Joined: 30th Jun 2006
Location: On Toast
Posted: 27th Feb 2014 02:43
Link
Quote: "Now, say we limited the random number generator. The generator is now only allowed to generate real numbers above zero, but that's its only limitation. Infinitely positive numbers are still possible. So what would happen to the average, now? Would it tend off to infinity as more values are generated? Surely not. The average would, in that case, be completely random and unpredictable, right?"

I think it would tend towards infinity. Think about it like this, say the first number you draw is 90531, then what is the chance that the next number will be less than 90531, and lower the average, versus the next number being greater than 90531, and raising the average?

Formerly OBese87.
Back to top
Profile PM Email
Dark Java Dude 64
Community Leader
13
Years of Service
User Offline
Joined: 21st Sep 2010
Location: Neither here nor there nor anywhere
Posted: 27th Feb 2014 03:24 Edited at: 27th Feb 2014 03:25
Link
Ah! Good way to think about it, indeed. If I am not mistaken, there would be an infinitely small chance that any number would lower the average, but an infinitely high chance that any number would raise the average?

Back to top
Profile PM Website
nonZero
12
Years of Service
User Offline
Joined: 10th Jul 2011
Location: Dark Empire HQ, Otherworld, Silent Hill
Posted: 27th Feb 2014 11:51 Edited at: 27th Feb 2014 12:08
Link
Okay, looked at the Wikipedia on Discrepancy Theory. Basically, it states that it\'s impossible for complete uniformity in a certain set. I totally misunderstood coz that quote is ambiguous.

Okay, the theoretical term \"random\" (we\'ll call trand) is no relationship to the real-world examples we call \"random\" (rrand).
Why? Because random does not exist in the physical world. Rrand is the result of (in some cases innumerable -- to humans) sets of calculable factors. Example: tossing a coin. What happens is dependent on dents, warping or other irregularities in the coin, its position in relation to your finger when flicked up, air pressure and movement, gravity, dust particles, velocity flicked at, position your hand was when you caught it, etc. Nothing is rrand because rrans is a simplified explanation of \"too many calculable factors\" (btw, I say calculable because they are, individually). So dismiss any real-world. example because irrespective of probability, possibility will always exist given the correct circumstances.
Onwards. Trand is different because it is an abstract and its own laws are applicable to it. The question is, though, how to actually produce trand. Even RNG on a PC is a technically calculable outcome. RNG relies on seeds and algorithms. Much like rrand, RNG results are predictable if all factors are known. However, decently-crafted algorithms will do their best to produce results that are, at times, one-sided and others, more evenly distributed. In that way, RNG with computers is possibly closer to trand.

Where am I going? Honestly I believe it is possible for perfect distribution in the real world with rrand. I don\'t deny that trand will obey the theory for one moment just as the characters of Harry Potter will obey the laws if magic. I also don\'t deny that RNG on computers may yield results favouring the theory. However, this simply cannot be applied to the real world as anything more than a high probability since each circumstance involves absolute factors that guarantee an absolute outcome.

ver 7.5 /// int 145 /// str 45 /// dex 85 /// end 200 /// mat 3
Back to top
Profile PM Email Website
BatVink
Moderator
21
Years of Service
User Offline
Joined: 4th Apr 2003
Location: Gods own County, UK
Posted: 27th Feb 2014 12:50
Link
I almost agree with all of that except for one tiny but hugely significant thing. When you say:

Quote: "each circumstance involves absolute factors that guarantee an absolute outcome"


As the saying goes, what happens when a butterfly flaps it's wings?
This is a question asked about predicting the future. Because something as insignificant as a butterfly beating it's wings changes the entire course of the future. The movement of people around your coin when it is tossed is not an absolute factor with a guaranteed absolute outcome.

It's all too much for my head

ten-net consulting limited
Back to top
Profile PM Email
nonZero
12
Years of Service
User Offline
Joined: 10th Jul 2011
Location: Dark Empire HQ, Otherworld, Silent Hill
Posted: 27th Feb 2014 20:59
Link
Except that human behavior is even predetermined. The fact that I posted this proves I was going to. Factors are my psychological makeup vs my habitat. The future is already written. By deciding not to do something (in an attempt to escape fate) you are fulfilling your fate because that was predetermined.
Welcome to The Matrix

ver 7.5 /// int 145 /// str 45 /// dex 85 /// end 200 /// mat 3
Back to top
Profile PM Email Website
BatVink
Moderator
21
Years of Service
User Offline
Joined: 4th Apr 2003
Location: Gods own County, UK
Posted: 27th Feb 2014 21:13
Link
Quote: "The fact that I posted this proves I was going to"


Major flaw in that one. Even if my action of creating the scenario to which you would respond was predetermined, you had no way of knowing I would, ergo you weren't predestined to post a reply.

I took the red pill and was surprised at the normality of what I saw

ten-net consulting limited
Back to top
Profile PM Email
bitJericho
21
Years of Service
User Offline
Joined: 9th Oct 2002
Location: United States
Posted: 28th Feb 2014 01:14
Link
Quote: "Except that human behavior is even predetermined. The fact that I posted this proves I was going to. Factors are my psychological makeup vs my habitat. The future is already written. By deciding not to do something (in an attempt to escape fate) you are fulfilling your fate because that was predetermined.
Welcome to The Matrix "


If that were true we wouldn't have evolved awareness, what's the purpose of awareness if not to make better decisions?

Back to top
Profile PM Email Website
Libervurto
17
Years of Service
User Offline
Joined: 30th Jun 2006
Location: On Toast
Posted: 28th Feb 2014 01:27
Link
Okay... so is the problem because when you flip a coin twice they are not repeats of the same exact scenario? There are always hidden variables. Therefore, recreating a scenario with the exact same probabilities is impossible. And if you cannot control the probabilities to keep them the same between two events you equally cannot balance the probabilities to average out over a sample of any size.

Does this mean true randomness does not exist at all, not even in theory?

Formerly OBese87.
Back to top
Profile PM Email
Dark Java Dude 64
Community Leader
13
Years of Service
User Offline
Joined: 21st Sep 2010
Location: Neither here nor there nor anywhere
Posted: 28th Feb 2014 01:59
Link
I'm not sure if factors and variables matter so much to randomness. The definition I have heard is that, if you can look at all of the random values generated in a series, and there is no way at all to predict what the next value shall be, then the series is random.

Back to top
Profile PM Website
easter bunny
11
Years of Service
User Offline
Joined: 20th Nov 2012
Playing: Dota 2
Posted: 28th Feb 2014 02:02
Link
Quote: "Does this mean true randomness does not exist at all, not even in theory? "

In fact, I believe the only place where true randomness actually occurs is in Quantum Mechanics


Audacia Games - Facebook
Back to top
Profile PM Email
Indicium
15
Years of Service
User Offline
Joined: 26th May 2008
Location:
Posted: 28th Feb 2014 02:40
Link
Quote: "The future is already written."


If you subscribe to newtonian physics only - I was under the impression that quantum physics blows this theory out of the water.


They see me coding, they hating. http://indi-indicium.blogspot.co.uk/
Back to top
Profile PM
easter bunny
11
Years of Service
User Offline
Joined: 20th Nov 2012
Playing: Dota 2
Posted: 28th Feb 2014 03:29
Link
That's what I said


Audacia Games - Facebook
Back to top
Profile PM Email
Indicium
15
Years of Service
User Offline
Joined: 26th May 2008
Location:
Posted: 28th Feb 2014 03:51
Link
I do apologise, I skimmed and missed that. You could take it as reinforcement of your ideas though.


They see me coding, they hating. http://indi-indicium.blogspot.co.uk/
Back to top
Profile PM
nonZero
12
Years of Service
User Offline
Joined: 10th Jul 2011
Location: Dark Empire HQ, Otherworld, Silent Hill
Posted: 28th Feb 2014 09:49 Edited at: 28th Feb 2014 09:53
Link
Quote: "...you had no way of knowing..."

Maybe I did, and if not, it's still feasible that someone else could draw on every factor to predict this.

Quote: "If that were true we wouldn't have evolved awareness..."

Who says we're aware? Can you prove your awareness to anyone but yourself, and even so, can you prove these are your thoughts?

Quote: "was under the impression that quantum physics blows this theory out of the water."

Unless all percieved outcomes all predetermined. Also bare in mind there is no reason why all possible outcomes aren't all predetermined in varying branches. That said, everything exists.

This thought is definitely scary, as is fate and especially lack of true awareness, so I generally choose not to believe them because they don't "feel" right. I'm supposing this feeling towards what I've said is likely an indication of something else. I went through a phase of waking up some nights in total fear and depression at the thought of my "feeling" just being a construct -- along with my current emotions. Spells of this and depression often reared their ugly heads. Then I realised that the answer was that it didn't matter. So life was life, mysterious or a predictable and I was me, a puppet or a sentience. I know it's kinda an easy out, but it beats the alternative of insanity.

ver 7.5 /// int 145 /// str 45 /// dex 85 /// end 200 /// mat 3
Back to top
Profile PM Email Website
Mobiius
Valued Member
21
Years of Service
User Offline
Joined: 27th Feb 2003
Location: The Cold North
Posted: 28th Feb 2014 19:20 Edited at: 28th Feb 2014 19:20
Link
If C is infinite, The answer is -(1/12)


Now Visit My Website
Back to top
Profile PM Email Website
Dark Java Dude 64
Community Leader
13
Years of Service
User Offline
Joined: 21st Sep 2010
Location: Neither here nor there nor anywhere
Posted: 28th Feb 2014 23:21 Edited at: 1st Mar 2014 08:58
Link
Quote: "The answer is -(1/12)"




Back to top
Profile PM Website
Back to top

Login to post a reply

Server time is: 2024-05-04 11:17:26
Your offset time is: 2024-05-04 11:17:26