It is not mathematically sound to do statistics with a random number generator. Computers do not actually generate random numbers, but instead, they can only make pseudo-random numbers that have a certain distribution.
Any 'simulation' done in this way will always have a bias.
In order to get correct statistics, you must actually compute the statistics. Sure, the proper way to put it mathematically would have been "we did a Monte-Carlo based simulation of the probability distribution of the longest hitting streak under our model due to the intractability of direct computation", but this is an editorial in the New York Times, not a mathematical journal!
As a side note, just because a computation is performed on a set of pseudorandom numbers does not mean it is biased...usually the whole point of pseudorandomness is that the discrepancy between computations involving them and identical computations involving true random numbers will typically be quite small.
From the descriptions I've seen of their research, it seems that they're treating all games identically for the purpose of determining a typical season's behavior. While this may me necessary to make the computation tractable, it's not realistic, and introduces a sizable bias towards long hitting streaks.
In reality, a league is typically very imbalanced from team to team and from pitcher to pitcher (probably even more so in the game of the early 20th century than now). It's easier to get hits off of two successive average pitchers than it is to get hits both off of a very good and a very bad pitcher. For example (to oversimplify a good deal):
Say the league is split 50/50 between "good" pitchers (pitchers you'll get a hit off of 50% of games) and "bad" pitchers (pitchers you'll get a hit off of 80% of games). In a typical 20 game stretch, you'll encounter 10 good pitchers and 10 bad ones, and your odds of getting a hit in all 20 games would be (0.50)^10(0.80)^10, about 1/9537.
Under their analyis as I understand it, they'd replace all the pitchers by mediocre pitchers who you'd get a hit off of 65% of the time, and your odds would be (0.65)^20, about 1/5517.
This one assumption almost doubled your chances of getting a hit in all 20 games.
There are other biases as well going the other way (ignoring the effect of hitting slumps, for example), but this one jumped out at me.
"-Isn't the "out-degree 2" restriction an obstruction as well? Would the proof work for more general graphs, with a different out-degree for each node, or even for different out-degrees for different nodes?"
I'm not sure how big a restriction this is. Say, for example, node A was actually connected to nodes B,C,D,E. I would just replace A with four new cities A1, A2, A3, and A4. A1 would connect to A2 and B, A2 would connect to A3 and C, and A4 would connect to D and E. Whatever directions I gave on this new map would work for the old one as well.
I'll have increased the size of the network by a good deal, but this may not pose too much of a problem if the algorithm is fast enough.
"- Is the algorithm incremental? i.e. could you maintain a previous coloring and build on it as you add more nodes to the graph? I'm guessing that it would be the case if the proof is by induction on the number of nodes, right?"
I'm not sure. The paper makes some reference to the eigenvectors of the graph, which don't necessarily behave well under adding more nodes. I don't know whether they're used in the algorithm itself or just in the proof though (I haven't examined the paper in detail).
The question behind road coloring is this: Given a directed network with out-degree 2 (from any place you can get to exactly two other places), we want to color the edges leading out of each node red or blue so the following "universal directions" condition exists:
For any final destination A, there is a set of directions (e.g. take red three times, then blue twice, then red again) that gets you to A no matter where you started from. It may not be the shortest path, but you'll get there.
There is one obvious obstruction and one slightly less obvious obstruction: If your network is disconnected so you can't get to A from your starting point no matter what path you follow, you're clearly stuck. On the other hand, there's also a "periodicity" obstruction if all of the cycles of the graph are multiples of the same number. For example, suppose that you were trying to give universal directions for a square, where the roads in question connected every vertex to its two neighbors. If I want to go from my starting point to an adjacent vertex, I have to take an odd number of steps. If I want to go from my starting point to the opposite vertex, I have to take an even number of steps. This means I can't even know how many steps I have to take (let along which steps) unless I knew where I started.
It was conjectured, and Trahtman showed, that these two are the only possible obstructions. In particular, he even gives an algorithm for figuring out how to label the roads quickly.
I guess the applications I'd see in this are for algorithms and the design of autonomous systems. The idea here is that, if the robot gets stuck somewhere in a multi-step procedure, you may want it to restart from the beginning. However, this can be difficult if the robot does not know where it is in the procedure, or even where it is physically. Trahtman's algorithm could allow you to exchange some computation at the beginning of the procedure (which can be done before the robot goes out, for example), for this "reset" functionality. I don't know whether this is feasible or not though.
I think the culprit may be that they divided fixed-line telephones and mobile telephones into two separate categories for the survey, but kept e-mail as a single category.
If they had made a survey where the phones were kept as a single category but e-mail was divided into two categories (say a company sponsored server vs. a third party e-mail service like Yahoo) the results would probably have been reversed.
"If I ever wanted to commit fraud in the election system, I would have. And that would not need to involve hacking a machine"
The catch is, the fraud that you would be committing (registering as a non-citizen) would only affect the election by at most 1 vote, and that single vote is quite unlikely to change the election.
The danger in using insecure voting machines is that a single fraudster can swing an election by many votes, making it much more likely that their intervention affected the final outcome.
"Andrus said a friend of his who owned a restaurant that did not feature music was contacted by a company looking to charge him because it owned the rights to a Hank Williams Jr. song, "Are You Ready for Some Football?" The song preceded every "Monday Night Football" telecast, which the restaurant carried on its televisions."
In this situation in particular my suspicion is the friend was being shaken down by a fraudster who didn't really own the rights to the song, but was playing off of restaurants' fear of lawsuits.
Shouldn't licensing to the song have been included in the licensing fee the restaurant paid to publicly show "Monday Night Football" (the show already having paid a licensing fee to use the song)?
Something seems strange with the move numbers
on
Celebrating Puzzles
·
· Score: 3, Interesting
The 65 ring puzzle is claimed to take what turns out to be exactly 2^64 moves. This makes some sense sense for a recursive puzzle, since we could be in a situation where the two ring puzzle finishes in 1 move and each additional ring doubles the length.
However, it's not consistent with the 9 move puzzle, which is supposed to require 341 (2^8+2^6+2^4+2^2+1) moves. Perhaps the 65 ring puzzle instead requires 2^64+2^62+2^60+...+2^2+1=24,595,658,764,946,068,82 1 moves to solve?
They're not quite science, but all 4 papers I tried from the Postmodernism Generator at http://www.elsewhere.org/pomo were classified as authentic, though with a lower score than my Stochastic Processes homework was (between 75 and 91%)
1: Love.
1: Hate.
2: Love hate.
3: Hate love hate.
5: Love hate hate love hate.
8: Hate love hate love hate hate love hate.
13: Love hate hate love hate hate love hate love hate hate love hate.
Why just add syllables when you can add entire lines?
To quote "The Right Stuff" (the movie, not the book): "You know, I went to my high school reunion and all my old girlfriends were talking about how cut throat and stressful their husband's lives were. I wonder how they would feel if when their husbands left for work in the morning, there was a one in four chance he might get killed."
I don't know how close that one in four odds are to being accurate, but back in those days the death rate among test pilots was frightfully high. And yet they continued doing it, and it is due to those pilots that we are in space now.
How much is space worth to us? Is it worth the ~2% chance (based on what's happened in the past) of a shuttle disaster? If we can't lower that risk below 2%, should we never leave this planet again?
One thing I find surprising is that bluesq.com is still allowing betting on the plot points of the new book (the identity of the half blood prince and which character dies). Enough people by now have had access to copies of the novel that it would seem likely that one or more of them could make a killing by betting large sums of money on the characters in question with no risk whatsoever.
You can see the current odds at http://www.bluesq.com/bet?action=go_events&type_id =2099 (spoiler warning: by this point one character is a VERY heavy favorite, so it's quite possible that he is the person going to die and people have already made inside bets)
One person definitely can kill a company
on
A $251 Million Typo
·
· Score: 1
As the case of Barings Bank, which was wiped out after 233 years of business after it gave Nick Leeson a bit too much trading authority. It only took a couple years for Leeson to run up losses of $1.3 billion on the futures market.
The problem as they describe it (find the shortest possible route through all the locations) is, as far as I know, NOT easy checkable in the way they describe.
If I recall correctly, NP actually describes a set of decision problems for which a positive answer is very easily checkable, but a negative answer might or might not be.
For example, take the question "Is a number composite?". If the answer is yes, it is possible to find a certificate of compositeness (in this case the two factors) that can be used to confirm the result very quickly. However, for a long time it was unknown whether a fast test existed to test the negative of that result (though a polynomial time certificate of primality has recently been found).
In the travelling salesman case, the proper formulation for an NP problem would be "Given a set of distances and a number x, is there a cycle visiting all the vertices with total length less than x?" Now there is a certificate for a positive answer (the cycle in question), but a certificate of the negative result is much harder to come by.
"I find it really sad to consider that a person almost died and that the "positive outcome" is that he returned to work."
Would you have preferred it if the outcome was "The patient responded well to the treatment immediately, but was unable to regain enough of his normal life to return to work"?
All those numbers tell us is that the average Japanese student is more mathematically literate than the average student from the U.S., France, Denmark, etc. (Russia's not even mentioned).
However, the hacking in question would be done instead by the few most proficient hackers (who might or might not be the most proficient mathematically), and certainly not by the hypothetical "average".
Perhaps people here would be more interested
on
Math Awareness Month
·
· Score: 1
was a similar comment made by Lyndon Johnson ("If one morning I walked on top of the water across the Potomac River, the headline that afternoon would read "President Can't Swim").
Interesting that people are now modifying that quote to talk about bias form the Liberal side now.
Actually, the site was experiencing difficulties with high traffic before it got mentioned here (possibly due to its mention on the NY Times site yesterday?)
And at the same time you've seen your cable bill drop since those same idiots are subsidizing your Food Network watching.
A la Carte will lower your bill and the channels you don't watch, but it will also raise your bill for the channels you do watch. Are you absolutely certain the costs won't outweigh the benefits?
"both are renowned scientific institutions that gain reputation not by doing everything as fast as possible, but as accurately and precisely as possible"
I think NASA would have done well to remember that fact. When they focused too much on the outer words in the phrase "Faster, Better, Cheaper" a few years ago the results ended up being a probe that crashed into Mars instead of landing on it.
Slashdot Mirror
From the descriptions I've seen of their research, it seems that they're treating all games identically for the purpose of determining a typical season's behavior. While this may me necessary to make the computation tractable, it's not realistic, and introduces a sizable bias towards long hitting streaks.
In reality, a league is typically very imbalanced from team to team and from pitcher to pitcher (probably even more so in the game of the early 20th century than now). It's easier to get hits off of two successive average pitchers than it is to get hits both off of a very good and a very bad pitcher. For example (to oversimplify a good deal):
Say the league is split 50/50 between "good" pitchers (pitchers you'll get a hit off of 50% of games) and "bad" pitchers (pitchers you'll get a hit off of 80% of games). In a typical 20 game stretch, you'll encounter 10 good pitchers and 10 bad ones, and your odds of getting a hit in all 20 games would be (0.50)^10(0.80)^10, about 1/9537.
Under their analyis as I understand it, they'd replace all the pitchers by mediocre pitchers who you'd get a hit off of 65% of the time, and your odds would be (0.65)^20, about 1/5517.
This one assumption almost doubled your chances of getting a hit in all 20 games.
There are other biases as well going the other way (ignoring the effect of hitting slumps, for example), but this one jumped out at me.
"-Isn't the "out-degree 2" restriction an obstruction as well? Would the proof work for more general graphs, with a different out-degree for each node, or even for different out-degrees for different nodes?"
I'm not sure how big a restriction this is. Say, for example, node A was actually connected to nodes B,C,D,E. I would just replace A with four new cities A1, A2, A3, and A4. A1 would connect to A2 and B, A2 would connect to A3 and C, and A4 would connect to D and E. Whatever directions I gave on this new map would work for the old one as well.
I'll have increased the size of the network by a good deal, but this may not pose too much of a problem if the algorithm is fast enough.
"- Is the algorithm incremental? i.e. could you maintain a previous coloring and build on it as you add more nodes to the graph? I'm guessing that it would be the case if the proof is by induction on the number of nodes, right?"
I'm not sure. The paper makes some reference to the eigenvectors of the graph, which don't necessarily behave well under adding more nodes. I don't know whether they're used in the algorithm itself or just in the proof though (I haven't examined the paper in detail).
The question behind road coloring is this: Given a directed network with out-degree 2 (from any place you can get to exactly two other places), we want to color the edges leading out of each node red or blue so the following "universal directions" condition exists: For any final destination A, there is a set of directions (e.g. take red three times, then blue twice, then red again) that gets you to A no matter where you started from. It may not be the shortest path, but you'll get there. There is one obvious obstruction and one slightly less obvious obstruction: If your network is disconnected so you can't get to A from your starting point no matter what path you follow, you're clearly stuck. On the other hand, there's also a "periodicity" obstruction if all of the cycles of the graph are multiples of the same number. For example, suppose that you were trying to give universal directions for a square, where the roads in question connected every vertex to its two neighbors. If I want to go from my starting point to an adjacent vertex, I have to take an odd number of steps. If I want to go from my starting point to the opposite vertex, I have to take an even number of steps. This means I can't even know how many steps I have to take (let along which steps) unless I knew where I started. It was conjectured, and Trahtman showed, that these two are the only possible obstructions. In particular, he even gives an algorithm for figuring out how to label the roads quickly. I guess the applications I'd see in this are for algorithms and the design of autonomous systems. The idea here is that, if the robot gets stuck somewhere in a multi-step procedure, you may want it to restart from the beginning. However, this can be difficult if the robot does not know where it is in the procedure, or even where it is physically. Trahtman's algorithm could allow you to exchange some computation at the beginning of the procedure (which can be done before the robot goes out, for example), for this "reset" functionality. I don't know whether this is feasible or not though.
I think the culprit may be that they divided fixed-line telephones and mobile telephones into two separate categories for the survey, but kept e-mail as a single category.
If they had made a survey where the phones were kept as a single category but e-mail was divided into two categories (say a company sponsored server vs. a third party e-mail service like Yahoo) the results would probably have been reversed.
"If I ever wanted to commit fraud in the election system, I would have. And that would not need to involve hacking a machine"
The catch is, the fraud that you would be committing (registering as a non-citizen) would only affect the election by at most 1 vote, and that single vote is quite unlikely to change the election.
The danger in using insecure voting machines is that a single fraudster can swing an election by many votes, making it much more likely that their intervention affected the final outcome.
"Andrus said a friend of his who owned a restaurant that did not feature music was contacted by a company looking to charge him because it owned the rights to a Hank Williams Jr. song, "Are You Ready for Some Football?" The song preceded every "Monday Night Football" telecast, which the restaurant carried on its televisions."
In this situation in particular my suspicion is the friend was being shaken down by a fraudster who didn't really own the rights to the song, but was playing off of restaurants' fear of lawsuits.
Shouldn't licensing to the song have been included in the licensing fee the restaurant paid to publicly show "Monday Night Football" (the show already having paid a licensing fee to use the song)?
The 65 ring puzzle is claimed to take what turns out to be exactly 2^64 moves. This makes some sense sense for a recursive puzzle, since we could be in a situation where the two ring puzzle finishes in 1 move and each additional ring doubles the length.
2 1 moves to solve?
However, it's not consistent with the 9 move puzzle, which is supposed to require 341 (2^8+2^6+2^4+2^2+1) moves. Perhaps the 65 ring puzzle instead requires 2^64+2^62+2^60+...+2^2+1=24,595,658,764,946,068,8
They're not quite science, but all 4 papers I tried from the Postmodernism Generator at http://www.elsewhere.org/pomo were classified as authentic, though with a lower score than my Stochastic Processes homework was (between 75 and 91%)
1: Love. 1: Hate. 2: Love hate. 3: Hate love hate. 5: Love hate hate love hate. 8: Hate love hate love hate hate love hate. 13: Love hate hate love hate hate love hate love hate hate love hate. Why just add syllables when you can add entire lines?
The New York Times has their obituary up for him at http://www.nytimes.com/2005/09/04/politics/04REHNQ UIST.OBIT.WEB.html?pagewanted=all.
Registration required as usual, but this seems of high enough quality to make it worthwhile.
To quote "The Right Stuff" (the movie, not the book): "You know, I went to my high school reunion and all my old girlfriends were talking about how cut throat and stressful their husband's lives were. I wonder how they would feel if when their husbands left for work in the morning, there was a one in four chance he might get killed."
I don't know how close that one in four odds are to being accurate, but back in those days the death rate among test pilots was frightfully high. And yet they continued doing it, and it is due to those pilots that we are in space now.
How much is space worth to us? Is it worth the ~2% chance (based on what's happened in the past) of a shuttle disaster? If we can't lower that risk below 2%, should we never leave this planet again?
One thing I find surprising is that bluesq.com is still allowing betting on the plot points of the new book (the identity of the half blood prince and which character dies). Enough people by now have had access to copies of the novel that it would seem likely that one or more of them could make a killing by betting large sums of money on the characters in question with no risk whatsoever.
d =2099 (spoiler warning: by this point one character is a VERY heavy favorite, so it's quite possible that he is the person going to die and people have already made inside bets)
You can see the current odds at http://www.bluesq.com/bet?action=go_events&type_i
As the case of Barings Bank, which was wiped out after 233 years of business after it gave Nick Leeson a bit too much trading authority. It only took a couple years for Leeson to run up losses of $1.3 billion on the futures market.
s html for more details on his story.
See http://www.bbc.co.uk/crime/caseclosed/nickleeson.
It depends on the form you put the problem.
The problem as they describe it (find the shortest possible route through all the locations) is, as far as I know, NOT easy checkable in the way they describe.
If I recall correctly, NP actually describes a set of decision problems for which a positive answer is very easily checkable, but a negative answer might or might not be.
For example, take the question "Is a number composite?". If the answer is yes, it is possible to find a certificate of compositeness (in this case the two factors) that can be used to confirm the result very quickly. However, for a long time it was unknown whether a fast test existed to test the negative of that result (though a polynomial time certificate of primality has recently been found).
In the travelling salesman case, the proper formulation for an NP problem would be "Given a set of distances and a number x, is there a cycle visiting all the vertices with total length less than x?" Now there is a certificate for a positive answer (the cycle in question), but a certificate of the negative result is much harder to come by.
"I find it really sad to consider that a person almost died and that the "positive outcome" is that he returned to work."
Would you have preferred it if the outcome was "The patient responded well to the treatment immediately, but was unable to regain enough of his normal life to return to work"?
Unfortunately, in a correctly performed test 50% participants would unknowingly be stuck with a placebo instead of the real thing.
Worse yet, they may suffer some sort of placebo effect.
All those numbers tell us is that the average Japanese student is more mathematically literate than the average student from the U.S., France, Denmark, etc. (Russia's not even mentioned). However, the hacking in question would be done instead by the few most proficient hackers (who might or might not be the most proficient mathematically), and certainly not by the hypothetical "average".
in last year's topic on the mathematics of (mostly large scale) networks. http://www.mathaware.org/mam/04/index.html
was a similar comment made by Lyndon Johnson ("If one morning I walked on top of the water across the Potomac River, the headline that afternoon would read "President Can't Swim").
Interesting that people are now modifying that quote to talk about bias form the Liberal side now.
Actually, the site was experiencing difficulties with high traffic before it got mentioned here (possibly due to its mention on the NY Times site yesterday?)
And at the same time you've seen your cable bill drop since those same idiots are subsidizing your Food Network watching.
A la Carte will lower your bill and the channels you don't watch, but it will also raise your bill for the channels you do watch. Are you absolutely certain the costs won't outweigh the benefits?
"Evil lurks in the datalinks as it lurked in the streets of yesteryear.
But it was never the streets that were evil"
(spoken by Sister Miriam as an introduction to her character in Sid Meier's Alpha Centauri)
"both are renowned scientific institutions that gain reputation not by doing everything as fast as possible, but as accurately and precisely as possible"
I think NASA would have done well to remember that fact. When they focused too much on the outer words in the phrase "Faster, Better, Cheaper" a few years ago the results ended up being a probe that crashed into Mars instead of landing on it.