Forbidden subwords -- logic vs intuition

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

Forbidden subwords -- logic vs intuition

Postby skullturf » Thu Dec 02, 2010 2:05 am UTC

One thing in mathematics that can be frustrating, but also very interesting, goes something as follows. You're trying to decide which of two competing statements, P or Q, is true. At first, your intuition tells you the correct answer is probably P. Later, you discover a proof (yours or someone else's) that in fact, Q is true and P is false. If the proof is sound, then in a sense, that's the end of the issue. But sometimes, even if you have no doubt that the proof is sound, something still feels a little "unresolved". Why did my intuition think it was P? How can I reconcile this?

From one point of view, this may sound a little silly -- a proof is a proof, right? Once you've proved something, what else is there to say? But sometimes, rather than just saying "Okay, problem solved, so I just throw away my original intuition and never think of it again", we feel the need to "work on" that original intuition -- how do I come up with a new informal, imprecise, intuitive way of looking at things in order to try to convince my intuition that the correct answer is Q?

Here's an example that sort of qualifies for me.

Spoiler:
You have a balanced 26-sided die, whose faces are labeled with the letters of the alphabet. If you roll the die n times and generate an n-letter "word", what's more likely: that the word contains XX as a subword, or that the word contains XY as a subword?

Consider n = 3.

There are 26^3 possible words. How many of them contain XY as a subword? There are 26 words of the form XY*, and 26 of the form *XY. So the probability of containing XY as a subword is 2*26/26^3.

How many words contain XX as a subword? There are 26 words of the form XX*. There are 26 of the form *XX, but there are 2*26-1 such words altogether, because we counted the word XXX twice.

So (at least for words of length 3) for a randomly generated word, the probability of containing XY as a subword is slightly higher than the probability of containing XX as a subword. (As it turns out, that trend continues for larger n.)

Roughly paraphrasing the argument, XY is more likely because it can't overlap with itself.

At first, I had a really hard time wrapping my mind around that and making it intuitive. How on earth does the fact that the word doesn't overlap with itself make it "more likely"? It almost seemed like, if anything, the word that can overlap with itself should be "more likely".


I wrestled with this for a little while and managed to change my intuition a bit. I can maybe post some remarks later about that, but I thought there was a chance that people here might want to wrestle with this one. And I hope you think the question in general is an interesting one -- what are some tricks for changing your intuition so it conforms with the facts? Can you think of other interesting examples from your own experience?

pizzazz
Posts: 487
Joined: Fri Mar 12, 2010 4:44 pm UTC

Re: Forbidden subwords -- logic vs intuition

Postby pizzazz » Thu Dec 02, 2010 3:35 am UTC

I guess as an "intuitive" explanation, one could say that there is a smaller probability of XX in any given set of 3 rolls because XXX contains two such pairs (XX* and *XX) in one roll, but it only counts as one roll. So there are just as many XX as XY, but there are one fewer rolls that produce XX than XY, because two of those XX's come on the same roll, leaving one roll for XY that doesn't have a matching XX.

As far as other unintuitive problems go, I actually never had trouble accepting the solution to the Monty Hall problem (your first pick has 1/3 chance, your second 1/2), but I still wrestle with the boy/girl problem.

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

Re: Forbidden subwords -- logic vs intuition

Postby skullturf » Thu Dec 02, 2010 3:58 am UTC

Yeah, that's similar to how I eventually managed to convince myself.

Here's an analogy I thought of:

Suppose your city has exactly the same number of cats as dogs. So if you throw a dart at a random spot in your city, you're just as likely to hit a cat as a dog. (Let's pretend cats and dogs are the same size.)

Now suppose your city has a rule that you're not allowed more than two dogs in the same household, but there's no similar restriction on cats.

This means it's possible to have a bunch of cats together in the same house. If you notice these "clumps" of cats, then superficially, you might think something like, "Where there's one or two cats, there can be more. Since it's possible to have more cats, it kind of looks like cats are more likely."

But if you randomly select a household, the chance it contains at least one dog is greater than the chance it contains at least one cat. This is precisely because of the "clumping".

Edit: Oooh, and speaking of the boy/girl problem, the versions that really blow my mind are the ones where they specify a child's name, or the day of the week they were born.

User avatar
Blatm
Posts: 638
Joined: Mon Jun 04, 2007 1:43 am UTC

Re: Forbidden subwords -- logic vs intuition

Postby Blatm » Thu Dec 02, 2010 4:01 am UTC

pizzazz wrote:the Monty Hall problem (your first pick has 1/3 chance, your second 1/2)


If you switch doors, you win 2/3rds of the time, not 1/2 the time.

pizzazz
Posts: 487
Joined: Fri Mar 12, 2010 4:44 pm UTC

Re: Forbidden subwords -- logic vs intuition

Postby pizzazz » Thu Dec 02, 2010 4:25 am UTC

Blatm wrote:
pizzazz wrote:the Monty Hall problem (your first pick has 1/3 chance, your second 1/2)


If you switch doors, you win 2/3rds of the time, not 1/2 the time.


That's what I meant to write.

++$_
Mo' Money
Posts: 2370
Joined: Thu Nov 01, 2007 4:06 am UTC

Re: Forbidden subwords -- logic vs intuition

Postby ++$_ » Thu Dec 02, 2010 6:26 am UTC

The way I deal with the boy/girl problem is to realize that the answer is really an artifact of the stupid and artificial problems we create to talk about conditional probability.

The point is that the situation in which you know that one child is a boy, but not which one, never comes up in real life. People do not go around saying "I have two children and at least one is a girl." If making such statements were a daily ritual among people with two children, at least one of whom is a girl, then it would be true that 1/3 of the time that you hear such a statement, the other child in the family is a girl too, and I find that fact reasonably easy to accept. The reason our intuition fails is that the situation described in the problem is utterly absurd and alien from any real experience.

The "at least one of them is a girl named Florida" version of the problem is exactly in accordance with our intuition -- the answer is 50%, just like it should be. The only reason we begin to have doubts about it is that our minds have been twisted by the absurd first version of the problem. (Of course, there is something slightly fishy about "at least one of them is a girl named Florida" -- there could be two Floridas -- so the probability is actually slightly less than 50% if some people like naming both of their daughters after the same state.)

User avatar
RogerMurdock
Posts: 158
Joined: Mon Jul 27, 2009 10:35 pm UTC

Re: Forbidden subwords -- logic vs intuition

Postby RogerMurdock » Thu Dec 02, 2010 7:44 am UTC

I do this with most math/physics things I learn. I try to understand them at an intuitive level, so that next time I have a new problem I can look at it quickly and understand what is going on.

Sadly, sometimes it's hard to communicate this desire to "really understand" what I'm learning to the teacher. Case in point: my mechanics class last year. Solutions would be provided to problems but I would still be asking questions about the general nature of things. My teacher would be exasperated, telling me "What don't you understand in my solution???", and I would have to explain every step made sense, but I didn't really feel like it should and hence it was not satisfying. Once you do get an intuitive grasp of a new concept though, oh boy is it worth it. Suddenly seemingly random mathematical operations appear to be small leaps of logic.

User avatar
Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: Forbidden subwords -- logic vs intuition

Postby Talith » Thu Dec 02, 2010 12:58 pm UTC

I think probability in particular is one field full of these kinds of examples. My way of 'rationalising' the Monty Hall's problem is to think of the similar problem with 100 doors, the host opens 98 doors that don't have a goat behind, should you change your answer? Well of course! It's simple to see why now. I don't know why the solution seems so much less obvious with only 3 doors, perhaps it's because of how much closer to each other the involved chances are in the 3 door problem. I think It's probably the sign of maturation as a mathematician when you can learn to only use your intuition to make conjectures and then follow where the proof leads, not worrying if it 'doesn't seem right'.

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

Re: Forbidden subwords -- logic vs intuition

Postby skullturf » Thu Dec 02, 2010 3:02 pm UTC

++$_ wrote:The point is that the situation in which you know that one child is a boy, but not which one, never comes up in real life. People do not go around saying "I have two children and at least one is a girl." If making such statements were a daily ritual among people with two children, at least one of whom is a girl, then it would be true that 1/3 of the time that you hear such a statement, the other child in the family is a girl too, and I find that fact reasonably easy to accept. The reason our intuition fails is that the situation described in the problem is utterly absurd and alien from any real experience.


I agree, and in the days of the week example, that's even more true.

With "at least one of them is a girl", you can kinda sorta think up situations where it's not totally unrealistic. Suppose I know my co-worker Lou has exactly two children, but I know absolutely nothing else about them. Then one day, I happen to mention to him, "I was reading this interesting article about the challenges of a father raising a daughter" and he says "Oh, cool, I'd like to look at that." If I take that as implying he has at least one daughter, what's the probability he has two daughters?

To make these problems more "intuitive", it may help to remember: probability in this context is just proportions, and it matters what set you're selecting from.

I would likely never say to Lou, "I was reading an article about the challenges of raising a daughter who was born on Tuesday."

But if you got all parents of exactly two children to gather together in the Superdome, and if you said "If at least one of your two children is a girl born on a Tuesday, stand up", and if you then ask "Among the people who are now standing, what proportion have such-and-such property?" -- then the answer is whatever a counting argument says it is. And since this isn't an everyday situation, our everyday intuition isn't much help.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Forbidden subwords -- logic vs intuition

Postby skeptical scientist » Thu Dec 02, 2010 7:57 pm UTC

I think a first useful step is to figure out precisely why your intuition was that P was true, and to what extent this intuition is actually true. Then you can figure out what went wrong with your intuition.

For example, with the occurrences of XX/XY problem, your intuition was that XX and XY should each appear in the same fraction of n letter words. The true statement that suggested this false intuition is that the number of occurrences of XX and the number of occurrences of XY among the set of all n letter words is the same - both occur exactly (n-1)26n-2 times among the 26n words of length n. The reason they don't occur in the same fraction of words is that the average number of XX occurrences in words containing XX is greater than the average number of XY occurrences in words containing XY. This is not terribly surprising, given that XY can occur at most n/2 times (in the word XYXYXY...), but XX can occur as often as n-1 times (in the word XXX...). From these two entirely believable (and true) statements, we can conclude that XX should appear in fewer words than XY, but occur more times (on average) when it does appear.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
nehpest
Posts: 518
Joined: Fri Jun 12, 2009 9:25 pm UTC

Re: Forbidden subwords -- logic vs intuition

Postby nehpest » Fri Dec 03, 2010 12:38 am UTC

I have had similar feelings, OP. For me, it was Godel's incompleteness theorem. I follow the logic (at least, as explained by Doug Hofstadter) and I accept and agree that it's true, but I find it unsatisfying on an emotional level. It doesn't seem "right" to me that math should have holes in it, especially holes that can't possibly be fixed.
Kewangji wrote:Someone told me I need to stop being so arrogant. Like I'd care about their plebeian opinions.

blag

ahazaq2
Posts: 36
Joined: Sun May 16, 2010 6:27 pm UTC

Re: Forbidden subwords -- logic vs intuition

Postby ahazaq2 » Fri Dec 03, 2010 3:46 am UTC

I vote product rule.

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

Re: Forbidden subwords -- logic vs intuition

Postby skullturf » Fri Dec 03, 2010 3:59 am UTC

ahazaq2 wrote:I vote product rule.


Drawing a rectangle might help. Say its sides are u and v.

So its current area is uv. How does the area change if both u and v are changing by small amounts du and dv respectively?

If du and dv are both positive, we've added three things:

--a strip of dimensions u times dv
--a strip of dimensions v times du
--a very small corner whose dimensions are du times dv, and is hence very very small.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Forbidden subwords -- logic vs intuition

Postby Yakk » Fri Dec 03, 2010 4:51 pm UTC

skullturf, back to that subword...

The fact that they are compatible doesn't help. Because if you have the word already, you don't care that "other instances are blocked". You already have the subword.

The fact that XX 'self-overlaps' actually causes a problem. With 3 dice, an X or Y in the 2nd location has the chance to generate an XY subword (either side) -- but only the X has a chance to generate an XX subword.

Another way to give your intuition a break is to simplify. A simple simplification is dropping the letter count to 2 -- but that ends up not working. In this case, dropping the letter count to 2 helps more.

Once you grasp the simpler case, examine what happens when you make it more complex.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 12 guests