Math Genius: Bounding distance from uniform distribution in a random walk on regular graph

Original Source Link

Following is a question from Arora-Barak’s Computational Complexity, a simple exercise in probability.

Steps to show UPATH is in RL

Please note that a random step here is defined as: either stay back or go to a neighbour randomly.

I get the idea for each of the step but I am only left with proving the bound $Delta(mathbf{p^k}) leq (1 – n^{-10n}) Delta(mathbf{p})$ for some $k$.

It is easy to show that $Delta(mathbf{p^k})$ is a non-increasing sequence and furthermore since $G$ is connected it should strictly decrease after $n$ steps (that is $Delta(mathbf{p^n}) < Delta(mathbf{p})$). The question also assumes that $G$ is non-bipartite but I don’t think so if it’s required.

I have a hunch that $Delta(mathbf{p^n}) leq left(1 – frac1nright)Delta(mathbf{p})$. If I am able to prove this then I am done because $Delta(mathbf{p^{kn}}) leq left(1 – frac1nright)^kDelta(mathbf{p}) leq left(1 – frac{1}{n^k}right)Delta(mathbf{p})$ and so $k=10n$ gives us the desired inequality.

I shall first show that the inequality holds true for $mathbf{p} = mathbf{e_u}$ where $mathbf{e_u}$ is the probability vector with $1$ at vertex $u$ and $0$ elsewhere.

Let $P$ be the transition matrix ($P_{xx} = frac{1}{d+1}$ and $P_{xy} = frac{1}{d+1}$ iff $(x,y) in E$) for our random walk and so $P^k$ is the $k$-step random walk.

Let $M_k$ denote the maximum entry of the $u^{th}$ row of $P^k$. Then notice that for every vertex $v$:
$$(P^{k+1})_{uv} = sum_w (P^{k})_{uw} (P^1)_{wv} leq M_k sum_w P_{wv} = M_k$$

Thus, $M_{k+1} leq M_k$ and so in particular $M_n leq M_1 leq frac{1}{d+1}$.

Finally $mathbf{p^n} = mathbf{p}P^n = $ $u^{th}$ row of $P^n$ and so $max_{mathbf{v}} {mathbf{p^n_v}} = M_n leq frac{1}{d+1} leq left(1 – frac{1}{n}right)^2$ because $frac{1}{d+1} + frac{2}{n} leq 1$ for all $n geq 3$ and $d geq 2$.

(Note: For $n<3$, $mathbf{p^k}$ is uniform distribution for all $k > 1$ and so the result follows immediately. And for $dleq 1$, since $G$ is connected, it follows that $nleq 2$ and so we are done)

Hence $Delta(mathbf{p^n}) = max_{mathbf{v}} {mathbf{p^n_v} – frac1n} leq max_{mathbf{v}} {mathbf{p^n_v}} leq left(1-frac1nright)Delta(mathbf{p})$ (as $Delta(mathbf{p}) = left(1-frac1nright)$) as desired.

Now for any general distribution $mathbf{p}$, we can express it as $mathbf{p} = sum_{mathbf{v}} mathbf{p_v}mathbf{e_v}$. I am stuck at this point. I had in mind that once I have showed for the “good” probability vectors ($mathbf{e_u}$), this case should follow immediately. But it doesn’t seem so.

Any help with proceeding further would be really appreciated.


Note: I know that $mathbf{p^k}$ will converge to uniform distribution (from a theorem in Markov Chains that for irreducible, aperiodic chains distribution converges to the stationary distribution) which will directly give that $Delta(mathbf{p^k})$ converges to $0$. But proof of this general theorem from Markov Chains requires sophisticated methods like coupling argument or spectral theorem. And this question, as it is asked, suggests me that it can be done without using that theorem.

Another question I wanted to ask: The above bound shows that $Delta(mathbf{p^k})$ converges to $0$ and so the maximum entry from each day distribution converges to $frac1n$. But can we conclude from it that $mathbf{p^k}$ converges to uniform distribution?

Tagged : / / /

Math Genius: How do I approach arranging functions so that each function is big O of the next function?

Original Source Link

The specific question I have to work on is:

$sqrt{n}$ , $log{n^{100}, }$ $ n^{10}$, $log(10^n)$ , $log(n^n)$, $ n!$, $ 3^n$, $log(n!)$

The way I approached this was just choosing a large value for $ n= 100$, and just putting them by order of least to greatest output. However, as this results in some really big outputs, I’m not sure if my result is accurate.

My answer: $sqrt{n}$ , $log{n^{100}, }$ $log(10^n)$ , $log(n!)$, $log(n^n)$, $ n^{10}$, $ 3^n$, $ n!$

I’m fairly confused by the textbook in regards to the growth of functions/big O notation, I understand the basic concept/definition but not how they go about determining this aside from the limit method.

Some hints:

  1. $logleft(a^bright) = b log a$, can you apply that to simplify $log left(n^{100}right)$ and $log left(10^nright)$ and $logleft(n^nright)$?
  2. How do $sqrt{n}$ and $log n$ compare in order? (Think L’Hospital’s Rule for example)
  3. Generally, if $f(n),g(n)$ are functions, you can get a lost of insight in comparing their orders from $$lim_{n to infty} frac{f(n)}{g(n)}$$

You have the 1st two in the wrong order. Since $(log x)/xto 0$ as $xto infty,$ we have $lim_{xto infty}(log (x^A))/x^B=0 $ for any positive $A,B.$

Because $(log (x^A))/x^B=$ $(A/B)cdot (log (x^B))/x^B=$ $(A/B)cdot (log x’)/x’$ where $x’=x^{A/B}to infty$ as $xto infty.$

Apply this with $A=1/2, B=100.$

The $=$ sign in “$f(x)=O(g(x))$ as $xto infty$” is not literal. It means there exists $K>0$ and $rin Bbb R$ such that $|f(x)|le K|g(x)|$ for all $x>r.$ It does not require that $|f(x)/g(x)|$ converge as $xto infty.$

But if $lim_{xto infty}|f(x)/g(x)|$ does exist then $f(x)=O(g(x))$ as $xto infty.$

There is also little-$o,$ which also has a non-literal $=$ sign. “$f(x)=o(g(x))$ as $xto infty$” means that for $any$ $K>0$ there exists $r_Kin Bbb R$ such that $|f(x)|le K|g(x)|$ for all $x>r_K.$

If $f(x)=o(g(x))$ then $f(x)=O(g(x)).$

If $g(x)ne 0$ for all sufficiently large $x$ then (i): $f(x)=o(g(x))$ iff $lim_{xto infty} f(x)/g(x)=0,$ and (ii): $f(x)=O(g(x))$ iff $lim_{rto infty}sup_{x>r}|f(x)/g(x))<infty.$

Tagged : / / / /

Math Genius: What is the computational complexity of linear programming?

Original Source Link

What is the computational complexity of solving a linear program with $m$ constraints in $n$ variables?

The best possible (I believe) is by Michael Cohen, Yin Tat Lee, and Zhao Song:
Solving linear program in the current matrix multiplication time.
https://arxiv.org/abs/1810.07896
(STOC 2019)
Hope this helps.

Brand’s 2020 result derandomized the Cohen, Lee and Song result.
Here is the link
https://arxiv.org/pdf/1910.11957.pdf

Tagged : /

Math Genius: How to calculate running time of code?

Original Source Link

I’m finding great difficulty calculating runtime with loops. It’s easy when there is one loop, especially when the counter is being incremented by one:

for (int i = 0; i < N; i++)

It is clear that the running time is N. But I don’t understand loops that don’t iterate N times. For instance:

for (int i = 5; i < N; i++)

Now I can’t tell what the running time is because it will not run N times.

It get’s even more difficult when there are nested loops. This was an example that was given to me on an exercise:

for (int i = 0; i < N; i++)
    for (int j = i+1; j < N; j++)
        for (int k = i+1; k < N; k++)
            for (int h = k+1; h < N; h++)

I don’t even know where to begin calculating the running time. All I can do is say that the outer loop runs N times but I can’t go further than that. k being equal to i+1 rather than j+1 confuses me even more.

How can I understand how to calculate the running time with nested loops better?

For a loop like this,

for (int i = 5; i < N; i++)

one way to count the number of iterations is to make a list of the number of different
values of $i$ that will occur; each one results in one iteration of the loop.
Those values are
$$ 5, 6, 7, 8, ldots, N – 1. $$
In case you still don’t recognize how many numbers are in that list,
it’s almost the same as the list we get for for (int i = 0; i < N; i++), which is
$$ 0, 1, 2, 3, 4, 5, 6, ldots, N – 1. $$
The difference is that when we start at $i=5$, we skip the first five numbers in the longer list. Those iterations never occur. So instead of $N$ iterations, we have only
$N – 5$ iterations.

Now for this more complicated example:

for (int i = 0; i < N; i++)
    for (int j = i+1; j < N; j++)
        for (int k = i+1; k < N; k++)
            for (int h = k+1; h < N; h++)

In order to get some clue about how many iterations of the inner loop might occur,
it can help to try some actual numbers. So if $N = 4,$ for example,
the outer loop runs four times, with values of $i$ ranging from $0$ to $3.$
Let’s see what happens within each of those loops:

  • $i=0$: then $j$ runs from $1$ to $3$ (three values), and so does $k.$ But there are only two values of $h$ ($2$ and $3$) for $k=1,$ one value of $h$ ($h=3$) when $k=2,$ and no
    values of $h$ at all (the loop never iterates even once) when $k=3,$ because $k+1=N.$ So adding up the numbers of $h$-loops for each $k,$ we get $2+1+0,$ and we get the same again for each value of $j,$ which makes $3cdot(2+1+0)$ times through the innermost loop when $i=0.$

  • $i=1$: then $j$ and $k$ each take only two values ($2$ and $3$); $h$ takes only one value for $k=2$ and none for $k=3.$ Adding up all the innermost loop iterations, we have $1+0$ innermost iterations for each $j,$ for $2cdot(1+0)$ innermost loop iterations altogether.

  • $i=2$: the only iterations of the middle two loops are for $j=3$ and $k=3,$ but when we get to the $h$ loop there are no values left to iterate over; the total is $1cdot(0)$ iterations.

  • $i=3$: no iterations of any of the inner loops.

So adding up over all the times through the outermost loop, we get
$3cdot(2+1+0) + 2cdot(1+0) + 1cdot(0).$

What if $N=5?$ We then get more iterations of the inner loop while $i=0.$ If you follow the same reasoning as before, you get $4cdot(3+2+1+0)$ iterations of the innermost loop,
followed by $3cdot(2+1+0)$ and so forth just like before; the total ends up at
$4cdot(3+2+1+0) + 3cdot(2+1+0) + 2cdot(1+0) + 1cdot(0).$

See a pattern? (The reason I have not yet actually calculated the results of adding or
multiplying any of these numbers is that I did not want to lose track of the pattern.)
Once we see a pattern, if we can write the sum for any $N$ using a suitable notation,
we can work with it algebraically.
Extending the pattern to larger values of $N,$ the number of inner loops is

$$ f(N) = sum_{m=1}^{N-1} left( m sum_{h=0}^{m-1} h right). $$

Now the only thing left is to find a more convenient way to represent the total as a formula in terms of $N.$ We can use the fact that
$Sigma_{x=0}^{m-1} x = frac{m(m-1)}{2}$
to reduce this sum of multiples of sums to just a sum of terms,
each of which is a cubic polynomial.
It will be useful to know the formulas for $Sigma_{x=0}^m x^2$ and
$Sigma_{x=0}^m x^3$ too in order to solve this altogether.
In the end, it shouldn’t be too surprising if the leading term of the formula
for the total number of loops is some constant times $N^4,$
since we do after all have four nested loops each counting up by $1,$
albeit from various starting values.


In case the example $N=4$ as described above is still not clear, here is a time sequence of all the values that the variables $i,$ $j,$ $k,$ and $h$ take on during all the loops
for $N=4.$
$$begin{eqnarray}
quad& i &qquad & j qquad & k qquad & h quad \
hline
& 0 && 1 & 1 & 2 \
& 0 && 1 & 1 & 3 \
& 0 && 1 & 2 & 3 \
& 0 && 1 & 3 & \
& 0 && 2 & 1 & 2 \
& 0 && 2 & 1 & 3 \
& 0 && 2 & 2 & 3 \
& 0 && 2 & 3 & \
& 0 && 3 & 1 & 2 \
& 0 && 3 & 1 & 3 \
& 0 && 3 & 2 & 3 \
& 0 && 3 & 3 & \
& 1 && 2 & 2 & 3 \
& 1 && 2 & 3 & \
& 1 && 3 & 2 & 3 \
& 1 && 3 & 3 & \
& 2 && 3 & 3 & \
& 3 && & & \
end{eqnarray}$$
Each line represents a new set of values that occurred.
Blank entries mean there was no value of the variable that was less than $N$ when the variables to the left had the values shown.
The inner loop executes only for lines where all the variables have values,
which is just the lines where the entry for $h$ is not blank.

For example, consider the first four lines of the table. These show the iterations of
the $k$ loop when $i=0$ and $j=1:$ two iterations for $k=1,$ then one for $k=2,$ and
none at all for $k=3$ (indicated by the blank in the $h$ column), total $2 + 1 + 0.$
But these four lines occur almost exactly the same way three times; the only difference
is the value of $j,$ which is $1,$ $2,$ or $3.$ These three repetitions of the
pattern $2 + 1 + 0$ result in the term $3cdot(2 + 1 + 0)$ to count the inner loop
iterations for $i=0.$

Similar tables for $N=5$ or even $N=6$ are relatively easy to draw up if the
pattern is not clear enough from this table.

Tagged : / /

Math Genius: Linearization of a polynomial

Original Source Link

Arora and Barak in their book, CC A modern approach here may have a typo in
(8.15) on the page $161$:
$exists_{X_i}p(X_1,…,X_n)=p(X_1,…,X_{i-1},0,X_{i+1},…,x_n)+p(X_1,…,X_{i-1},1,X_{i+1},…,x_n)$
should read
$exists_{X_i}p(X_1,…,X_n)=p(X_1,…,X_{i-1},0,X_{i+1},…,x_n)+p(X_1,…,X_{i-1},1,X_{i+1},…,x_n)-p(X_1,…,X_{i-1},0,X_{i+1},…,x_n)cdot p(X_1,…,X_{i-1},1,X_{i+1},…,x_n)$.

This is because $p(X_1,…,X_{i-1},0,X_{i+1},…,x_n)$ and $p(X_1,…,X_{i-1},1,X_{i+1},…,x_n)$ might both be 1 in which case we would obtain $1+1=2$
which is not in ${0,1}$.

enter image description here

Tagged : / /

Math Genius: How long can proofs be?

Original Source Link

Let
$$f(n) = max{text{length of shortest proof of }varphi mid varphi text{ is a provable ZFC sentence of length } leq n}$$

How fast does $f$ grow? Is it polynomial, exponential, more than exponential, etc.?

This function grows really fast: there is no computable function which bounds it!

To see this, note that if we had a computable bound on $f$ we could tell whether a sentence $sigma$ is consistent with $mathsf{ZFC}$ (just search over all proofs of length $<f(vertsigmavert+1)$ for a $mathsf{ZFC}$-proof of $negsigma$). But from this information we could in turn build a computable complete consistent extension of $mathsf{ZFC}$:

  • Fix an appropriate enumeration $(sigma_i)_{iinmathbb{N}}$ of the sentences in the language of set theory.

  • Define a new sequence $(tau_i)_{iinmathbb{N}}$ of sentences by recursion as follows:

    • $tau_0=sigma_0$ if $sigma_0$ is consistent with $mathsf{ZFC}$, and $tau_0=negsigma_0$ otherwise.

    • $tau_{i+1}=sigma_{i+1}$ if $sigma_{i+1}wedgebigwedge_{jle i}tau_i$ is consistent with $mathsf{ZFC}$, and $tau_{i+1}=negsigma_{i+1}$ otherwise.

  • The set ${tau_i:iinmathbb{N}}$ is then a complete computable consistent theory containing $mathsf{ZFC}$ (note that when $sigma_i$ is an axiom of $mathsf{ZFC}$ we’ll have $tau_i=sigma_i$).

However, this contradicts the first incompleteness theorem. (Or Church’s theorem, if you like – basically the above is the proof of Church’s theorem from the first incompleteness theorem.)


Note that we really used very little about $mathsf{ZFC}$ here. The first incompleteness theorem applies to a huge range of theories, ranging from much weaker than $mathsf{ZFC}$ to much stronger than $mathsf{ZFC}$; briefly, any consistent computably axiomatizable theory which satisfies a very mild technical “strength condition” (basically: at least as powerful as Robinson’s $Q$) is subject to this phenomenon. See section $4$ of this paper of Beklemishev for more details on this point.

To be precise, the form of the first incompleteness theorem I’m using is: “Every computably axiomatizable consistent theory which interprets Robinson’s $mathsf{Q}$ is incomplete.” Note that we don’t need an $omega$-consistency assumption here; while present in Godel’s original proof, it was later removed by Rosser.

Tagged : / /

Math Genius: Why is it so computationally hard to determine group isomorphism?

Original Source Link

Finding an isomorphism requires to show that for 2 groups $G$ and $H$, there exists a bijective map $phi : Gto H$ such that
$$phi(ab)=phi(a)phi(b)$$
For all $a,b in G$. This is (probably
naively) pretty straight forward, and there are plenty of theorems that allow us to show that groups of specific orders must be isomorphic to some specific set of groups. So, my question (which I hope isn’t too loaded) is

What intrinsically makes finding if 2 groups are isomorphic so hard? Is it showing that they are bijective, is it showing that they are operation preserving, or is it something entirely different?

Tagged : / / /

Math Genius: Constraint satisfaction problem with a semilattice polymorphism is polynomial-soluble

Original Source Link

Let $mathbb{A}=(A;R)$ be a relation structure, where $A$ is a finite set, $varnothingneq Rsubseteq A^2$ is a relation preserved by a semilattice operation $f$. This means that $f:A^2to A$ is idempotent, associative and commutative. Show that $mathrm{CSP}(mathbb A)in mathsf P$.

I encounter the problem as a generalisation of the version when $R$ is subdirect, in which case the CSP is clearly polynomial-soluble, as each primitive positive sentence naturally holds. However, in general when $R$ is not subdirect, this claim clearly fails. I am considering using clone homomorphism and interpretation to prove the general case, but so far I have not got any clue.

Thank you very much for help!

We may assume $mathbb{A}$ is an idempotent core structure. (If it isn’t, read the chapter “Polymorphisms and how to use them” by Barto, Kozik, and Willard. You want Theorems 16 and 17.)

Now that $mathbb{A}$ is idempotent, every non-empty subuniverse of $mathbf{A}=mathrm{Pol}(mathbb{A})$ has a 1-element subuniverse that is absorbed via $f$.

Before we talk about Prague instances, I first want to make sure we’re on the same page. $mathrm{CSP}(mathbb{A})$ is a decision problem whose input is a finite relational structure $mathbb{X}$ of the same signature as $mathbb{A}$ and whose output is ‘yes’ if there is a homomorphism $mathbb{X}tomathbb{A}$ and is ‘no’ if there is not. To show $mathrm{CSP}(mathbb{A})$ belongs to $mathsf{P}$, we must exhibit a polynomial-time algorithm that decides it. I’ll describe an algorithm below:

  1. Collect all partial homomorphisms $mathbb{X}tomathbb{A}$ whose domain has at most 3 elements. Call this collection $H$.
  2. For every subset $L$ of $X$ of size 3, if a partial homomorphism $p$ in $H$ whose domain is $K$ (where $K$ is a subset of $L$ of size at most 2) does not have an extension in $H$ to all of $L$, then remove $p$ from $H$. Repeat until all choices of $L$, $K$, and $p$ have been checked.
  3. If $H$ is empty, return ‘no’. Else return ‘yes’.

The runtime of this algorithm is polynomial in the size of $X$ and if $H$ is empty, then there cannot be a homomorphism $mathbb{X}tomathbb{A}$. To get that a nonempty $H$ implies existence of a homomorphism, we need to analyze the structure of $H$.

For $x,yin X$, let $H_x=Hcap A^{{x}}$ and
$H_{xy}={(h_1,h_2)in H_xtimes H_y:h_1,h_2text{ have a common extension in }H}$.

Let $mathcal{H}={H_x:xin X}cup{H_{xy}:x,yin X}$.

This $mathcal{H}$ satisfies the property that for any $x,y,zin X$, and any $(h_1,h_3)in H_{xz}$, there is $h_2in H_y$ such that $(h_1,h_2)in H_{xy}$ and $(h_2,h_3)in H_{yz}$.

This property is stronger than being a Prague instance (the book chapter mentioned above in the comments asks you to show this as an exercise, but I think you can find the proof in the appendix of “Constraint satisfaction problems of bounded width” by Barto and Kozik)

Once you have that, you can just follow along with Proposition 10 like I mentioned in the comments.

Tagged : / / /

Math Genius: A problem involving squared numbers and can it be solved in polynomial time?

Original Source Link

$f(x)$ = $x$$S$, $x$ = $x$^$2$

All elements in $S$ must be integers ($1$, $N$) as in counting from $1$ to $N$.

$N$ = $4$

$S$ = $[1,2,3,4]$

Then all elements in $S$ will be squared.

$S$ = $[1, 4, 9, 16]$

I need to be able to have all elements in $S$ to not be a factor of another. (excluding itself if it is alone and $1$)

[4] and [16] are a problem.

  • I need to have $S$ to have a length of given $N$.

  • I must find a list of $N$ integers that are all $n$^$2$ without any of them sharing factors.

Algorithm

while S hasfactors:

   # re-create list S starting (1, N) until 
   # N integers are found that are not factors of each other

   square all elements in S
   remove = set(factors in S)
     S = set(S) - set(remove)
      if length(S) = N and hasNOfactors:
        OUTPUT {1, 169, 121, 49}

Question

The algorithm runs fine on practical inputs. But, as the magnitude of $N$ gets larger it gets ridiculously slow.

Can this problem be solved in polynomial time?

A simple approach is to use the first $N$ prime numbers plus $1$ if you would like. That is the set of numbers with smallest maximum magnitude that are pairwise relatively prime. You can find them with a sieve, which I believe is about $N^2$, and is certainly polynomial. Having found them, square them and you are done.

If $N=6$ and you start with $1$, the list becomes $1,2,3,5,7,11$, which square to $1,4,9,25,49,121$

Tagged : / /