Catégories

# Infinitely Many Hats (3/3)

This is the last in a series of three exercices de style to show some interesting aspects of the game of hats: a puzzle which was initially proposed by Lionel Levine.

Here we look at case where each player has a tower of countably infinitely many hats on their head and try constructing efficient strategies from the results of the first exercice.

## Definitions and notations

### Towers and strategies

We use notations inspired by .

Let $\mathbb{T}_{<\mathbb{N}}$ denote the set of all towers of finite height and $\mathbb{T}_{\mathbb{N}}$ the set of towers of countably infinite height.

\begin{align}
\mathbb{T}_{<\mathbb{N}}
&\stackrel{\text{def}}{=}\bigcup_{n\in\mathbb{N}} \mathbb{T}_n\\
\mathbb{T}_{\mathbb{N}}
&\stackrel{\text{def}}{=}[2]^{\mathbb{N}}
\end{align}

$\mathbb{T}_{<\mathbb{N}}$ is countable but $\mathbb{T}_{\mathbb{N}}$ has the cardinality of the real line. $\mathbb{T}_{\mathbb{N}}$ is also known as the Cantor space.

Let $\mathbb{S}_{\mathbb{N}}$ denote the set of strategies for the game of hats with towers of countably infinite height. A (symmetric) strategy maps a tower to a chosen position:

\begin{align}
\mathbb{S}_{\mathbb{N}}
&\stackrel{\text{def}}{=}{\mathbb{Z}}^{\mathbb{T}_{\mathbb{N}}}
\end{align}

$\mathbb{S}_{\mathbb{N}}$ has cardinality strictly greater than the real line.

### Hit set and win rate

With infinite towers we can still use $\eta_{t,u}(s)$ to denote the outcome of applying strategy $s\in\mathbb{S}_{\mathbb{N}}$ to the configuration $(t,u)$, however it is no longer possible to calculate the hit score as a sum and the win rate as a mean value.

We substitute with $\eta(s)$, the hit set of strategy $s$:

\eta(s)\stackrel{\text{def}}{=}\{(t,u)\in\mathbb{T}_{\mathbb{N}}\times\mathbb{T}_{\mathbb{N}}\mid\eta_{t,u}(s)=1\},

and write $\mu(s)$ for the win rate of strategy $s$, defined as the Baire/Borel measure of $\eta(s)$ in the space $\mathbb{T}_{\mathbb{N}}\times\mathbb{T}_{\mathbb{N}}$ (when it is measurable).

\mu(s)\stackrel{\text{def}}{=}\mu(\eta(s)).

### Embedding

For convenience we identify the towers in $\mathbb{T}_n$ with towers in $\mathbb{T}_{\mathbb{N}}$ (by completing with black hats) and the strategies in $s\in\mathbb{S}_n$ with strategies in $s\in\mathbb{S}_{\mathbb{N}}$ (by discarding hats at position $n$ and beyond).

Thus we loosely write $s(t)$ and $eta_{t,u}(s)$ even when $s$, $t$ and $u$ are a mix of finite/infinite strategies and towers.

\begin{align}
\forall i<j, \;\;
\left\{
\begin{array}{l}
\mathbb{T}_i
\subset \mathbb{T}_j
\subset \mathbb{T}_{<\mathbb{N}}
\subset \mathbb{T}_{\mathbb{N}}\\
\mathbb{S}_i
\subset \mathbb{S}_j
\subset \mathbb{S}_{\mathbb{N}}\\
\end{array}
\right.
\end{align}

## Limits

### Infinite towers as limits of finite towers

Every tower $t\in\mathbb{T}_{\mathbb{N}}$ is the limit of a sequence of towers in $\mathbb{T}_{<\mathbb{N}}$ (with the topology of the Cantor space).

Proof: if $s\!\mid\!k$ denotes the initial segment of $s$ of size $k\in\mathbb{N}$, then:

s = \lim_{n\to\infty} s\!\mid\!n

In fact, we can view $t\in\mathbb{T}_{\mathbb{N}}$ as the Cauchy completion of $t\in\mathbb{T}_{<\mathbb{N}}$.

### Finite strategies are continuous

A finite strategy $s\in\mathbb{S}_n$, embedded into $\mathbb{S}_{\mathbb{N}}$ as a mapping $s: \mathbb{T}_{\mathbb{N}} \to \mathbb{Z}$, is continuous.

### Limits of strategies

Here we allow strategies as functions $s: \mathbb{T}_{\mathbb{N}} \to \mathbb{Z}$ with partial domain.

Given a sequence $s_n\in\mathbb{S}_{\mathbb{N}}$ we define its pointwise limit:

\begin{align}
\lim (s_n):\; &\big\{t\mid \lim_{n\to\infty} s_n(t)\text{ exists}\big\} \to \mathbb{Z}\\
&\;t \mapsto \lim_{n\to\infty} s_n(t) \nonumber
\end{align}

It is natural to try constructing efficient infinite strategies as limits of finite strategies.

## Infinite lowest-white strategy

Consider the infinite lowest-white strategy $\mathbf{W}_\omega$:

\mathbf{W}_\omega \stackrel{\text{def}}{=} \lim_{n\to\infty} \mathbf{W}_n

$\mathbf{W}_\omega$ has win rate $1\over3$.

### Proof

Considering all towers in $\mathbb{T}_{\mathbb{N}}$, let’s represent the combined output of the $\mathbf{W}_n$ strategies as a tree, as shown in the picture below:

Let’s denote in gray the points where the pointwise limit is reached:

We see that $\mathbf{W}_\omega=\lim(\mathbf{W}_n)$ is defined almost everywhere1 with respect to the Baire/Borel measure, and we can squeeze its hit set the following way:

I_k \subset \eta(\mathbf{W}_\omega) \subset S_k

where:

$$\left\{ \begin{array}{l} I_k = \eta(\mathbf{W}_k) \setminus U_k\\ S_k = \eta(\mathbf{W}_k) \cup U_k\\ U_k = \big\{(t,u)\mid \text{ card}\bigcup_{i\geq k}\{\mathbf{W}_i(t)\}\neq1 \text{ or card}\bigcup_{i\geq k}\{\mathbf{W}_i(u)\}\neq1\big\} \end{array} \right.$$

$I_k$ is an increasing sequence of sets and $S_k$ is a decreasing sequence, with $\lim_{k\to\infty} \mu(U_k) = 0$, $\lim_{k\to\infty} \mu(I_k) = 1/3$, $\lim_{k\to\infty} \mu(S_k) = 1/3$, hence $\mu(\mathbf{W}_\omega) = 1/3$. $\quad \Box$

Note (as shown in the picture below) that $\mathbf{W}_\omega$ is a computable function and can be written as a finite automaton that processes the stream of hats from $t\in\mathbb{T}_{\mathbb{N}}$:

## Infinite Carter strategy

Consider the infinite Carter strategy $\mathbf{C}_\omega$:

\mathbf{C}_\omega \stackrel{\text{def}}{=} \lim_{n\to\infty}
\mathbf{X}_n,

where:

$$\left\{ \begin{array}{l} \mathbf{X}_{2k-1} = \mathbf{C}_k\!\mid\!(2k-1)\\ \mathbf{X}_{2k} = \mathbf{C}_k\!\mid\!(2k) \end{array} \right.$$

$\mathbf{W}_\omega$ has win rate $7\over20$.

### Proof

Considering all towers in $\mathbb{T}_{\mathbb{N}}$, let’s represent the combined output of the $\mathbf{X}_n$ strategies as a tree, as shown in the picture below:

Let’s denote in gray the points where the pointwise limit is reached:

We see that $\mathbf{C}_\omega=\lim(\mathbf{X}_n)$ is defined everywhere, and we can squeeze its hit set the following way:

I_k \subset \eta(\mathbf{C}_\omega) \subset S_k

where:

$$\left\{ \begin{array}{l} I_k = \eta(\mathbf{X}_k) \setminus U_k\\ S_k = \eta(\mathbf{X}_k) \cup U_k\\ U_k = \big\{(t,u)\mid \text{ card}\bigcup_{i\geq k}\{\mathbf{X}_i(t)\}\neq1 \text{ or card}\bigcup_{i\geq k}\{\mathbf{X}_i(u)\}\neq1\big\} \end{array} \right.$$

$I_k$ is an increasing sequence of sets and $S_k$ is a decreasing sequence, with $\lim_{k\to\infty} \mu(U_k) = 0$, $\lim_{k\to\infty} \mu(I_k) = 7/20$, $\lim_{k\to\infty} \mu(S_k) = 7/20$, hence $\mu(\mathbf{C}_\omega) = 7/20$. $\quad \Box$

Note (as shown in the picture below) that $\mathbf{C}_\omega$ is a computable function almost everywhere2 and can be written as a finite automaton that processes the stream of hats from $t\in\mathbb{T}_{\mathbb{N}}$:

## Infinite Reyes strategy

Consider the infinite Reyes strategy $\mathbf{R}_\omega$:

\mathbf{R}_\omega \stackrel{\text{def}}{=} \lim_{n\to\infty}
\mathbf{X}_n,

where:

$$\left\{ \begin{array}{ll} \mathbf{X}_{3k-2} &= \mathbf{C}_k\!\mid\!(3k-2)\\ \mathbf{X}_{3k-1} &= \mathbf{C}_k\!\mid\!(3k-1)\\ \mathbf{X}_{3k} &= \mathbf{C}_k\!\mid\!(3k) \end{array} \right.$$

$\mathbf{W}_\omega$ has win rate $7\over20$.

### Proof

Considering all towers in $\mathbb{T}_{\mathbb{N}}$, let’s represent the combined output of the $\mathbf{X}_n$ strategies as a tree, as shown in the picture below:

Let’s denote in gray the points where the pointwise limit is reached:

We see that $\mathbf{R}_\omega=\lim(\mathbf{X}_n)$ is defined almost everywhere3, and we can squeeze its hit set the following way:

I_k \subset \eta(\mathbf{C}_\omega) \subset S_k

where:

$$\left\{ \begin{array}{l} I_k = \eta(\mathbf{X}_k) \setminus U_k\\ S_k = \eta(\mathbf{X}_k) \cup U_k\\ U_k = \big\{(t,u)\mid \text{ card}\bigcup_{i\geq k}\{\mathbf{X}_i(t)\}\neq1 \text{ or card}\bigcup_{i\geq k}\{\mathbf{X}_i(u)\}\neq1\big\} \end{array} \right.$$

$I_k$ is an increasing sequence of sets and $S_k$ is a decreasing sequence, with $\lim_{k\to\infty} \mu(U_k) = 0$, $\lim_{k\to\infty} \mu(I_k) = 7/20$, $\lim_{k\to\infty} \mu(S_k) = 7/20$, hence $\mu(\mathbf{R}_\omega) = 7/20$. $\quad \Box$

Note (as shown in the picture below) that $\mathbf{R}_\omega$ is a computable function on its definition domain and can be written as a finite automaton that processes the stream of hats from $t\in\mathbb{T}_{\mathbb{N}}$:

## References

Kechris, A. S. (2012). Classical descriptive set theory. Springer.
1. In fact $\mathbf{W}_\omega$ is defined everywhere except at $(0, 0, \cdots)$
2. $\mathbf{W}_\omega$ is not computable only at points $(0,0,\cdots)$ and $(1,1,\cdots)$
3. $\mathbf{R}_\omega$ is defined for all $t$ such that $\exists k, \text{ card}\{t_{3k},t_{3k+1},t_{3k+2}\}\neq1$

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.