Test Your Intuition (10): How Does “Random Noise” Look Like.

This is a bit unusual post in the “test your intuition” corner as the problem is not entirely formal.  

How does random noise in the digital world typically look?

Suppose you have a memory of n bits, or a memory based on a larger r-letters alphabet, and suppose that a “random noise” hits the memory in such a way that the probability of each bit being affected is t.

What will be the typical behavior of such a random digital noise? Part of the question is to define “random noise” in the best way possible, and then answer it for this definition.

The source of this question is an easy fact about quantum memory which asserts that if you consider a random noise operation acting on a quantum memory with n qubits, and if the probability that every qubit is damaged is a tiny real number t, then typically the noise  has the following form: with large probability nothing happens and with tiny probability (a constant times t) a large fraction of qubits are harmed.

 I made one try for the digital (binary) question but I am not sure at all that it is the “correct” definition for what “random noise” is.

(Maybe I should try to ask the problem also on “math overflow“. See also here, here and here for what math overflow is.)

Test Your Intuition #9 (answer to #9),  #8  (answer),   #7,   #6,  #5,  #4 (answer), #3 (answer), #2,  #1.

Home

I just came back home after two months in the US, mainly in and around New Haven and also in IPAM (Los Angeles) and Texas A&M. I heard all sort of wonderful things (but some sad news as well). I met a lot of friends and quite a few new people (including quite a few fellow bloggers). I was a bit slow on blogging but I do plan to catch up.

I need help from technically savvy readers for the following Audio project.

The Polynomial Hirsch Conjecture: Discussion Thread, Continued

Here is a  link for the just-posted paper Diameter of Polyhedra: The Limits of Abstraction by Freidrich Eisenbrand, Nicolai Hahnle,  Sasha Razborov, and Thomas Rothvoss.

And here is a link to the paper  by Sandeep Koranne and Anand Kulkarni “The d-step Conjecture is Almost true”  – most of the discussion so far was in this direction.

We had a long and interesting discussion regarding the Hirsch conjecture and I would like to continue the discussion here.  

The way I regard the open collaborative efforts is as an open collective attempt to discuss and make progress on the problem (and to raise more problems), and also as a way to assist people who think or work (or will think or will work) on these problems on their own.

Most of the discussion in the previous thread was not about the various problems suggested there but rather was about trying to prove the Hirsch Conjecture precisely! In particular, the approach of Sandeep Koranne and Anand Kulkarni which attempts to prove the conjecture using “flips” (closely related to Pachner moves, or bistaller operations) was extensively discussed.  Here is the link to another paper by Koranne and Kulkarni ”Combinatorial Polytope Enumeration“. There is certainly more to be understood regarding flips, Pachner moves, the diameter, and related notions. For example, I was curious about for which Pachner moves  ”vertex decomposibility” (a strong form of shellability known to imply the Hirsch bound) is preserved. We also briefly discussed metric aspects of the Hirsch conjecture and random polytopes.

For general background: Here is a  chapter that I wrote about graphs, skeleta and paths of polytopes. Some papers on polytopes on Gunter Ziegler’s homepage  describe very interesting and possibly relevant current research in this area. Here is a  link to Eddie Kim and Francisco Santos’s survey article on the Hirsch Conjecture. 

Here is a link from the open problem garden to the continuous analog of the Hirsch conjecture proposed by Antoine Deza, Tamas Terlaky, and  Yuriy Zinchenko.

Chomskian Linguistics

Here is another little chapterette from my book. It follows a chapter based on discussions that followed a post by David Corfield from n-Category Cafe. There, the following thought was raised: Is there something analogous to Chomsy’s theory of language’s structure and language acquisition when it comes to mathematics. One interesting aspects is trying to understand “dyscalculia” which is a term describing children’s learning disabilities in mathematics. 

(Eran Nevo) The g-Conjecture III: Algebraic Shifting

This is the third in a series of posts by Eran Nevo on the g-conjecture. Eran’s first post was devoted to the combinatorics of the g-conjecture and was followed by a further post by me on the origin of the g-conjecture. Eran’s second post was about the commutative-algebra content of the conjecture. It described the Cohen-Macaulay property (which is largely understood and known to hold for simplicial spheres) and the Lefshetz property which is known for simplicial polytopes and is wide open for simplicial spheres.

The g-conjecture and algebraic shifting

Squeezed spheres

Back to the question from last time, Steinitz showed that

any simplicial 2-sphere is the boundary of a convex 3-polytope.

However, in higher dimension

there are many more simplicial spheres than simplicial polytopes,

on a fixed large number of vertices.

Answer to Test Your Intuition (9)

Two experimental results of 10/100 and 15/100 are not equivalent to one experiment with outcomes 3/200.

(Here is a link to the original post.)

One way to see it is to think about 100 experiments. The outcomes under the null hypothesis will be 100 numbers (more or less) uniformly distributed in [0,1]. So the product is extremely tiny.

What we have to compute is the probability that the product of two random numbers uniformly distributed in [0,1] is smaller or equal 0.015. This probability is much larger than 0.015.

Here is a useful approximation (I thank Brendan McKay for reminding me): if we have independent values in  then the prob of product is

In this case  0.015 * ( 1 – log(0.015) ) = 0.078

So the outcomes of the two experiments do not show a significant support for the theory.

The theory of hypothesis testing in statistics is quite fascinating, and of course, it became a principal tool in science and  led to major scientific revolutions. One interesting aspect is the similarity between the notion of statistical proof which is important all over science and the notion of interactive proof in computer science. Unlike mathematical proofs, statistical proof are based on following certain protocols and standing alone if you cannot guarantee that the protocol was followed the proof has little value.

Geometry and Probability

 

 

Igor Pak’s “Lectures on Discrete and Polyhedral Geometry”

Here is a link to Igor Pak’s  book on Discrete and Polyhedral Geometry  (free download) . And here is just the table of contents.

It is a wonderful book, full of gems, contains original look on many important directions, things that cannot be found elsewhere, and great beyond great pictures (which really help to understand the mathematics). Grab it!

 

Test Your Intuition (9)

Click on the picture if you wish to read about the “Mars effect”  

A) You want to test the theory that people who were born close to noon on July 7 are unusually tall. You choose randomly 100 Norwegian men over 25 years old and discover that the one person born closest to noon of 7/7 is the 15th tallest among them. Then you chose 100 Nigerian women and discover that the woman born closest to noon on July 7 is the 10th tallest. You figure out that without the putative effect being real (in other words, under the null hypothesis)  the chance for such results occuring at random is 1/10 times 3/20 which is 1.5%, and conclude that this lends significant support to your theory. Are you correct?

B) In a certain scientific area, the level of significance required for a statistical test is 5%.  Would it serve the quality of scientific papers in this area to reduce the required significance level to, say, 0.5%, in order to exclude publishing papers which report experiments that were successful by sheer chance?

The Polynomial Hirsch Conjecture: Discussion Thread

This post is devoted to the polymath-proposal about the polynomial Hirsch conjecture. My intention is to start here a discussion thread on the problem and related problems. (Perhaps identifying further interesting related problems and research directions.)

Earlier posts are: The polynomial Hirsch conjecture, a proposal for Polymath 3 , The polynomial Hirsch conjecture, a proposal for Polymath 3 cont. , The polynomial Hirsch conjecture – how to improve the upper bounds .

First, for general background: Here is a  chapter that I wrote about graphs, skeleta and paths of polytopes. Some papers on polytopes on Gunter Ziegler’s homepage  describe very interesting and possibly relevant current research in this area,  and also a few of the papers under “discrete geometry” (which follow the papers on polytopes) are relevant. Here are again links for the recent very short paper by  Freidrich Eisenbrand, Nicolai Hahnle, and Thomas Rothvoss, the 3-pages paper by Sasha Razborov,  and to Eddie Kim and Francisco Santos’s survey article on the Hirsch Conjecture.

Here are the basic problems and some related problems. When we talk about polytopes we usually mean simple polytopes. (Although looking at general polytopes may be of interest.)

Problem 1: Improve the known upper bounds for the diameter of graphs of polytopes, perhaps finding a polynomial upper bound in term of the dimension and number of facets .

Strategy 1: Study the problem in the purely combinatorial settings proposed in the EHR paper.

Strategy 2: Explore other avenues.

Problem 2: Improve  the known lower bounds for the problem in the abstract setting.

Strategy 3: Use the argument for upper bounds as some sort of a role model for an example. 

Strategy 4:Try to use recursively mesh constructions as those used by EHR.

Problem 3: What is the diameter of a polytopal digraph for a polytope with n facets in dimension d.

A polytopal digraph is obtained by orienting edges according to some generic linear objective function. This problem can be studied also in the abstract setting of shellability. (And even in the context of unique sink orientations.)

Problem 4: Find a (possibly randomized) pivot rule for the simplex algorithm which requires, in the worse case, small number of pivot steps.

A “pivot rule” refers to a rule to walk on the polytopal digraph where each step can be performed efficiently.

Problem 5: Study the diameter of graphs (digraphs) of specific classes of polytopes. 

Problem 6: Study these problems in low dimensions.

Here are seven additional relevant problems.

Problem 7: What can be said about expansion properties of graphs of polytopes?