Solved and unsolved problems

The present column is devoted to probability theory.

I Six new problems – solutions solicited

Solutions will appear in a subsequent issue.

284

Let $V$ be a finite set and $\tilde{V}\subset V$. For a finite path $\mathbf{w}=(w_0,w_1,\dots ,w_{\eta })$ on $V$, we let $n_0=0$, and for $i\ge 1$, we let

We call ${\mathfrak{L}}_{\tilde{V}}(\mathbf{w}):=(w_{n_0},w_{n_1},\dots ,w_{n_{\iota }})$, where $n_{\iota }$ is the last index found by the algorithm, the partial loop erasure (PLE) of $\mathbf{w}$.

Let $(X_n,{\mathbb{P}}_x)$ be a discrete-time irreducible Markov chain on a finite set $V$, and let ${\sigma }_A=\min \{n\ge 0:X_n\in A\}$ and $X{|}_{[0,{\sigma }_A]}=(X_0,X_1,\dots ,X_{{\sigma }_A})$. Prove that

where $\stackrel{(d)}{=}$ means that both sides have the same law.

Shiping Cao (Department of Mathematics, University of Washington, Seattle, USA)

This problem is a simplified version of Theorem 1 of my recent paper: S. Cao, Scaling limits of loop-erased Markov chains on resistance spaces via a partial loop-erasing procedure. Adv. Math.435, part B, article no. 109382 (2023).

285

The following democratic process is implemented in a population of $N$ sheep during a Yes/No referendum. At the initial time $t=0$, $m$ sheep are pro-Yes, and $N-m$ sheep are pro-No. At each time $t=1,2,\dots$, a sheep is randomly chosen (independently of what happened before) and it bleeps its opinion. Instantly, a sheep from the opposite camp (if at least one remains) switches its opinion. The process stops when a consensus is reached.

We denote by $P_{m,N}$ the probability that “Yes” wins when starting with $m$ pro-Yes sheep in the population. Of course, $P_{0,N}=0$, $P_{N,N}=1$, and, due to the symmetry of the problem, $P_{N,2N}=1/2$.

Question.

Find a simple expression for $P_{m,N}$. (In particular, this expression should allow you to estimate very easily the evolution of this probability when starting from a very small majority, i.e., estimate $P_{N+a_N,2N}$ for different sequences $1\ll a_N\ll N$.)

Lucas Gerin (CMAP, École Polytechnique, Palaiseau, France)

286

Let $\alpha \in \mathbb{R}$ and consider the transition probability density $P(x;t|y)$ from a point $y\ge 0$ after a time $t>0$ of a Brownian motion on the non-negative real line with reflecting boundary conditions; in particular, $P(x;t|y)$ is the weak solution of the following initial value problem with Robin boundary condition:

1. ${\partial }_{t}P(x;t|y)=\alpha {\partial }_{x}P(x;t|y)+\frac{1}{2}{\partial }_x^{2}P(x;t|y)$ for all $x,y\ge 0$ and $t>0$;

2. $[2\alpha P(x;t|y)+{\partial }_{x}P(x;t|y){]}_{x=0}=0$ for all $t>0$, where the derivative at the origin is the one-sided right derivative;

3. ${\lim }_{t\to 0}{\int }_0^{\infty }f(x)P(x;t|y)dx=f(y)$ for all bounded continuous functions $f$ and $y\ge 0$.

Prove that the solution is given by

for any $x,y\ge 0$ and $t>0$, where $\mathrm{erfc}(x)=\frac{2}{\sqrt{\pi }}{\int }_x^{\infty }{e}^{-y^2}dy$ is complementary error function and ${\partial }_x$ is the partial derivative with respect to $x$.

Mario Kieburg (School of Mathematics and Statistics, University of Melbourne, Parkville, Melbourne, Australia)

287

We place $n$ different pairs of socks in a tumble dryer. When the dryer has thoroughly mixed the socks, they are taken out one by one. If a sock is the partner of one of the socks on the sorting table, both are removed, otherwise it is put on the table until its partner emerges from the dryer. For $k\in \{1,\dots ,2n\}$, let $X_k$ be the number of socks on the table when the $k$th sock is taken from the dryer. With $X_0=0$, the random path $(X_0,\dots ,X_{2n})$ is a Dyck path. Recall that a path $(x_0,\dots ,x_{2n})$ is called a Dyck path if $|x_i-x_{i+1}|=1$, $x_i\ge 0$ for $1\in \{1,\dots ,2n-1\}$ and $x_0=x_{2n}=0$.

The number of Dyck paths of a given length is given by the Catalan numbers, but not all Dyck paths come up with the same probability in the sock sorting process. For example, for $n=2$ there are two Dyck paths, $(0,1,0,1,0)$ and $(0,1,2,1,0)$. The former has probability $\frac{1}{3}$ and the latter $\frac{2}{3}$. The problem is now, given a Dyck path $(x_0,\dots ,x_{2n})$ of arbitrary length, to find a formula for the probability

Peter Mörters (University of Cologne, Germany)

288

In a university hospital, there are 9 major medical departments performing surgery. The cardiology unit performs 21% of all surgeries conducted hospital-wide, with 5% of total cardiac surgeries occurring at least twice a day. A total of 30 patients are assigned to surgery. Assuming that surgeries are equally likely on any given day of the year, if two or more surgeries occur on the same day, what is the probability that they are assigned to the cardiology unit?

Gaetano Valenza (Bioengineering and Robotics Research Center “E. Piaggio” & Department of Information Engineering, School of Engineering, University of Pisa, Italy)

289

It is the king’s birthday, and he decides to please the republican sentiments in the population and release some prisoners who are held for their republican views. The prisoners all have equally excellent rational skills and are placed in separate castles, so that they are unable to speak and communicate with each other. The king decides to challenge the prisoners and gives each of them a coin. Within a quarter of an hour, each of them, say $n$ prisoners, has to decide whether to toss the coin or not. If at least one coin is tossed and all coins being tossed show head, all $n$ prisoners are released, otherwise none of them are. The king believes the prisoners have a slim chance of being released. But is that so? What is the probability that they all are released? The prisoners are told the number $n$.

Carsten Wiuf (Department of Mathematical Sciences, University of Copenhagen, Denmark)

II Open problems

by Van Vu (Department of Mathematics, Yale University, USA)

Open problems on random matrices

Let $M_n$ be a random matrix of size $n$ whose entries are iid $\pm 1$ random variables (with probability $1/2$ each). It is known that most of the eigenvalues of this matrix, with high probability, are complex and distribute by the circular law [⁠2⁠ T. Tao and V. Vu, From the Littlewood–Offord problem to the circular law: universality of the spectral distribution of random matrices. Bull. Amer. Math. Soc. (N.S.) 46, 377–396 (2009) ]. The question here is that how many are real.

The following conjecture is motivated by my joint work with T. Tao in [⁠3⁠ T. Tao and V. Vu, Random matrices: Universality of local spectral statistics of non-Hermitian matrices. Ann. Probab. 43, 782–874 (2015) ].

290*. Conjecture (real eigenvalues)

$M_n$ has, with probability $1-o(1)$, $\Theta (\sqrt{n})$ real eigenvalues.

Edelman, Kostlan, and Shub [⁠1⁠ A. Edelman, E. Kostlan and M. Shub, How many eigenvalues of a random matrix are real? J. Amer. Math. Soc. 7, 247–267 (1994) ] obtained a precise formula for the expectation of the number of real eigenvalues for a Gaussian matrix, which is of order $\sqrt{n}$. In [⁠3⁠ T. Tao and V. Vu, Random matrices: Universality of local spectral statistics of non-Hermitian matrices. Ann. Probab. 43, 782–874 (2015) ], Tao and Vu proved that the same formula holds (in the asymptotic sense) for certain random matrices with entries $0,\pm 1$, as a part of a Four Moment Theorem for non-symmetric matrices. However, we cannot extend the proof to $M_n$. As a matter of fact, it is not known that with high probability, $M_n$ has at least 2 real roots.

The next problem bears some resemblance to the famous “rigidity” problem in computer science. Given a $\pm 1$ matrix $M$, let $\mathrm{Res}(M)$ denote the minimum number of entries we need to switch (from 1 to $-1$ and vice versa) in order to make $M$ singular. Thus, $\mathrm{Res}(M)$ can be seen as the resilience of $M$ against an effort to reduce its rank. It is easy to show that $\mathrm{Res}(M_n)$ is, with high probability, at most $(1/2+o(1))n$, it typically takes this many switches to make the first two rows of the matrix equal.

291*. Conjecture (rank resilience)

With probability $1-o(1)$, $\mathrm{Res}(M_n)=(1/2+o(1))n$.

For more discussion and related problems, we refer to [⁠4⁠ V. H. Vu, Recent progress in combinatorial random matrix theory. Probab. Surv. 18, 179–200 (2021) ].

III Solutions

276

Consider the tiling of the plane by regular hexagon tiles, with centers in the lattice $L$ of all $\mathbb{Z}$-linear combinations of the vectors $(1,0)$ and $(-\frac{1}{2},\frac{\sqrt{3}}{2})$. Glue all but finitely many tiles into position, remove the unglued tiles to form a region, discard some of these tiles, and arrange the remaining $n$ unglued tiles in the region without rotating them, in arbitrary positions such that none of the tiles overlap. Is there a way to slide the unglued tiles within the region, keeping them upright and non-overlapping, so that their centers all end up in $L$?

Hannah Alpert (Department of Mathematics and Statistics, Auburn University, USA)

Solution by the proposer

Yes. We think of tiles as being specified by their centers, so we use the word “tile” to mean “center of a tile” whenever the meaning is unambiguous. Our first lemma shows that it suffices to slide the tiles to $L^{\ast }$, which we define to be the lattice that contains $L$ as well as all the vertices of the hexagons of the original tiling. This lattice $L^{\ast }$ is generated by the vectors $(0,\frac{\sqrt{3}}{3})$ and $(\frac{1}{2},\frac{\sqrt{3}}{6})$, which are orthogonal to $(1,0)$ and $(-\frac{1}{2},\frac{\sqrt{3}}{2})$, respectively.

We want to slide from an arbitrary tile arrangement to $L^{\ast }$. In the starting arrangement, sliding is obstructed by tangencies, which are pairs of tiles that touch. When two tiles touch only at vertices, we call it a double tangency. We can make a graph of all tangencies by drawing an edge between the centers of each pair of tiles that are tangent, whether they are both unglued tiles, or one unglued and one glued, or both glued; this graph is embedded in the plane. Any subset of the tangencies determines a linear subspace of ${\mathbb{R}}^{2n}$, consisting of the infinitesimal perturbations of the unglued tiles that preserve those tangencies. If a pair of tiles is tangent but the tangency is not included in the subset, the perturbation is allowed to destroy the tangency, either by making the tiles overlap, or by creating a gap between them. We say that a tangency graph is rigid if this linear subspace of perturbations is trivial.

Our strategy for sliding all tiles to $L^{\ast }$ is to find a perturbation direction that preserves all the tangencies, and slide in that direction until a new tangency forms. Then we find a perturbation direction that preserves all the tangencies, including the new one, slide in that direction, and so on, until the graph of all tangencies becomes rigid. The next lemma completes the proof.

277

Find two non-homeomorphic topological spaces $A$ and $B$ such that their products with the interval, $A\times [0,1]$ and $B\times [0,1]$, are homeomorphic.

Guillem Cazassus (Mathematical Institute, University of Oxford, UK)

Solution by the proposer

One can take $A$ the 2-sphere with 3 discs removed, and $B$ the 2-torus with one disc removed. These can both be seen as obtained from the 2-disc by attaching two 1-handles, as in Figure ⁠1⁠. After taking their products with $[0,1]$, the extra dimension added allows to exchange the attaching positions of the handles to go from the first picture to the second.

278

What is the topology of the space of straight lines in the plane?

Guillem Cazassus (Mathematical Institute, University of Oxford, UK)

Solution by the proposer

Call this space $\mathcal{M}$. It is an open Möbius strip: here are two possible ways to see this.

Solution 1:

Let ${\mathcal{M}}_0\subset \mathcal{M}$ correspond to the lines passing through the origin. Then ${\mathcal{M}}_0$ is a circle $\mathbb{R}/\pi \mathbb{Z}$, and one can consider the projection $\mathcal{M}\to {\mathcal{M}}_0$ sending a line to its parallel passing through 0. This is a fibration, with fiber $\mathbb{R}$, and the inclusion ${\mathcal{M}}_0\hookrightarrow \mathcal{M}$ gives a section of it. There are two such fibrations possible: the trivial one (cylinder) and the Möbius strip. The one we consider cannot be trivial, otherwise it would mean that one can find another section disjoint from ${\mathcal{M}}_0$. This would mean that one can take a given line disjoint from the origin, and half-twist it continuously without hitting the origin. Therefore, it is the Möbius strip.

Solution 2:

We can view $\mathcal{M}$ as the quotient of ${\mathcal{M}}^{\mathrm{or}}$, the space of oriented lines. First, ${\mathcal{M}}^{\mathrm{or}}$ can be identified with the cylinder $(\mathbb{R}/2\pi \mathbb{Z})\times \mathbb{R}$, the first coordinate being the angle with the horizontal axis, and the second the “algebraic distance” to the origin (take the distance, and put a minus sign if the origin is at the left of the line).

Second, under this identification, the involution reversing the orientation of a line is the map $\iota :(\theta ,d)\mapsto (\theta +\pi ,-d)$, and $\mathcal{M}\simeq {\mathcal{M}}^{\mathrm{or}}/\iota$. It follows that $\mathcal{M}$ can be obtained from the strip $[0,\pi ]\times \mathbb{R}$ (a fundamental domain for $\iota$) by identifying its two edges by the twist $(0,d)\sim (\pi ,-d)$, which gives a Möbius strip.∎

279

In the standard twin paradox, Greg stays at home whilst John travels across space. John finds, upon returning, that he has aged less than Greg. This is an apparent paradox because of the symmetry in the situation: in John’s rest frame, it seems like Greg is doing the moving and so should also be experiencing time dilation. The standard explanation of the paradox is that there is no symmetry: at some point John needs to turn around (accelerate), so, unlike Greg, John’s rest frame is not inertial for all times. So let’s modify the set-up: suppose that space-time is a cylinder (space is a circle). Now, John eventually comes back to where he started without needing to decelerate or accelerate. In this fleeting moment of return, as the twins pass one another, who has aged more?

Jonny Evans (Department of Mathematics and Statistics, University of Lancaster, UK)

Solution by the proposer

John has aged more. You can just integrate to compute his proper time and see it is smaller. If the speed of John is $v$, the size of the universe is $L$ and the speed of light is $c$, then the proper time until return measured by John is

against Greg’s $L/v$.

But why is this not a paradox? Again, the problem is that, despite appearances, there is no symmetry in the situation. In other words, there is no global isometry of space-times interchanging their rest frames. Space-time is foliated by a distinguished family of closed space-like geodesic loops. These are orthogonal to Greg’s world-line, but not to John’s. This means that, unlike in Minkowski space-time, John could do an experiment to figure out that he is moving. For example, suppose that Greg sees John moving to the right. If John emits a red light ray leftwards and a blue light ray rightwards, and waits for them to circle around the universe, he will see the red light ray return first; see Figure ⁠2⁠.∎

You can read a more leisurely discussion of this version of the twin paradox in the following paper: J. R. Weeks, The twin paradox in a closed universe. Amer. Math. Monthly108, 585–590 (2001).

280

The $k$-dilation of a piecewise smooth map is the degree to which it stretches $k$-dimensional area. Formally, for a map $f:U\to V$ between subsets $U\subseteq {\mathbb{R}}^m$ and $V\subseteq {\mathbb{R}}^n$, or more generally between Riemannian manifolds,

where ${\Lambda }^{k}D{f}_x:{\Lambda }^k{T}_{x}U\to {\Lambda }^k{T}_{f(x)}V$ is the induced map on the $k$-th exterior power and $|\cdot |$ is the operator norm. A map of rank $k-1$ has $k$-dilation zero, so this can be thought of as a quantitative refinement of rank.

Consider the rectangular prism $R_{\epsilon }=[0,1{]}^2\times [0,\epsilon ]$.

1. Let $f:R_1\to R_{\epsilon }$ be a map of relative degree$1$, that is, it restricts to a degree-$1$ map between the boundaries of the rectangles. Show that the $2$-dilation of such a map is bounded below by a $C>0$ which does not depend on $\epsilon$.

2. Now let $c_{\epsilon }$ be the minimum $2$-dilation of a surjective map $f:R_1\to R_{\epsilon }$. Construct examples to show that $c_{\epsilon }\to 0$ as $\epsilon \to 0$.

Fedor (Fedya) Manin (Department of Mathematics, University of California, Santa Barbara, USA)

Solution by the proposer

1. The statement follows from applying the idea that “$2$-dilation is the degree to which the map stretches area of surfaces” to the boundary. Let $f:R_1\to R_{\epsilon }$ be a map of relative degree $1$, and write $dA$ for the area form on $\partial R_{\epsilon }$. By the definition of degree,

   $$\mathrm{Area}(\partial R_{\epsilon })={\int }_{\partial R_1}{f}^{\ast }dA.$$

   Now, $f^{\ast }dA(v_1\wedge v_2)=dA(Df(v_1)\wedge Df(v_2))\le {\mathrm{Dil}}_2(f)|v_1\wedge v_2|$, and therefore

   $$\mathrm{Area}(\partial R_{\epsilon })\le {\mathrm{Dil}}_2(f)\mathrm{Area}(\partial R_1).$$

   Therefore, ${\mathrm{Dil}}_2(f)\ge 1/3$.

2. Assume that $\epsilon =n^{-3}$ for some integer $n$. We will construct a map $f:R_1\to R_{\epsilon }$ with ${\mathrm{Dil}}_2(f)=16n^{-2}=16{\epsilon }^{2/3}$. The basic idea is to use the fact that $R_1$ has much larger volume than $R_{\epsilon }$. Some portion of that volume will be cut up into chunks, shrunk down by a factor of around $n$, and distributed surjectively over $R_{\epsilon }$. The rest will be used to make the map continuous; this may be highly distorted, but does not contribute to the $2$-dilation because it maps to a one-dimensional subspace of $R_{\epsilon }$.

   Split $R_{\epsilon }$ into an $n^3\times n^3$ grid of cubes $K_1,\dots ,K_{n^6}$ of side length $n^{-3}$. These are in one-to-one correspondence with an $n^2\times n^2\times n^2$ grid of cubes $L_1,\dots ,L_{n^6}$ in $R_1$ of side length $n^{-2}$. Let $L_i^{\prime }$ be the cube of side length $\frac{2}{3}{n}^{-2}$ which is concentric with $L_i$. We define $f$ on each $L_i^{\prime }$ so that it maps $\partial L_i^{\prime }$ to the center of $K_i$ and the interior of $L_i^{\prime }$ surjectively over $K_i$, with $Df{|}_{\partial L_i^{\prime }}=0$. Such a map can be made $4n^{-1}$-Lipschitz, and therefore its $2$-dilation is $16n^{-2}$. Outside the $L_i^{\prime }$, we can extend this map to a smooth map whose image is a tree embedded in $R_{\epsilon }$, the vertices of which are the centers of the $K_i$. Since the tree is one-dimensional, the $2$-dilation of this portion is zero.

This problem demonstrates a tension frequently encountered in metric geometry. Suppose you are trying to construct a map between two spaces with certain properties and geometric bounds. When you try to do it the obvious way, the geometric complexity blows up in one direction but stays very small in another. Can the map be modified by “trading off” these dimensions while preserving the desired properties?

Both halves of the problem are inspired by research papers: (⁠2⁠) is an approximate version of a construction by Kaufman of a rank $1$ map from the cube to the square [⁠7⁠ R. Kaufman, A singular map of a cube onto a square. J. Differential Geometry 14, 593–594 (1979) ], while (⁠1⁠) is a simple case of a complex and surprising result of Guth [⁠6⁠ L. Guth, The width-volume inequality. Geom. Funct. Anal. 17, 1139–1179 (2007) , Theorem 2]. For other pairs of rectangles Guth shows, using a very different construction, that one can trade off between different dimensions to some degree even while constructing maps of relative degree $1$. Both Kaufman’s and Guth’s constructions have inspired further work. For instance, Wenger and Young [⁠8⁠ S. Wenger and R. Young, Lipschitz homotopy groups of the Heisenberg groups. Geom. Funct. Anal. 24, 387–402 (2014) ] used a construction similar to Kaufman’s to show that certain Lipschitz maps from spheres to Heisenberg groups (unexpectedly!) have Lipschitz extensions to balls. In contrast, Goldstein, Hajłasz and Pankka [⁠5⁠ P. Goldstein, P. Hajłasz and P. Pankka, Topologically nontrivial counterexamples to Sard’s theorem. Int. Math. Res. Not. IMRN, no. 20, 7073–7096 (2020) ] used a Kaufman-style construction to create low-rank maps $S^{n+1}\to S^n$ which are actually topologically nontrivial.

281

Given a triangle in the (real or complex) plane, show that there is a natural bijection between the set of smooth conics passing through the vertices and the set of lines avoiding the vertices.

Jack Smith (St John’s College, University of Cambridge, UK)

Proof by the proposer

Suppose $C$ is a conic through the vertices $P$, $Q$, and $R$ of the triangle, and let ${\ell }_P$, ${\ell }_Q$, and ${\ell }_R$ be its respective tangent lines at these points. By Pascal’s theorem, the intersections ${\ell }_P\cap QR$, ${\ell }_Q\cap RP$, and ${\ell }_R\cap PQ$ are collinear, lying on a line $L$ say. We claim that the map $C\mapsto L$ (is well defined and) gives the desired bijection.

To prove this, take homogeneous coordinates $[x:y:z]$ on the plane in which $P$, $Q$, and $R$ are $[1:0:0]$, $[0:1:0]$, and $[0:0:1]$, respectively.

A general conic through these points is described by the equation

for a unique $[a:b:c]$ in ${\mathbb{P}}^2$. The conic is smooth if and only if $a$, $b$, and $c$ are all non-zero. Meanwhile, a general line in the plane is described by the equation

and it avoids $P$, $Q$, and $R$ if and only if $\alpha$, $\beta$, and $\gamma$ are all non-zero. It therefore remains to show that the map $C\mapsto L$ induces a bijection from triples of non-zero scalars $(a,b,c)$ to triples of non-zero scalars $(\alpha ,\beta ,\gamma )$.

Suppose then that $C$ is the smooth conic

Differentiating, we see that the line ${\ell }_P$ is $cy+bx=0$, so

Similarly ${\ell }_Q\cap RP=[-a:0:c]$ and ${\ell }_R\cap PQ=[a:-b:0]$, and we see that there is a unique line $L$ through these points, with the equation

So the map $C\mapsto L$ is well defined and corresponds to

This is a bijection, with inverse

so we are done. ∎

We wait to receive your solutions to the proposed problems and ideas on the open problems. Send your solutions to Michael Th. Rassias by email to mthrassias@yahoo.com.

We also solicit your new problems with their solutions for the next “Solved and unsolved problems” column, which will be devoted to discrete mathematics.

References

1. A. Edelman, E. Kostlan and M. Shub, How many eigenvalues of a random matrix are real? J. Amer. Math. Soc. 7, 247–267 (1994)
2. T. Tao and V. Vu, From the Littlewood–Offord problem to the circular law: universality of the spectral distribution of random matrices. Bull. Amer. Math. Soc. (N.S.) 46, 377–396 (2009)
3. T. Tao and V. Vu, Random matrices: Universality of local spectral statistics of non-Hermitian matrices. Ann. Probab. 43, 782–874 (2015)
4. V. H. Vu, Recent progress in combinatorial random matrix theory. Probab. Surv. 18, 179–200 (2021)
5. P. Goldstein, P. Hajłasz and P. Pankka, Topologically nontrivial counterexamples to Sard’s theorem. Int. Math. Res. Not. IMRN, no. 20, 7073–7096 (2020)
6. L. Guth, The width-volume inequality. Geom. Funct. Anal. 17, 1139–1179 (2007)
7. R. Kaufman, A singular map of a cube onto a square. J. Differential Geometry 14, 593–594 (1979)
8. S. Wenger and R. Young, Lipschitz homotopy groups of the Heisenberg groups. Geom. Funct. Anal. 24, 387–402 (2014)