Recent MathOverflow Questions

How to prove |x+x_1+...+x_n| >= |x| - (|x_1|+...+|x_n|)? [on hold]

Math Overflow Recent Questions - Sat, 03/31/2018 - 05:35

I'm having trouble proving this equation: $$|x+x_1+...+x_n| \ge |x| - (|x_1|+...+|x_n|)$$

I tried induction and triangle inequality, but with no luck. Help please

Morrey condition (integral condition) and (local) Holder condition

Math Overflow Recent Questions - Sat, 03/31/2018 - 05:10

Let $x \in \mathbb{R}^n$ and $f:\mathbb{R^n} \to \mathbb{R}$ be a non-negative function such that $f(x)=0$. Is it true that (assuming $\alpha,\beta>0$) $$\limsup_{r \to 0} r^{-\alpha \beta}\frac{1}{|B_{r}(x)|}\int_{B_{r}(x)} f(y)^\alpha dy < \infty$$ implies $$|f(z)| \le C|z-x|^\beta,$$ for $z$ close enough to $x$ and for some constant $C>0$?

Sequential criteria for continuity [on hold]

Math Overflow Recent Questions - Sat, 03/31/2018 - 04:43

Theorem (Sequential criteria for continuity). $f$ is continuous at $a$ if and only if for every sequence $a_n$ converging to $a$, we have $f(a_n)$ converging to $f(a)$.

My interest here is the reverse direction which says “If every sequence $a_n$ converging to $a$, we have $f(a_n)$ converging to $f(a)$, then $f$ is continuous at $a$”.

I have looked at a lot of real analysis textbooks and all of them without any exceptions use contrapositive/contradiction to prove this. It makes me wonder if a direct/constructive proof without using contrapositive/contradiction is possible and how?

I am not against proof by contradiction but I am desperately curious if one can construct a direct proof.

A question on Deligne-Serre lifting lemma

Math Overflow Recent Questions - Sat, 03/31/2018 - 04:42

Good day, everyone. I have been studying the paper "Formes modulaires de poid 1" written by Deligne and Serre. I am confused by lemma 6.11, or the so-called Deligne-Serre lifting lemma in the paper.

The original proof is somewhat short and rough, so I have found another note which gives a more detailed statement at page 7 in the following website

However, there is still some problem I cannot figure out. The main question is as follows:

Let $\mathcal{O}$ be a discrete valuation ring, $\mathfrak{m}$ be its maximal ideal, and $k$, $K$ be residue field and field of fractions respectively. Let $M$ be a finitely generated free $\mathcal{O}$-module, and $\mathcal{T}$ a family of mutual commuting elements in End($M$), and we denote the $\mathcal{O}$-algebra generated by $\mathcal{T}$ by $\mathbb{T}$.

At the last part of this note, we have found a minimal prime $\mathfrak{p}$ in $\mathbb{T}$ which annihilates $f$ in the module $M / \mathfrak{m}M$, hence $\mathfrak{p} \in Ass_\mathbb{T}(M / \mathfrak{m}M) \subset Supp_\mathbb{T}(M / \mathfrak{m}M) \subset Supp_\mathbb{T}(M)$. Thus, $Ann_\mathbb{T}(M)\subset \mathfrak{p}$. Now we need to tensor all things with $K$, and let $\mathcal{P}$ be the ideal generated by $\mathfrak{p}$ in $K \otimes M$. Then it claims that $Ann_{K \otimes \mathbb{T}}(K \otimes M) \subset \mathcal{P}$ and $\mathcal{P} \in Supp_{K\otimes\mathbb{T}}(K\otimes M)$. But how can I ensure that that $\mathcal{P}$ is still a prime ideal? Moreover, I need it to be a minimal prime so that I can deduce $\mathcal{P} \in Ass_{K\otimes M}(K\otimes M)$. Is such $\mathcal{P}$ always minimal?

The space of contractible loops of a finite dimensional $K(\pi,1)$

Math Overflow Recent Questions - Sat, 03/31/2018 - 04:18

Let $X$ be a finite dimensional $K(\pi,1)$ manifold. Is it true that the space contractible loops of this manifold can be contracted to the space of constant loops on $X$? What if $X$ is a finite dimensional $CW$-complex?

I understand that the answer is positive if $X$ is a negatively curved manifold, since in this case there is a geometric argument.

On what varieties are the conjectures on $L$-functions true

Math Overflow Recent Questions - Sat, 03/31/2018 - 03:45

In Peter Schneider's paper "Introduction to the Beilinson conjectures", he lists some hypothesis (conjectures) on the $L$-function associated to the pure motive $H^i(X)$ where $X$ is a smooth projective variety defined over $\mathbb{Q}$.

  1. $L(H^i(X),s)$ converges absolutely for $\text{Re}\,s >1+i/2$, hence it does not vanish in this region.

  2. $L(H^i(X),s)$ has a meromorphic continuation to the whole complex plane, and the only possible pole occurs at $s=1+i/2$ for even $i$.

  3. $L(H^i(X),1+i/2) \neq 0$, (I guess he means when $s=1+i/2$ is not a pole).

  4. $\Lambda(H^i(X),s):=L(H^i(X),s)\cdot L_{\infty}(H^i(X),s)\cdot(\text{exponential factor})$ has a functional equation with respect to the operation $s \mapsto i+1-s$, where $L_\infty(H^i(X),s)$ is the Euler factor associated to the archimedean place of $\mathbb{Q}$.

For a variety $Y$ defined over a number field $K$, its Euler factor at a non-archimedean place is defined similarly.

Question 1. How to define the Euler factor at a archimedean place?

For a real place of $K$, there is still an involution $F_{\infty}$ induced by complex conjugation on the $\mathbb{C}$-valued points $Y(\mathbb{C})$, and I guess the Euler factor is defined as the $\mathbb{Q}$-case? But how to define the Euler factor for a (conjugated pair of) complex place(s)?

Question 2. I guess the four hypothesis are also expected for the $L$-function of $H^i(Y)$. At current stage, for which (class of) smooth projective varieties (over a number field) has these hypothesis been proved?

Alternating sum of powers

Math Overflow Recent Questions - Sat, 03/31/2018 - 03:30

Fix a positive integer $k$. Is it true that for large enough $n$ there exist signs such that $$\pm 1^k\pm 2 ^k\pm \dots \pm n^k=(n(n+1)/2\, \text{mod}\, 2)? $$

It is not hard to show that such sums may be made bounded (since $2^{k+1}$ consecutive signs may be chosen so that the contribution of corresponding summands equals to 0.) But I do not see immediate reasons why it can not be made so ultimately small.

A question related to Dirichlet's theorem

Math Overflow Recent Questions - Fri, 03/30/2018 - 23:19

Is it possible for a natural number $k$ to exist such that for all primes $p$: $$(p+1)k-1$$ is composite?

(i.e., can all $3k-1$, $4k-1$, $6k-1$, $8k-1$, $12k-1$, $14k-1$, $18k-1$, $20k-1$, $24k-1$, $30k-1$, $32k-1$, $38k-1$, $42k-1$, $44k-1$, $48k-1$, ... be composite?)

Is measure preserving function almost surjective?

Math Overflow Recent Questions - Fri, 03/30/2018 - 20:51

Let $F:[0,1]\to[0,1]$ be a Lebesgue measure preserving function. Is $F$ almost surjective, i.e., the image of $F$ has interior measure one?

This question is motivated by the following observation. If $F$ satisfies the above and $X$ is uniformly distributed over $[0,1]$, then $F(X)\sim Unif[0,1]$, i.e., $F(X)$ seems to appear almost everywhere in [0,1]. I believe the answer is no, but a counterexample is nontrivial.

A relating post is but the counter example therein does not apply to my question. (The function constructed there has different domain and range.)

Simple $C^*$ algebras with invariant subspace property

Math Overflow Recent Questions - Fri, 03/30/2018 - 18:11

Edit: According to the valuable comment of Yemon Choi I revise the question by replacing "faithful" with "irreducible".

We say that a $C^*$ algebra $A$ satisfies the invariant subspace property if there exist an irreducible representation $\phi: A \to B(H)$, for some Hilbert space $H$, such that $\forall a \in A,\; \phi(a)$ has a nontrivial closed invariant subspace of $H$.

What is an example of a simple $C^*$ algebra with this property not isomorphic to the matrix algebra or the algebra of compact operators?

In particular, does $C^*_{red}(F_2)$ satisfy this property?

What is a natural way to extend a function from a subset of vertices to faces?

Math Overflow Recent Questions - Fri, 03/30/2018 - 16:46

Let $n$ be a positive integer, and suppose $f$ is a probability distribution on the $2^n$ subsets of $[\![n]\!] := \{1,\ldots,n\}$. What is a "natural" way to extend $f$ to a distribution $\bar{f}$ on the simplex $\Delta_n := \{x \in \mathbb R^n | x_1,\ldots x_n \ge 0, \sum_i x_i = 1\}$ satisfying the constraint that $\bar{f}(x) = f(I)$ whenever $x$ is the centroid of the face of $\Delta_n$ spanned by by a nonempty subset $I \subseteq [\![n]\!]$ of vertices ?

In other words, how to extend a function specified only at the centroids of the faces of a simplex, to the entire simplex ?

Rquirement 1: $\bar{f}$ should be a continuous function on $\Delta_n$ and so can't be just piecewise linear on the faces, for example.

What is the intuition behind Almgren's frequency function?

Math Overflow Recent Questions - Fri, 03/30/2018 - 16:11

It is by now well-known that for a harmonic function $u : B_1^n(0) \to \mathbb{R}$, the ratio $$ N(r) := \frac{r\int_{B_r(0)}|\nabla u|^2}{\int_{\partial B_r(0)} u^2} $$ is a non-decreasing function of $r$.

This and analogous expressions have been used in many different fundamental works on elliptic equations, but to me, it has always seemed like a mystery and as a result I have trouble even remembering this expression and usually have to look it up.

What's the intuition behind the definition of $N$? What does this ratio of energy in the ball and L^2 norm on the sphere even represent?

What is the extreme value distribution for the Kolmogorov-Smirnov D statistic?

Math Overflow Recent Questions - Fri, 03/30/2018 - 12:59

I occasionally find that I want to apply a K-S test in the context of unit-testing software that involves random behaviors. Unit testing with sampling statistics is a bit tricky because you want to minimize false-failures.

Extreme value distributions seem like one useful approach, since they make it possible to run a series of experiments, find a maximum D statisic between experimental results and an expected distribution, and measure the probability that D is an outlier using Extreme Value theory.

The idea is that I might run (n) K-S tests, comparing n pairs of samples. This will result in n D-statistic values; the maximum of these values will adhere to some variation of extreme value distribution. I could use the formula for this (or an approximation).

I have never found an extreme value distribution for the K-S D statistic. I suspect it at least adheres to the Weibull form of the EV distribution since its value has a finite maximum, but not even sure of that. I might do some empirical fitting but a more general formula would be even nicer.

Matrix trace & norm

Math Overflow Recent Questions - Fri, 03/30/2018 - 04:49

For any nonnegative semidefinite matrix $A$ and any matrix $B$, we have

$$\mbox{tr} (AB) \le \mbox{tr} (A) \, \|B\|$$

where $\mbox{tr}(\cdot)$ is the trace and $\|\cdot\|$ is the operator norm. How to prove this?

Does knight behave like a king in his infinite odyssey?

Math Overflow Recent Questions - Thu, 03/29/2018 - 15:54

The Knight's Tour is a well-known mathematical chess problem. There is an extensive amount of research concerning this question in two/higher dimensional finite boards. Here, I would like to tackle this problem on the unbounded infinite board, $\mathbb{Z}\times\mathbb{Z}$.

The first issue is how to construct a knight's tour on the infinite plane. An intuitive way is to build it locally by mimicking the king's spiral tour in $\mathbb{Z}\times\mathbb{Z}$ board as follows:

Roughly speaking, a knight may follow the king's pattern by completing a knight's tour on an $n\times n$ block and then moving to the next block in the spiral order. For instance, in the below picture each square represents a certain $n\times n$ part of the $\mathbb{Z}\times\mathbb{Z}$ plane and the blue path is a knight tour performed in that particular block. It is connected to a point in the neighbor blocks with a knight move.

Of course, the existence of such a nice natural number $n$ should be checked. However, it sounds reasonable to expect that for a sufficiently large $n$ (which there are so many open knight tours with various beginning and ending points) there are some tours which can serve as the building blocks of the knight's king-like spiral. (Actually only a few straight and right-oriented $n\times n$ tours with appropriate beginning and ending points are needed. The other blocks will be redundant up to isomorphism).

Here, the first question arises:

Question 1. Is there (a concrete example of) a knight's tour on the infinite plane?

In the special case, does the already described strategy for building a knight's tour locally actually work? If yes, what is the minimum required $n$?

Assuming an affirmative answer to the above question, the next step is to speculate on the general structure of all possible knight tours on the infinite plane:

Question 2. Do all infinite knight's tours on the infinite plane arise as a combination of local finite knight's tours on a grid of blocks of the same size (whose local knight's tours are attached to their neighbor counterparts in a king's move fashion)?

Precisely, is it true that for any given knight's tour $t$ on the infinite plane $\mathbb{Z}\times\mathbb{Z}$, there is a (probably large) natural number $n$ and a partition $p$ of the plane into $n\times n$ blocks in a grid such that the restriction of $t$ into any block in $p$ is an $n\times n$ knight's tour in that particular block itself? We call the partition $p$ a localization of the knight's tour $t$ into a grid of $n\times n$ blocks.

If no, what is an example of an infinite knight's tour which can't be seen as a combination of local knight's tours in a grid of finite blocks of the same size (no matter what the resolution of the gird is)?

If yes, what is: $$min\{n_t|~t~\text{is a knight's tour of $\mathbb{Z}\times\mathbb{Z}$ & there is a localization of}~t~\text{into a grid of}~n\times n~\text{blocks}\}$$ In better words, what is the finest possible resolution of a grid for a knight's tour of the infinite plane, $\mathbb{Z}\times\mathbb{Z}$?

As a remark it is worth mentioning that not all partitions of the infinite plane into $n\times n$ blocks are in the form of a perfect grid. For example, see the left picture in the following diagram which is a partition of the plane via $n\times n$ blocks different from a grid of $n\times n$ blocks (right):

So, for the sake of completeness, one may reduce the grid partition condition in question 2 to merely a partition of the infinite plane into $n\times n$ blocks:

Question 3. What is the answer to question 2 if we merely consider partitions of the infinite plane into $n\times n$ blocks, rather than those partitions which arrange blocks in a perfect grid?

The question could be asked in a more general sense as well:

Question 4. Is the knight's tour on the infinite plane always decomposable into finite knight's tours? Precisely, is it true that for every knight's tour $t$ on the infinite plane there is a partition $p$ of the plane into finite squares (not necessarily consisting of blocks in a grid or of the same size) such that the restriction of $t$ to any block in $p$ is a finite knight's tour as well?

Update. Thanks to Joel's answer and Eric's counterexample, the questions 1 and 2-4 have been answered positively and negatively respectively. Thus, we know that there are open knight's tours of the unbounded infinite plane, $\mathbb{Z}\times\mathbb{Z}$, of different nature, namely those which are formed of local knight's tours of finite planes and those total tours which don't arise this way. In this sense the answer to the question in the title is: "Sometimes but not always!"

Remark. As an additional piece of information, it is worth mentioning that there are some simple infinite sub-spaces of $\mathbb{Z}\times\mathbb{Z}$-plane which don't admit a knight's tour while some others do. For example, it is easy to see that one can obtain a knight's tour for $\mathbb{N}\times\mathbb{N}$ sub-plane through a local block by block construction via Joel's $5\times 5$ blocks introduced in his answer. However, it is intuitively clear that the infinite strip (i.e. $[-n,+n]\times\mathbb{Z}$ for some $n$) doesn't admit a knight's tour because the knight in such a sub-space must cover both infinite sides of the strip in a back and forth movement and so it should pass the central part of the strip infinitely many times which is impossible simply because after finitely many passages there will be no empty room left in the central region. Anyway, it sounds an interesting question to classify all infinite sub-spaces of $\mathbb{Z}\times\mathbb{Z}$-plane which admit a knight's tour. The same has already been done for all finite rectangle-shape sub-spaces of $\mathbb{Z}\times\mathbb{Z}$-plane, namely $m\times n$-boards.

When does the enveloping algebra functor lift to the category of bialgebras?

Math Overflow Recent Questions - Thu, 03/29/2018 - 06:51

Let $\mathrm{Ass} $ denote the operad, whose algebras are associative unital algebras, considered as a dg-operad. Denote $\mathrm{Ch} $ the category of chain complexes over a commutative ring $\mathrm{R} $ and denote $\mathrm{Bialg}_{ } (\mathrm{Ch} )$ the category of cocommutative (counital and unital) bialgebras in $\mathrm{Ch}. $

Let $\mathcal{O}$ be a dg-operad and $\phi: \mathcal{O} \to \mathrm{Ass} $ a map of dg-operads. $\phi$ induces a free-forgetful adjunction $ \mathcal{U} : \mathrm{Alg}_{ \mathcal{O} } ( \mathrm{Ch} ) \rightleftarrows \mathrm{Alg}_{ \mathrm{Ass} } ( \mathrm{Ch} ).$

When does the left adjoint $ \mathcal{U} : \mathrm{Alg}_{ \mathcal{O} } ( \mathrm{Ch}) \to \mathrm{Alg}_{ \mathrm{Ass} } (\mathrm{Ch} ) $ lift to a functor $ \mathrm{Alg}_{ \mathcal{O} } ( \mathrm{Ch} ) \to \mathrm{Bialg}_{ } (\mathrm{Ch} )? $

For $\mathcal{O}$ the Lie operad there is such a lift.

For $\mathcal{O}$ the Lie operad the left adjoint $\mathcal{U}$ is the enveloping algebra. For every Lie-algebra $\mathrm{X}$ the bialgebra structure on $\mathcal{U}(\mathrm{X})$ is encoded in a symmetric monoidal structure on the category $\mathrm{LMod}_{ \mathcal{U}(\mathrm{X}) } (\mathrm{Ch} )$ (being the category of representations of $\mathrm{X}$) lifting the symmetric monoidal structure on $\mathrm{Ch} .$

The category of representations of $\mathrm{X}$ can also be described as the category $\mathrm{Mod}^{\mathcal{O}}_{ \mathrm{X} } (\mathrm{Ch} ) $ of $\mathrm{X}$-modules over the Lie-operad.

This leads to my 2. question: For which dg-operads $ \mathcal{O}$ and $ \mathcal{O}$-algebras $\mathrm{X}$ does the symmetric monoidal structure on $\mathrm{Ch} $ lift to a symmetric monoidal structure on $\mathrm{Mod}^{\mathcal{O}}_{ \mathrm{X} } (\mathrm{Ch} ) ?$

More generally given a dg-operad $\mathcal{O}$ and a $\mathcal{O}$-algebra $\mathrm{X}$ there is a enveloping associative algebra $\mathcal{U}_{ \mathcal{O}}( \mathrm{X} ) $ with the property that we have a canonical equivalence $$\mathrm{LMod}_{\mathcal{U}_{ \mathcal{O}}( \mathrm{X} ) } (\mathrm{Ch} ) \simeq \mathrm{Mod}^{\mathcal{O}}_{ \mathrm{X} } (\mathrm{Ch} ) .$$

As a cocommutative bialgebra structure on an associative algebra corresponds to a symmetric monoidal structure on its category of left modules lifting the symmetric monoidal structure on $ \mathrm{Ch} $, my 2. question is equivalent to the following:

For which dg-operads $ \mathcal{O}$ does the enveloping associative algebra functor $ \mathcal{U} : \mathrm{Alg}_{ \mathcal{O} } ( \mathrm{Ch}) \to \mathrm{Alg}_{ \mathrm{Ass} } (\mathrm{Ch} ) $ lift to a functor $ \mathrm{Alg}_{ \mathcal{O} } ( \mathrm{Ch} ) \to \mathrm{Bialg}_{ } (\mathrm{Ch} )? $

Why do these two Monster-related calculations yield $163$?

Math Overflow Recent Questions - Thu, 03/29/2018 - 03:46

Fact 1: (1979, Conway and Norton)$^{1}$

"There are $194-22-9=\color{blue}{163\,}$ $\mathbb{Z}$-independent McKay-Thompson series for the Monster."

Note: There are 194 (linear) irreducible representations of $\mathbb{M}$, hence 194 conjugacy classes. Of these, there are 22 that are complex quadratic valued. Of the remaining, there are 9 linear dependencies.$^{2}$

Fact 2: (2004, C. Cummins)$^{3}$

"The genus 0 moonshine groups have $132 + 1 + 4 + 5 + 13 + 1 + 7=\color{blue}{163}$ equivalence classes with period 1."

Note: There are exactly $6486$ genus $0$ moonshine groups, but only $371$ equivalence classes. Of these, $310\,$ have a rational representative. (Curiously, $\color{red}{310} =163+67+43+19+11+7$.)

\begin{array}{|c|r|c|c|c|c|c|c|c|c|c|c|} \hline \text{Period}& & 15^* & 11^*& 7^*& 3^*& 2^*& i& i\,2& 2 & 5 &\color{brown}{\text{Total}}\\ \hline 1&132& 0& 1& 4& 5& 0& 13& 1& 0& 7 & \color{blue}{163}\\ 2&120& 0& 0& 2& 1& 7& 4& 2& 2& 2& 140\\ 3& 26& 1& 0& 1& 4& 0& 2& 0& 0& 0& 34\\ 4& 16& 0& 0& 0& 0& 2& 0& 0& 0& 0& 18\\ 6& 10& 0& 0& 0& 0& 0& 0& 0& 0& 0& 10\\ 8& 3& 0& 0& 0& 0& 0& 0& 0& 0& 0& 3\\ 12& 2& 0& 0& 0& 0& 0& 0& 0& 0& 0& 2\\ 24& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1\\ \hline \color{brown}{\text{Total}}&\color{red}{310}& 1& 1& 7& 10& 9& 19& 3& 2& 9& \color{brown}{371}\\ \hline \end{array}

Question: While the value $163$ was calculated differently in Facts 1 and 2, are they just different ways of saying the same thing, and that one implies the other?


  1. Monstrous Moonshine, by J.H. Conway & S.P. Norton.
  2. Sporadic and Exceptional, by Yang-Hui He & John McKay.
  3. Congruence Subgroups of Groups Commensurable with PSL (2, Z) of Genus 0 and 1, by C. J. Cummins.
  4. Tables by C. J. Cummins.

Two smooth tangent almost complex curves in a $4$-manifold

Math Overflow Recent Questions - Wed, 03/28/2018 - 16:24

I believe that the following is correct and would like to find a reference:

Statement. Suppose we have a smooth (i.e., $C^\infty$) almost complex structure on $\mathbb R^4$ and $C_1, C_2$ are two $J$-holomorphic curves passing through $(0,0)$, tangent at $(0,0)$ and regular at $(0,0)$. Then there exist $C^{\infty}$ smooth complex coordinates $(z,w)$ such that $C_1$ is locally given by $w=0$ and $C_2$ by $w=z^n$.

PS. I think it would be enough for me to know that $C_2$ can be given by $w=z^n+O|z^{n+1}|$. However everything must be $C^{\infty}$ - the coordinates, and the $O|z^{n+1}|$ term.

PPS. A very close reformulation of this question is posted separately here: Normal form of two tangent symplectic surfaces in $\mathbb R^4$ I do this to remove any possible uncertainty about the question

Differential geometry of gerbes

Math Overflow Recent Questions - Wed, 03/28/2018 - 12:28

Gerb on a topological space $X$ is a stack of groupoids $\mathcal{F}$ on site $\mathcal{O}(X)$ where category is category of open sets on $X$ it’s obvious grothendieck topology satisfying following conditions:

  1. Locally non empty i.e., Given $x\in X$ there is an object/open set $U$ containing $x$ such that $\mathcal{F}(U)$ is non empty.
  2. Locally connected i.e., Given $a,b\in\mathcal{F}(U)$ and $x\in U$ there exists an open sub set $V$ of $U$ contains $x$ such that $a|_V$ is isomorphic to $b|_V$.

I am trying to understanding differential geometry of gerbes and finding it difficult with the resources that I have with me.

I am reading about gerbes from Lawrence Breen’s notes and Moerdijk notes Goal for near future is to understand Differsntial geometry of gerbes as in of Breen and Messing.

I am comfortable with Differentisl geometry of principal bundles as in chapter $2$ of Kobayashi and Nomizu. As torsors are in some sense Principal bundles and torsors are examples of gerbes I have some hope in understanding about connections on Gerbes.

Any outline of concepts of connections on gerbes would be definitely useful.

What is th first/second/… thing I need to know to understand about differential geometry of gerbes.

Probability question about random shuffling of piles of rocks

Math Overflow Recent Questions - Wed, 03/28/2018 - 08:35

I have $k$ piles of rocks placed on a circle so that every pile has exactly two neighboring piles. We know that initially the piles have $x_1,\dots,x_k$ rocks in each respectively. A monkey plays the following game: at each timestep it picks a random pile, takes a rock from it, and places it in one (again randomly) of its adjacent piles . If a pile becomes empty it disappears and we're left with a game of $k-1$ piles (the monkey can't "revive" an empty pile by placing a rock where it used to be). The game is played until only one pile remains. What is the expected number of timesteps until this happens?

My thoughts so far are that this is like taking a lazy random walk on a graph where each node is a configuration of the $x$ values. For $k=2$ the solution is simple because it's just a random walk but even for $k=3$ I can't solve it and thus use induction. I tried thinking of a Markov chain coupling but haven't succeeded for now.


Subscribe to curious little things aggregator