# Probabilistic Burnside groups

Gil Goffer  Department of Mathematics, University of California, San Diego, La
Jolla, CA, 92093, USA<EMAIL_ADDRESS>and  Be’eri Greenfeld  Department of
Mathematics, University of California, San Diego, La Jolla, CA, 92093, USA
<EMAIL_ADDRESS>
###### Abstract.

We construct probabilistic Burnside groups containing non-abelian free
subgroups. These are finitely generated groups in which the probability that a
random element, chosen uniformly from a finite ball in its Cayley graph or via
a non-degenerate random walk, satisfies a group law of the form $x^{k}=1$ with
probability is tending to $1$. In particular, this answers an open question
posed by Amir, Blachar, Gerasimova, and Kozma, and gives the first example of
a finitely generated group which satisfies a group law with probability $1$ –
but does not satisfy any group law.

##  1\. Introduction

The Burnside Problem [3] asks whether a finitely generated group of finite
exponent must be finite. Equivalently, whether the free Burnside group:

$B(m,k)=\left<x_{1},\dots,x_{m}\ |\ w^{k}=1\ \text{for every word}\ w\
\text{in}\ x_{1},\dots,x_{m}\right>$

is finite for every positive integers $m,k$. This problem has been settled in
1968 by Novikov and Adian [5] who proved that $B(m,k)$ can be infinite for
suitable $m,k$; see also [1]. Ol’shanskii [6, 7] introduced a geometric
approach to Burnside groups, constructing infinite Burnside groups using small
cancellation theory and the theory of hyperbolic groups; see also [4].

A group law of a group $G$ is a nontrivial element $w\in F(x_{1},x_{2},\dots)$
in the free group which vanishes under any substitution from $G$. For
instance, the commutator $[x_{1},x_{2}]$ is a group law for any abelian group,
the iterated commutator law $[x_{1},[x_{2},[\cdots[x_{l},x_{l+1}]\cdots]$ is a
group law for any $l$-step nilpotent group, and the free Burnside group
$B(m,k)$ satisfies the group law $w=x^{k}$.

Let us take a probabilistic approach. Let $\vec{\mu}=(\mu_{n})_{n=1}^{\infty}$
be a sequence of probability measures on an infinite group $G$. Define the
probability that $G$ satisfies a group law $w$ with respect to $\vec{\mu}$ by:

$\Pr_{G,\vec{\mu}}(w=1):=\limsup_{n\rightarrow\infty}\Pr_{g_{1},\dots,g_{d}\sim\mu_{n}}\left(w(g_{1},\dots,g_{d})=1\right)$

where in the $n$-th term of the limit, $g_{1},\dots,g_{d}$ are independent
random variables with distribution $\mu_{n}$. We say that a word $w$ is a
$\vec{\mu}$-probabilistic group law if:

$\Pr_{G,\vec{\mu}}(w=1)=1.$

A natural question that arises is: given a group satisfying a probabilistic
law, how close is it to satisfying an actual group law?

Natural sequences of measures to consider are:

  * •

Uniform measures on balls of the Cayley graph. Fix a finite symmetric
generating set $S$ of $G$. Let $B_{G,S}(n)$ denote the $n$-ball of the Cayley
graph of $G$ with respect to $S$ and let $\mu_{n}$ be the uniform distribution
on $B_{G,S}(n)$.

  * •

Random walks. Fix a finitely supported step distribution $\mu$ on $G$ whose
support generates $G$ as a semigroup. Let $\mu_{n}=\mu^{*n}$.

See [2] for a thorough discussion of the various notions of probabilistic
group laws. In [2] the authors construct, for any $\varepsilon>0$, a finitely
generated group $G$ and a generating set $S$ such that for the sequence of
measures induced by random walks $\vec{\mu}=(\mu^{*n})_{n=1}^{\infty}$ (where
$\mu$ is a uniform distribution on $S$), $G$ satisfies
$\Pr_{G,\vec{\mu}}(w=1)>1-\varepsilon$, yet $G$ contains a free subgroup.
However, their generating set (and hence the sequence of measures) varies as
$\varepsilon$ is taken to be smaller and smaller. Another notion of
probabilistic laws, applicable to residually finite groups can be found in
[8].

In this paper we construct a probabilistic Burnside group which contains a
free subgroup. Namely, we prove:

######  Theorem 1.1.

There exist a finitely generated group $G$ and a fixed generating set $S$,
such that $G$ satisfies the law $x^{k}=1$ with probability $1$:

$\Pr_{G,\vec{\mu}}(w=1)=\lim_{n\rightarrow\infty}\Pr_{x\sim\mu_{n}}\left(x^{k}=1\right)=1$

For the following cases:

  1. (1)

$\mu_{n}$ is the uniform distribution on the $n$-th ball of the Cayley graph
of $G$ with respect to $S$; and when

  2. (2)

$\mu_{n}=\mu^{*n}$ is the random walk distribution induced by an arbitrary
finitely supported step measure $\mu$ on $G$ whose support generates $G$ as a
semigroup.

At the same time, $G$ contains a non-abelian free subgroup.

In particular, this answers a question from [2] (see discussion after Question
13.1 therein) and gives the first example of a finitely generated group which
satisfies a group law with probability $1$ but does not satisfy any group law.

The methods we use are inspired by Olshanskii’s work but require further
layers of construction in order to make sure that the probabilistic Burnside-
type property and a free subgroup coexist. We therefore include relevant
preliminaries from [7]; see Section 2. Section 3 includes our construction and
the proofs of its main properties.

### Acknowledgement.

We are gratefully thankful to Denis Osin for inspiring discussions, and in
particular for his advice regarding Lemma 3.6.

##  2\. Diagrams over groups

The definitions and results in this Section are taken from [7].

###  2.1. Letters and words

Let $S=\\{x_{1},\dots,s_{d}\\}$ be a fixed alphabet and let
$S^{-1}=\\{x_{1}^{-1},\dots,x_{d}^{-1}\\}$ be a new alphabet. A _word_ in the
alphabet $S\cup S^{-1}$ is a finite sequence $X=x_{1}x_{2}\dots x_{l}$ with
each $x_{i}\in S\cup S^{-1}$. The number $l$ is called _the length_ of $X$ and
is denoted by $|X|$. The empty word has length $0$ by convention. $X$ is
called _reduced_ if it does not contain any occurrence of $xx^{-1}$ or
$x^{-1}x$ for any $x\in S$. Two (not necessarily reduced) words $X,Y$ that are
the same letter by letter are said to be _visually equal_ , and we denote
$X\equiv Y$. A reduced word $Y$ is called a _subword_ of another reduced word
$X$ if $X\equiv UYZ$ for some words $U,Z$.

Let $F=F(S)$ denote the free group over $S$. If $X\equiv YZ$ then $ZY$ is
called a _cyclic shift_ of $X$. Clearly cyclic shifts of $X$ are conjugate to
$X$ in $F$ and every word is conjugate in $F$ to a _cyclically reduced word_ ,
that is, a reduced word whose first and last letters are not mutual inverses.
Moreover, if $X,X^{\prime}$ are two cyclically reduced words that are
conjugate in $F$ then $X^{\prime}$ is a cyclic shift of $X$. A _cyclic word_
is the set of all cyclic shifts of a word $X$. A _subword_ of a cyclic word is
a subword of one of the cyclic shifts of the ordinary word $X$.

###  2.2. Maps

A cell-decomposition $\Delta$ of a surface $X$ is called a _map_ on $X$. When
$X$ is an orientable surface, we assume that an orientation has been fixed on
$\Delta$. Maps on a disc are called _circular_ and maps on an annulus are
called _annular_. Any side of $\Delta$ with a specified orientation will be
called an _edge_ in $\Delta$, that is, every side gives rise to two edges in
$\Delta$, which are called inverses of each other. Let $e_{-},e_{+}$ denote
respectively the uniquely determined vertices of the edges $e$, so that
$(e^{-1})_{-}=e_{+}$ and $(e^{-1})_{+}=e_{-}$. A path $p$ is called _simple_
if if the vertices $(e_{1})_{-},\dots,(e_{n})_{-},(e_{n})_{+}$ are pairwise
distinct.

By convention, the boundary of a circular map is traversed clockwise, and for
an annular map, the outer is traversed clockwise while the inner is traversed
counter clockwise. Any connected component $Y$ of the boundary consisting of
$n$ unoriented edges $e_{1},e_{2},\dots,e_{n}$ that form a loop is called a
_contour_ of $\Delta$; the contour(s) of $\Delta$ are denoted
$\partial\Delta$; circular maps have one contour and annular maps have two. We
consider contours up to cyclic shifts, namely, we do not specify a unique
starting point.

If $e_{1},\dots,e_{n}$ are edges in $\Delta$ such that
$(e_{i})_{+}=(e_{i+1})_{-}$ for $i=1,\dots,n-1$, then the sequence
$p=e_{1}\dots e_{n}$ is called a _path_ in $\Delta$. We denote the length of
such a path by $|p|=n$. The concept of _subpath_ is fully analogous to that of
a subword.

###  2.3. Diagrams over groups

A map $\Delta$ equipped with an assignment of a letter $\phi(e)\in S\cup
S^{-1}$ for each edge $e$ of $\Delta$ such that
$\phi(e^{-1})\equiv\phi(e)^{-1}$ is called a _diagram over $S$_. The label of
a path $p=e_{1}\dots e_{n}$ is set to be the word
$\phi(p):=\phi(e_{1})\dots\phi(e_{n})$ over $S^{1}$; if $|p|=0$ then
$\phi(p)\equiv 1$ by definition. The label of a contour (of a cell or diagram)
is defined up to a cyclic shift, that is, as a cyclic word.

Let $\mathcal{R}\subset F(S)$ be a set of words. A cell of a diagram $\Delta$
is called an $\mathcal{R}$-cell if the label $\phi(p)$ of its contour is equal
up to a cyclic shift either to some $R\in\mathcal{R}$, or to $R^{-1}$.

A _diagram on a surface $X$ over a presentation $G=\langle
S\mid\mathcal{R}\rangle$_ is any diagram $\Delta$ over the alphabet $S$ whose
cells are all $\mathcal{R}$-cells. We also say that such a $\Delta$ is a
_diagram over $G$_. Ol’shanskii [7] calls a diagram over a presentation
_reduced_ if it does not contain a pattern called ‘$j$-pair’ for any rank $j$,
and shows that any diagram $\Delta$ can be replaced by a reduced diagram with
the same contour label. However, to avoid complications and the need of
defining $j$-cells, we use the following equivalent definition by Osin [9]: A
diagram $\Delta$ over a presentation $G=\langle S\mid\mathcal{R}\rangle$ is
called _reduced_ if it has a minimal number of $\mathcal{R}$-cells among all
diagrams over $G$ having the same boundary label as $\Delta$.

###  2.4. Graded presentations and graded diagrams

Suppose that a set of words $\mathcal{R}$ in a group alphabet $S\cup S^{-1}$
is decomposed into a disjoint union of subsets
$\mathcal{R}=\bigcup_{i=1}^{\infty}\mathcal{R}_{i}$ such that
$\mathcal{R}_{i}$ is disjoint from the set of cyclic conjugates and inverses
of $\mathcal{R}_{j}$ for any $j\neq i$. Then the presentation $G=\langle
S\mid\bigcup_{i=1}^{\infty}\mathcal{R}_{i}\rangle$ is called a _graded
presentation_ , and the members of $\mathcal{R}_{i}$ are called _relators of
rank $i$_. If two words $X,Y$ that are equal in the group $G(i):=\langle
S\mid\bigcup_{j=1}^{i}\mathcal{R}_{i}\rangle$, we say that they are _equal in
rank $i$_ (by convention, $G(0)=F(S)$, so ‘equality of rank $0$’ of words
$X,Y$ amounts to $X\equiv Y$). Conjugacy in rank $i$ is defined in a similar
manner.

Let $\Delta$ be a map on a surface and assume that every cell $\Pi$ of
$\Delta$ has a rank, namely, an integer $r=r(\Pi)\geq 0$, then $\Delta$ is
called a _graded map_. A diagram $\Delta$ is called _graded_ if its underlying
map is graded (i.e., the map obtained by forgetting its labeling). Naturally,
for a diagram $\Delta$ over a graded presentation, $r(\Pi)=i$ if the contour
label of $\Pi$ is visually equal to a defining relator of rank $i$.

The rank of a map (or a diagram) is: $r(\Delta)=\max_{\Pi\in\Delta}r(\Pi)$. If
$r(\Delta)\leq i$ we say that $\Delta$ is a map (diagram) _of rank $i$_. The
following two Van-Kampen type theorems are proven by Ol’shanskii in [7].

######  Lemma 2.1 ([7, Theorem 11.1]).

Let $W$ be a non-empty word over the alphabet $S^{1}$. Then $W=1$ in the group
$G$ given by a graded presentation if and only if there is a reduced circular
diagram over this presentation, whose contour label is visually equal to $W$.

######  Lemma 2.2 ([7, Theorem 11.2]).

Let $V$ and $W$ be two non-empty word over the alphabet $S^{1}$. Then these
words are conjugate in the group $G$ given by a graded presentation if and
only if there is a reduced annular diagram over this presentation, whose
contours $p$ and $q$ satisfy $\phi(p)\equiv V$ and $\phi(q)\equiv W^{-1}$.

In what follows, all maps and diagrams are assumed to be graded, so the
adjective ‘graded’ is often omitted.

###  2.5. contiguity subdiagrams

Let $p$ be a loop on a surface $X$ whose edges form the boundary of a subspace
$Y\subset X$ homeomorphic to a disc. Then the restriction of a cell
decomposition $\Delta$ to $Y$ is a decomposition of $Y$, called a _submap_ of
the map $\Delta$. By definition, a submap is always a circular submap. A
subdiagram of a diagram $\Delta$ is a submap $\Gamma$ of $\Delta$ whose edges
bear the same labels as in $\Gamma$. It can be thought of as a circular
diagram cut out from $\Gamma$.

Let $\Delta$ be a diagram over a presentation $\langle
S\mid\mathcal{R}\rangle$ and let $q$ be a subpath of $\partial\Delta$. Let
$\pi,\Pi$ be $\mathcal{R}$-cells in $\Delta$. Suppose that there is a simple
closed path $p=s_{1}q_{1}s_{2}q_{2}$ in $\Delta$, where $q_{1}$ is a subpath
of $\partial\pi$ and $q_{2}$ a subpath of $q$ (or of $\partial\Pi$), and
$|s_{1}|,|s_{2}|$ are bounded by a small fixed constant. We denote by $\Gamma$
the subdiagram of $\Delta$ inscribed by $p$. If $\Gamma$ contains no cells of
rank $\geq k$ then $\Gamma$ is called a _contiguity subdiagram of rank $k$_ of
$\pi$ to the subpath $q$ of $\partial\Delta$ (or to $\Pi$, respectively).
$q_{1}$ is called the _contiguity arc_ of $\pi$ to $q$ (respectively to
$\Pi$), and the ratio $|q_{1}|/|\partial\pi|$ is called the _contiguity
degree_ of $\pi$ to $q$ (resp. to $\Pi$) and is denoted by $(\pi,\Gamma,q)$
(resp. $(\pi,\Gamma,\Pi)$). We sometimes write $q_{1}=\Gamma\cap\pi$ and
$q_{2}=\Gamma\cap q$ (resp. $q_{2}=\Gamma\cap\Pi)$). For a detailed inductive
construction of contiguity subdiagrams, we refer the reader to [7, Section
14.2].

###  2.6. $A$-maps and existence of $\gamma$-cells

We now describe a certain condition of maps, defined by Olshanskii, Section
15.2 in [7], called _Condition $A$_. Intuitively, this condition should
capture the special features of a map over a presentation in which all rank
$j$ relators are of the form $B^{k}$ for $B$ a simple period of length $j$.
The precise definition of a simple period and precise choice of relators in
our construction, are brought in Section 3.

The definition of an $A$-map (namely, a map that satisfies Condition $A$) and
the facts on $A$-maps here to follow hold for certain small parameters,
$\alpha>\gamma>\epsilon>0$, which are defined in [7], and for sufficiently
large $k$. We denote $\bar{\alpha}=\frac{1}{2}+\alpha,$
$\bar{\gamma}=1-\gamma$, and note that the parameters are chosen such that
$\bar{\alpha}+\epsilon<\bar{\gamma}$. A path $p$ is called _geodesic_ if
$|p|\leq|p^{\prime}|$ for any path $p^{\prime}$ that can be achieved from $p$
by performing finitely many insertions of loops, deletions of loops,
insertions of subpaths of the form $ee^{-1}$, and deletions of subpaths of the
form $ee^{-1}$.

######  Definition 2.3 (Condition A).

A graded map $\Delta$ is called an _$A$ -map_ if:

  1. (1)

The contour $\partial\Pi$ of any cell of rank $j$ is cyclically reduced (that
is, does not contain a subpath of the form $ee^{-1}$) and $|\partial\Pi|\geq
kj$.

  2. (2)

Any subpath of length $\leq\max(j,2)$ of the contour of any cell of rank $j$
is geodesic in $\Delta$.

  3. (3)

If $\pi,\Pi$ are two cells in $\Delta$ and $\Gamma$ is a contiguity submap of
$\pi$ to $\Pi$ with $(\pi,\Gamma,\Pi)\geq\epsilon$, then
$|\Gamma\cap\Pi|<(1+\gamma)\cdot r(\Pi)$.

We will see later on that any map over the presentation we construct in
Section 3 is an $A$-map. Indeed, as any rank $j$ relator in our construction
is of the form $B^{k}$ for a period $B$ of length $j$, $(A1)$ is satisfied;
$(A2)$ is satisfied since the periods of rank $j$ are chosen as the shortest
words among their conjugates in rank $j-1$. Property $(A3)$ generalizes the
following observation: given any word $X$ which is both $B$-periodic and
$C$-periodic with $B\neq C$ and $X$ is ‘much longer’ than $B$ – say,
$|X|>k\epsilon|B|$ – we must have that $|X|>(1+\gamma)|C|$ where $\gamma$ is
‘small’. Viewing the word $X$ as the label of the contiguity arc of $\Gamma$,
we get property $(A3)$.

The concept of a rank of a cell is generalized to sections of $\partial\Delta$
as follows.

######  Definition 2.4.

A (cyclic) section $q$ of a contour of a map $\Delta$ is called a _smooth
section of rank $r>0$_ (we write $r(q)=r)$ if:

  1. (1)

Every subpath of length $\leq\max(r,2)$ of $q$ is geodesic in $\Delta$; and

  2. (2)

For each contiguity submap $\Gamma$ of a cell $\pi$ to $q$ satisfying
$(\pi,\Gamma,q)\geq\epsilon$, we have $|\Gamma\cap q|<(1+\gamma)r$.

Intuitively this means that the section $q$ behaves like a section in the
contour of a cell of rank $r$. To avoid ambiguity, for a given section $q$ we
let its rank be the minimal $r$ for which this definition is satisfied.

######  Lemma 2.5 ([7, Lemma 15.8]).

In an arbitrary $A$-map $\Delta$, the degree of contiguity of an arbitrary
cell $\pi$ to an arbitrary cell $\Pi$ or to an arbitrary smooth section $q$ of
the contour across an arbitrary contiguity submap $\Gamma$ is smaller than
$\bar{\alpha}$.

######  Lemma 2.6 ([7, Lemma 16.1]).

Let $\Delta$ be a circular $A$-map, $r(\Delta)>0$, whose contour is decomposed
into four sections $q^{1},q^{2},q^{3},q^{4}$. Then there is an
$\mathcal{R}$-cell $\pi$ and disjoint contiguity submaps
$\Gamma_{1},\Gamma_{2},\Gamma_{3},\Gamma_{4}$ of $\pi$ to
$q^{1},q^{2},q^{3},q^{4}$, respectively, in $\Delta$ (some of the latter may
be absent) such that:

$\Sigma_{i=1}^{4}(\pi,\Gamma_{i},q^{i})>\bar{\gamma}.$

######  Corollary 2.7 ([7, Corollary 16.2]).

Let $\Delta$ be an annular $A$-map with contours $q^{1}$ and $q^{2}$ (regarded
as cyclic sections) and $r(\Delta)>0$. Then $\Delta$ has an $\mathcal{R}$-cell
$\pi$ and disjoint contiguity submaps $\Gamma_{1}$ and $\Gamma_{2}$ of $\pi$
to $q^{1}$ and $q^{2}$, respectively, (one of these may be absent) such that
$(\pi,\Gamma_{1},q^{1})+(\pi,\Gamma_{2},q^{2})>\bar{\gamma}.$

Any cell $\pi$ as in Theorems 2.6 and 2.7 is called a _$\gamma$ -cell_ in
$\Delta$. Intuitively, these theorems say that almost all of the contour of a
$\gamma$-cell consists of outer arcs.

Finally, we will use the following claim, that is proved by Olshanskii as part
of his proof of Theorem 16.2 in [7].

######  Lemma 2.8.

Let $\Delta$ be an $A$-map of non-zero rank and let $\Gamma$ be a contiguity
submap of an $\mathcal{R}$-cell $\Pi$ to a section $q$ of the contour of
$\Delta$ such that $(\Pi,\Gamma,q)\geq\epsilon$. Suppose that $\Pi$ is chosen
in such a way that the number of cells in $\Gamma$ is minimal, then
$r(\Gamma)=0$

##  3\. The construction

We use Ol’shanskii’s terminology from [7, Chapter 6], adjusted to our needs.
Let $S=\\{c_{1},c_{2},\dots,c_{m},a,b\\}$. Set $G(0)=F(S)$, and
$\mathcal{X}_{0}=\mathcal{R}_{0}=\emptyset$. We now recursively define for any
integer $i\geq 0$ a set $\mathcal{R}_{i}$ of words over $S$ and a group
$G(i)$.

Let $i\geq 0$ and suppose that $\mathcal{R}_{i}$ and $G(i)$ have already been
defined.

A word $X\in\mathcal{X}_{i}$ is called a period of rank $i$. A (nontrivial)
word $W$ in $S$ is called simple in rank $i$ if:

  1. (S1)

$W$ is not conjugate in $G(i)$ to any power $B^{m}$ of a period $B$ of rank
$l\leq i$;

  2. (S2)

$W$ is not conjugate in $G(i)$ to a power of any word $C$ with $|C|<|W|$; and

  3. (S3)

$W$ is not conjugate in $G(i)$ to any word in the subgroup $\langle
a,b\rangle$ of $G(i)$.

Let $\mathcal{X}_{i}$ denote a maximal subset of words simple in rank $i-1$,
of length $i$, and with the property that if $A,B\in\mathcal{X}_{i}$ with
$A\neq B$ then $A$ is not conjugate in rank $i-1$ (that is, in $G(i-1)$) to
$B$ or $B^{-1}$. Set $\mathcal{R}_{i}$ to be $\\{X^{k}\mid
X\in\mathcal{X}_{i}\\}$, and set

$G(i)=\langle S\mid R=1\ :\ R\in\bigcup_{j=0}^{j=i}\mathcal{R}_{i}\rangle.$

Finally, set $\mathcal{R}=\bigcup_{j=0}^{\infty}\mathcal{R}_{j}$ and

$G=\langle S\mid R=1\ :\
R\in\mathcal{R}=\bigcup_{j=0}^{\infty}\mathcal{R}_{j}\rangle$ (3.1)

We comment that in Ol’shanskii’s original construction of a Burnside group [7,
Chapter 6], simple elements are defined slightly differently. In fact, these
are elements that satisfy Items (S1) and (S2) above. This, in turn, yields a
slightly different definition for a period.

The rest of this section is dedicated to proving the properties of $G$.

######  Lemma 3.1.

Let $g\in G$. Then either $g$ is conjugate in $G$ to an element from the
subgroup $\langle a,b\rangle$ or $g^{k}=1$.

###### Proof.

This follows directly from the construction, but we prove it here by induction
on the norm for the convenience of the reader. Indeed, suppose that an element
$g\in G$ is not conjugate to any element in $\langle a,b\rangle$. Let
$i=\|g\|$ be the norm of $g$ and suppose that any element with norm less than
$i$ is either of order dividing $k$ or is conjugate to some element from
$\langle a,b\rangle$. Let $W$ be a word of length $i$ representing $g$ in $G$.
By assumption, $W$ satisfies Item (S3) in the definition of a simple element
of rank $i-1$. If $W^{k}\neq 1$ in $G$, then $W$ also satisfies (S1) and (S2),
since any word $C$ with $|C|<|W|$ is either of order dividing $k$ or is
conjugate to some element from $\langle a,b\rangle$. Therefore $W$ is simple
of rank $i-1$, and so $\mathcal{R}_{i}$ contains $X^{k}$ for some $X$ that is
conjugate to $W^{\pm 1}$. But then $W^{k}=1$ in $G$, a contradiction. ∎

######  Lemma 3.2.

Every reduced diagram of rank $i\geq 1$ over the presentation 3.1 is an
$A$-map.

###### Proof.

Olshanskii’s Lemma 19.4 in [7] states that every reduced diagram of rank $\geq
1$ over the graded presentation brought in Section 18 of [7] is an $A$-map.
Although Lemma 19.4 [7] is formulated for a specific presentation, its proof
uses only the following four properties of the presentation:

  1. (P1)

Every relator of rank $i$ is of the form $A^{k}$ for a period $A$ of rank $i$;

  2. (P2)

A period of rank $i$ is simple in any rank less than $i$;

  3. (P3)

A period of rank $i$ is the shortest word among its conjugates in rank $i-1$;

  4. (P4)

For two periods $A,B$ of ranks $i,j$ respectively, $A$ is not conjugate to
$B^{\pm 1}$ in any rank smaller than $\min(i,j)$, unless $A\equiv B$.

It therefore suffices to show that the presentation 3.1 satisfies $(P1)-(P4)$.
The deduction of the conclusion from these four properties works precisely as
Olshanskii’s proof of Lemma 19.4 in [7]. We now verify properties $(P1)-(P4)$.

Property $(P1)$ follows directly from the definitions of $\mathcal{X}_{i}$,
$\mathcal{R}_{i}$.

For $(P2)$, observe that a simple element of rank $i-1$ is in particular
simple in any rank $j\leq i-1$. $(P2)$ now follows directly from the fact that
$\mathcal{X}_{i}$ contains only elements that are simple in rank $i-1$.

$(P3)$ follows immediately from $(P2)$. Indeed, a period of rank $i$ is simple
in any rank $<i$, so it is not conjugate in $G(i-1)$ to any shorter word by
Item (S2) of the definition of a simple element.

For $(P4)$ assume without loss of generality that $i\leq j$. If $i<j$, then
either $B$ or $B^{\pm 1}$ is conjugate in $G(i)$ to the period $A$, and so $B$
is not simple in rank $j$, contradicting $(P2)$. If $i=j$, then $A\equiv B$ by
definition of the set $\mathcal{X}_{i}$, concluding the proof of $(P4)$. ∎

The following lemma formalizes the fact that relators from $\mathcal{R}$ have
very small coincidence with words from $F(a,b)$.

######  Lemma 3.3.

Let $\Delta$ be a reduced diagram over the presentation 3.1 and $\Pi$ a cell
in $\Delta$. Let $q$ be a section of the contour of $\Delta$ such that the
label $\phi(q)$ is a word from $F(a,b)$. Then any contiguity submap $\Gamma$
of $\Pi$ to $q$ has contiguity degree $(\Pi,\Gamma,q)<\epsilon$.

###### Proof.

Suppose $\Gamma$ is a contiguity submap of $\Pi$ to $q$ with
$(\Pi,\Gamma,q)\geq\epsilon$ and such that the number of cells in $\Gamma$ is
minimal. By Lemma 3.2 $\Gamma$ is an $A$-map and so by Lemma 2.8, we have that
$r(\Gamma)=0$.

Since $(\Pi,\Gamma,q)\geq\epsilon$, the label of $q$ has a subword $T$ equals
in rank $0$, and so, visually equal, to a subword of the label of
$\partial\Pi$. Since the label of $\partial\Pi$ is a relator of rank $>0$, it
is of the form $A^{k}$ for some word $A$ that is a simple word of rank $\geq
0$, and $T$ has length $\geq\epsilon|A^{k}|$. Since $\epsilon k>2$, it follows
that $T$ must contain $A$ as a subword. This is impossible, since by
requirement (3) of the definition of a simple element $A$ must contain a
letter from $S\setminus\\{a,b\\}$, while $T$, as a subword of $\phi(q)$
contains only the letters $\\{a,b\\}$. ∎

For an element $g\in G$ we define its norm $\|g\|$ to be the minimum length
$|U|$ of a word $U\in F(S)$ representing $g$ in $G$. Similarly, for a word
$K\in F(S)$, we denote by $\|K\|$ the norm of the image of $K$ in $G$.
Evidently $\|K\|\leq|K|$.

The next lemma formalizes the fact that the subgroup $\langle a,b\rangle$
forms a convex subset of the Cayley graph $\Gamma(G,S)$. In particular, this
implies that $\langle a,b\rangle$ is a free subgroup, see the following
corollary thereafter.

######  Lemma 3.4.

Let $K$ be a word in $F(a,b)$ and $U$ an arbitrary word in $F(S)$, such that
$U=K$ in $G$ and $|U|\leq|K|$. Then $U\equiv K$.

In particular, for every word $K\in F(a,b)$ we have $\|K\|=|K|$.

###### Proof.

Suppose not. Then there exist $K\in F(a,b)$ and $U\in F(S)$ such that $U=K$ in
$G$, $|U|\leq|K|$, but $U\nequiv K$. Let $K,U$ be such words and such that the
cyclic word $KU^{-1}$ is of minimal possible length.

By Theorem 2.1 there exists a reduced graded circular diagram $\Delta$ over
the graded presentation 3.1 with contour $p$ and label $\phi(p)=KU^{-1}$. The
contour of $\Delta$ decomposes as $p=q^{1}q^{2}q^{3}q^{4}$ where
$\phi(q^{1})=K,\phi(q^{2})=U^{-1},\phi(q^{3})=\phi(q^{4})=\emptyset$. We have
that $q^{1},q^{2}$ are smooth section by minimality of $K,U$, while
$q^{3},q^{4}$ are smooth sections by definition. Since $\Delta$ has only a
finite number of cells, it is a diagram of rank $j$ for some $j\geq 0$

We claim that $r(\Delta)=0$. Indeed, if $r(\Delta)>0$, then by Lemma 3.2,
$\Delta$ is an $A$-map. Let $\Pi$ be an arbitrary cell in $\Delta$. By Lemma
3.3, the contiguity degree of $\Pi$ to $p_{K}$ is less than $\epsilon$. By
Lemma 2.5, the contiguity degree of $\Pi$ to $p_{U}$ is smaller than
$\bar{\alpha}$. Since $\epsilon+\bar{\alpha}<\bar{\gamma}$, we get that $\Pi$
is not a $\gamma$-cell. But Lemma 2.7 ensures that a $\gamma$-cell exists,
deriving a contradiction. We therefore get $r(\Delta)=0$.

$r(\Delta)=0$ implies that $KU^{-1}\equiv 1$ visually, and so $K\equiv U$,
deriving a contradiction again, and completing the proof of the lemma. ∎

######  Corollary 3.5.

The subgroup $\langle a,b\rangle\leq G$ is free non-abelian.

###### Proof.

Let $K$ be a freely reduced word in $F(a,b)$ with positive length, $|K|>0$. By
Lemma 3.4, $\|K\|=|K|>0$, and in particular, $K\neq 1$ in $G$. ∎

We next show that also the union of conjugates of $\langle a,b\rangle$ enjoys
some convexity qualities.

######  Lemma 3.6.

Suppose an element $g\in G$ is conjugate to an element in the subgroup
$\langle a,b\rangle$. Then there exist $K\in F(a,b)$ and $V\in F(S)$ such that
$VKV^{-1}$ represents $g$ in $G$ and such that $\|g\|=|VKV^{-1}|=2|V|+|K|$

###### Proof.

If not, let $g\in G$ be an element of minimal norm, for which the lemma is
false, and let $U$ be a word representing $g$ in $G$, with $|U|=\|g\|$. By
assumption, $g$ is conjugate to an element from $\langle a,b\rangle$. Let $K$
be a shortest word in $F(a,b)$ representing an element that is conjugate to
$g$ in $G$. Note that by minimality of the choice, both $U$ and $K$ are
cyclically reduced, as otherwise, they could be replaced by a shorter
conjugate. We can furthermore assume that $U\notin F(a,b)$, as the case $U\in
F(a,b)$ is taken care of in Lemma 3.4.

By Lemma 2.2 there exists a reduced graded annular diagram $\Delta$ over the
presentation 3.1 with contours $p_{K}$ and $p_{U}$ and labels $\phi(p_{K})=K$,
$\phi(p_{U})=U^{-1}$. Moreover, the paths $p_{U}$ and $p_{K}$ by minimality of
the choice.

We claim that $r(\Delta)=0$. Indeed, suppose that $r(\Delta)>0$ and let $\Pi$
be an arbitrary cell in $\Delta$. By Lemma 3.3, the contiguity degree of $\Pi$
to $p_{K}$ across an arbitrary contiguity submap is less than $\epsilon$. By
Lemma 3.2 $\Delta$ is an $A$-map, and so by Lemma 2.5, the contiguity degree
of $\Pi$ to $p_{U}$ across an arbitrary contiguity submap is less than
$\bar{\alpha}$. Since $\epsilon+\bar{\alpha}<\bar{\gamma}$, $\Pi$ is not a
$\gamma$-cell. But Lemma 2.7 ensures that a $\gamma$-cell exists, deriving a
contradiction.

The rank of $\Delta$ being $0$ means that $\Delta$ is a diagram over the free
group. Using Lemma 2.2 again, $K$ and $U$ are conjugates over the free group.
Since $U\notin F(a,b)$, it cannot be that $K\equiv VUV^{-1}$ for any word
$V\in F(S)$. It follows that $VKV^{-1}\equiv U$ visually, and so
$\|g\|=|U|=|VKV^{-1}|=2|V|+|K|$. We derived a contradiction, concluding the
proof of the lemma. ∎

Let $H$ denote the subgroup $H=\langle a,b\rangle$. For an element $h\in H$,
denote by $\|h\|_{H}$ its norm with respect to the generating set $\\{a^{\pm
1},b^{\pm 1}\\}$. As before, the notation $\|g\|$ for $g\in G$ is used to
denote the norm of $g$ with respect to the generating set $S\cup S^{-1}$.

For $r\in\mathbb{R}_{\geq 0}$ let:

$B_{G}(r)=\\{g\in G\ |\ \|g\|\leq r\\},\ B_{H}(r)=\\{a\in H\ |\ \|a\|_{H}\leq
r\\}$

be the corresponding $r$-balls in $G,H$ respectively and let

$\gamma_{G}(n)=\\#B_{G}(n),\ \gamma_{H}(n)=\\#B_{H}(n)$

denote the corresponding growth functions.

Recall that the free Burnside group $B(m,k)$ has exponential growth for
sufficiently large $m,k$. In particular, its growth exponent (with respect to
the standard set of generators) is at least $\alpha_{m,k}$, where
$\alpha_{m,k}\xrightarrow{m\rightarrow\infty}\infty$ given that $k\gg 1$ (but
fixed). Therefore $G$ grows exponentially; recall that by Fekete’s Lemma,
$\alpha:=\lim_{n\rightarrow\infty}\sqrt[n]{\gamma_{G}(n)}$ exists, and since
$G\twoheadrightarrow B(m,k)$, it is bounded from below by $\alpha_{m,k}$. Let
us pick $m,k$ such that $\alpha_{m,k}$ (and hence $\alpha$) are greater than
$12$. Let $N$ be such that for $r\geq N$,
$(\alpha-1)^{r}\leq\gamma_{G}(r)\leq(\alpha+1)^{r}$. In addition, recall that
$\gamma_{H}(r)\leq C\cdot 3^{r}$ for some $C>0$, the latter bounding the
growth of a free group $H$ on two generators with respect on the standard
generators. Finally, let $H^{G}:=\bigcup_{x\in G}xHx^{-1}$ denote the union of
conjugates of $H$ and let $\langle\langle
H\rangle\rangle:=\bigcap_{\begin{subarray}{c}N\trianglelefteq G\\\ H\leq
N\end{subarray}}N$ denote the normal closure of $H$ in $G$.

We now compute the density of torsion elements in $G$. By Lemma 3.1, this
amounts to computing the density of $H^{G}$.

######  Lemma 3.7.

We have:

$\frac{\\#B_{G}(n)\cap H^{G}}{\\#B_{G}(n)}\xrightarrow{n\rightarrow\infty}0.$

###### Proof.

By Lemma 3.6,

$\\#B_{G}(n)\cap H^{G}=\bigcup_{i=0}^{n}\Big{\\{}xax^{-1}\ |\ a\in B_{H}(i),\
x\in B_{G}\left(\frac{n-i}{2}\right)\Big{\\}}$

so:

$\displaystyle\\#B_{G}(n)\cap H^{G}$ $\displaystyle\leq$
$\displaystyle\sum_{i=0}^{n}\gamma_{H}(i)\gamma_{G}\left(\frac{n-i}{2}\right)$
$\displaystyle=$
$\displaystyle\sum_{i=0}^{n-2N}\gamma_{H}(i)\gamma_{G}\left(\frac{n-i}{2}\right)+\sum_{i=n-2N+1}^{n}\gamma_{H}(i)\gamma_{G}\left(\frac{n-i}{2}\right)$
$\displaystyle\leq$
$\displaystyle\sum_{i=0}^{n-2N}\gamma_{H}(i)\gamma_{G}\left(\frac{n-i}{2}\right)+2N\cdot
C3^{n}\cdot\gamma_{G}(N)$

Now denote $D:=2CN\gamma_{G}(N)$ (this is a constant with respect to $n$) and
notice that for $i\leq n-2N$ we have $\frac{n-i}{2}\geq N$ so
$\gamma_{G}\left(\frac{n-i}{2}\right)\leq(\alpha+1)^{\frac{n-i}{2}}$ so:

$\displaystyle\\#B_{G}(n)\cap H^{G}$ $\displaystyle\leq$
$\displaystyle\sum_{i=0}^{n-2N}C\cdot
3^{i}\cdot(\alpha+1)^{\frac{n-i}{2}}+D\cdot 3^{n}$ $\displaystyle\leq$
$\displaystyle C(n+1)\cdot\left(3\sqrt{\alpha+1}\right)^{n}+D\cdot 3^{n}$
$\displaystyle\leq$ $\displaystyle
C^{\prime}n\left(3\sqrt{\alpha+1}\right)^{n}$

for some new constant $C^{\prime}>0$. Since $\alpha>12$ it follows that
$3\sqrt{\alpha+1}<\alpha-1$ and so:

$\frac{\\#B_{G}(n)\cap
H^{G}}{\\#B_{G}(n)}\leq\frac{C^{\prime}n\cdot\left(3\sqrt{\alpha+1}\right)^{n}}{(\alpha-1)^{n}}\xrightarrow{n\rightarrow\infty}0,$

as claimed. ∎

We conclude by observing that $G$ satisfies the requirements of Theorem 1.1.

###### Proof of Theorem 1.1.

We now show that the group $G$, defined in 3.1 satisfies the requirements of
the theorem. As before, we denote by $H$ the subgroup $H=\langle a,b\rangle$.
By Lemma 3.5, $H\leq G$ is a free non-abelian subgroup.

Let $\mu_{n}$ be the uniform distribution on the $n$-th ball of the Cayley
graph $\Gamma(G,S)$ then:

$\Pr_{\mu_{n}}(x^{k}=1)=\frac{\\#B_{G}(n)\cap
H^{G}}{\\#B_{G}(n)}\xrightarrow{n\rightarrow\infty}0$

by Lemma 3.7.

Now let us consider a random walk according to some finitely supported
distribution $\mu$ on $G$ such that $\text{supp}(\mu)$ is a finite set
generating $G$ as a semigroup; namely, we consider the sequence of measures
$\mu_{n}=\mu^{*n}$. Let $\pi\colon G\twoheadrightarrow G/\langle\langle
H\rangle\rangle\cong B(m,k)$ be the quotient map and let $\pi_{\sharp}\mu$ be
the pushforward measure.

Since by Lemma 3.1 every element in $G$ which does not have order dividing $k$
is conjugate to an element from $H$, we obtain:

$\displaystyle\Pr_{\mu^{*n}}(x^{k}\neq 1)$ $\displaystyle\leq$
$\displaystyle\Pr_{\mu^{*n}}\left(x\in H^{G}\right)$ $\displaystyle\leq$
$\displaystyle\Pr_{\mu^{*n}}\left(x\in\langle\langle H\rangle\rangle\right)$
$\displaystyle=$ $\displaystyle\Pr_{(\pi_{\sharp}\mu)^{*n}}(x=1)$

Now $\Pr_{(\pi_{\sharp}\mu)^{*n}}(x=1)$ is the return probability of the
random walk on $G/\langle\langle H\rangle\rangle\cong B(m,k)$ with step
distribution $\pi_{\sharp}\mu$, whose support is a finite generating set of
$B(m,k)$. Therefore
$\Pr_{(\pi_{\sharp}\mu)^{*n}}(x=1)\xrightarrow{n\rightarrow\infty}0$ and
hence:

$\Pr_{\mu^{*n}}(x^{k}\neq 1)\xrightarrow{n\rightarrow\infty}0,$

as required. ∎

## References

  * [1] S. I. Adian, The Burnside problems and identities in groups, Springer (1979) (In Russian).
  * [2] G. Amir, G. Blachar, M. Gerasimova, G. Kozma, Probabilistic laws on infinite groups, https://doi.org/10.48550/arXiv.2304.09144.
  * [3] W. Burnside, An unsettled question in the theory of discontinuous groups, Quart. J. Pure Appl. Math. 33, 230–238 (1902).
  * [4] S. V. Ivanov, The free Burnside groups of sufficiently large exponents, Internat. J. Algebra Comput. 4, 1–308 (1994).
  * [5] P. S. Novikov, S. I. Adian, On infinite periodic groups I–III, Math. USSR Izv. 32, 212–244; 251–524; 709–731 (1968).
  * [6] A. Yu. Ol’shanskii, On the Novikov-Adian theorem, Math. USSR Sb. , 118 (1982) pp. 203–235 (In Russian)
  * [7] A. Yu. Ol’shanskii, Geometry of defining relations in groups, Translated from the 1989 Russian original by Yu. A. Bakhturin. Mathematics and its Applications (Soviet Series), 70. Kluwer Academic Publishers Group, Dordrecht, 1991. xxvi+505 pp.
  * [8] A. Shalev, Probabilistically nilpotent groups, Proc. Amer. Math. Soc. 146 (4), 1529–1536 (2018).
  * [9] D. Osin. Small cancellations over relatively hyperbolic groups and embedding theorems, Annals of mathematics (2010): 1-39.


# Designing for Fairness in Human-Robot Interactions

Houston Claure  Department of Computer Science
Yale University

##  I Introduction & Motivation

The foundation of successful human collaboration is deeply rooted in the
principles of fairness [10]. As robots are increasingly prevalent in various
parts of society where they are working alongside groups and teams of humans,
their ability to understand and act according to principles of fairness
becomes crucial for their effective integration. This is especially critical
when robots are part of multi-human teams, where they must make continuous
decisions regarding the allocation of resources. These resources can be
material, such as tools [11], or communicative, such as gaze direction
[VazquezTowardsGazeb, 13], and must be distributed fairly among team members
to ensure optimal team performance and healthy group dynamics (see Fig. 1 for
an example). Therefore, our research focuses on understanding how robots can
effectively participate within human groups by making fair decisions while
contributing positively to group dynamics and outcomes.

The growing reliance on intelligent systems emphasizes the importance that
fairness plays in their decision-making processes, especially as Artificial
Intelligence (AI) technologies are increasingly employed for critical
decisions like loan eligibility [2], university admissions [1], and job
interviews [15]. However, it is important to differentiate between the
fairness concerns associated with the algorithms referenced above, where their
decisions are one-time occurrences, and those made by robots, which require
continuous decision-making (e.g., the robot in Fig 1. makes multiple
allocation decisions during the collaborative task) [7, 4]. Furthermore,
unlike the machine learning algorithms that make one-shot decisions, robots
are embodied and operate in dynamic environments. This means that robot’s
actions can lead to harm often not considered in other areas of fairness
research, such as physical harm. Examples include self-driving cars that fail
to recognize darker-skinned individuals [19], caregiving robots that offer
unequal support among patients [20], and factory robots that assign tasks
unevenly across human workers [16]. Despite these challenges, current research
in human-robot interaction (HRI) is largely focused on dyadic interactions
between a single robot and a human [3], overlooking the complex dynamics that
emerge within larger groups [17, 18]. This gap underscores the need for more
research on fairness in robotics, taking into account the continuous and
context-dependent nature of robot decision-making in diverse human-robot
teams.

My work aims to develop computational tools and techniques to help overcome
the limitations in our understanding of how robots can adopt human concepts of
fairness, thereby enhancing their integration as effective team members..
Specifically, my work is focused on three research thrusts: 1) building
platforms to capture large-scale team data, 2) expanding our understanding of
how unfair robot actions shape interpersonal relationships, and 3) developing
algorithms that embed fairness into robot decision-making.

##  II Prior Work

###  II-A Building platforms to capture data from multi-agent groups

I have devised two novel experimental platforms aimed at exploring the
implications of fairness in HRI within the context of group dynamics. These
platforms are key assets for the evolution of HRI research. Similar to how
simulations have fueled advancements in robotics areas like physical
manipulation [14], easy-to-adapt experimental platforms are essential to
facilitate the systematic analysis of social interactions and make strides in
our understanding of the role of fairness in HRI.

Figure 1: Consider a scenario where a robot has to make decisions on how to
distribute resources across two team members. However, one team member is more
skilled than the other. How should a robot take skill level into account when
dividing its resources to maximize both efficiency and also fairness? This
example encapsulates the nuanced responsibility that robots have in human
teams: to enhance productivity while fostering an environment of trust and
equality.

####  II-A1 Co-Tetris for Online Experiments

I developed Co-Tetris as an innovative research tool designed to study
collective problem-solving and decision-making. Unlike traditional Tetris
111https://github.com/hbclaure/Co_Tetris, which is a single player game, Co-
Tetris necessitates cooperation, requiring players to coordinate their actions
in real-time. This collaborative twist on the classic game presents a unique
way to examine how individuals communicate and strategize towards a shared
objective. What makes Co-Tetris a significant contribution is its utility as a
research platform. It is a versatile tool that can simulate various
collaborative scenarios, offering insights into group dynamics and individual
roles within a team. By capturing quantitative data on player performance and
behavior, it provides empirical evidence on how people work together under
different conditions, including variable difficulties and learning curves.
This platform has been instrumental in studies examining fairness and social
behavior providing empirical data to inform theories in these domains [6, 8].
The adaptability of Co-Tetris to various experimental settings makes it a
valuable asset for exploring a wide spectrum of research questions relevant to
fairness in human-robot teams.

####  II-A2 Multiplayer Space Invaders for Laboratory Experiments

The Multiplayer Space Invaders Game [9] was developed as a platform for
analyzing robot decision-making in live, competitive settings. This game
extends a traditional Space Invaders game to a multiplayer game where players
work to eliminate as many enemy spaceships on their side of the screen as
possible. Each player commands an individual spaceship, differentiated by
color. The adversaries in the game are represented as alien spaceships and
organized into two distinct clusters on the display. A third player can
support one of the two players by moving to help eliminate the cluster of
enemies on the left or right side. Part of the novelty behind the game’s
design lies in that it incorporates numerous decision-making moments for the
supportive player, providing a framework to analyze different decision
patterns and investigate how they evolve temporally.

###  II-B Building Theory on How Unfair Robot Actions Shape Human Group
Dynamics

In a series of studies – aimed at exploring the impact of robots on group
dynamics and perceptions of fairness [5, 8, 12] – I investigated how robots’
resource distribution behaviors, a phenomenon I termed “machine allocation
behavior”, affect human interactions. Through the use of a novel tower
construction task [12] and the Co-Tetris platform [8], I analyzed interactions
in groups and found that unfair resource allocation by robots could lead to
tension among team members and affect team performance, highlighting the
importance of fair decisions in human-robot collaboration. A key finding from
our experiments suggests that team members who receive more resources from an
intelligent machine have feelings of empowerment over their teammates.
Expanding on these findings, I sought to predict perceptions of fairness in
dynamic interactions. I used the Multiplayer Space Invaders game to
demonstrate how fairness judgments evolve over the course of an interaction
[5] (see Fig. 2). I found that the timing of unfair actions from a robot
influences how perceptions of fairness evolve over time. Collectively, these
studies underscore the nuanced role of robots in shaping interpersonal
dynamics and fairness perceptions, contributing to a deeper understanding of
human-robot interaction and informing the design of fair and transparent
robotic systems.

###  II-C Designing Algorithms that Consider Fairness

This research thrust aims to answer how we can include concepts key to group
work, such as fairness, into a robot’s decision-making process. Toward this
goal, I explored the problem of a robot distributing resources across team
members with varying skill levels through the lens of the multi-armed bandit
framework. This led to the development of the strict-rate-constrained upper
confidence bound algorithm (UCB) as a viable solution [6]. This novel
algorithm allows a robot to learn about the skill level of each teammate by
observing their performance over time while including a constraint on the
minimum rate each human teammate can be selected to receive a resource
throughout the course of a task. I provided theoretical guarantees on
performance and proved that this algorithm has similar regret bounds to the
original unconstrained UCB. To evaluate our algorithm, I deployed the strict
rate-constrained UCB on the Co-Tetris platform, adjusting the level of
fairness (the number of blocks a lower-skilled player would receive control
over). Our large-scale online study (n = 290 participants) showed that
fairness in resource distribution has a significant effect on users’ trust in
robots.

Figure 2: Co-Tetris: a platform for observing group behavior in the face of
unfair AI decisions. I ran an experiment where one player was presented as an
intelligent system and disproportionately allocated falling Tetris blocks to
one player (left). Multiplayer Space Invaders: a robot and a human participant
competed to eliminate as many enemies on the screen as possible. A third robot
disproportionately supported one player by helping them eliminate enemies for
longer periods of time.

##  III Future Work

Motivated by people’s inherent drive for equity and justice, my research
envisions a future where collaborative robots proactively promote fairness
within teams, enhancing group harmony and success. This vision encompasses
three main objectives: establishing fairness benchmarks in Human-Robot
Interaction (HRI) across diverse domains like education, retail, law
enforcement, and healthcare; developing methods for learning to enable robots
to adapt their actions based on user feedback in real time, thereby aligning
closer with human expectations of fairness; and expanding theoretical
understanding of fairness in HRI, exploring dynamics of explainability and
transparency influenced by cultural and gender factors. Through a multifaceted
approach, including online surveys and lab studies, my work aims to develop
robots that not only recognize but also rectify disparities, ensuring fair
treatment for all team members and fostering effective human-robot
collaboration.

## References

  * Attaran et al. [2018] Mohsen Attaran, John Stark, and Derek Stotler.  Opportunities and challenges for big data analytics in us higher education: A conceptual model for implementation.  _Industry and Higher Education_ , 32(3):169–182, 2018.
  * Bhutta et al. [2022] Neil Bhutta, Aurel Hizmo, and Daniel Ringo.  How much does racial bias affect mortgage lending? evidence from human and algorithmic credit decisions.  2022\.
  * Chen et al. [2018] Min Chen, Stefanos Nikolaidis, Harold Soh, David Hsu, and Siddhartha Srinivasa.  Planning with Trust for Human-Robot Collaboration.  In _ACM/IEEE International Conference on Human-Robot Interaction_ , 2018.  ISBN 9781450349536.  doi: 10.1145/3171221.3171264.
  * Claure and Jung [2021] Houston Claure and Malte Jung.  Fairness considerations for enhanced team collaboration.  In _Companion of the 2021 ACM/IEEE International Conference on Human-Robot Interaction_ , pages 598–600, 2021.
  * [5] Houston Claure, Kate Candon, Olivia Clark, and Marynel Vázquez.  Dynamic fairness perceptions in human-robot interaction.  In _Computer supported cooperative work (CSCW) ’24’ (Submitted)._
  * Claure et al. [2020] Houston Claure, Yifang Chen, Jignesh Modi, Malte Jung, and Stefanos Nikolaidis.  Multi-armed bandits with fairness constraints for distributing resources to human teammates.  In _Proceedings of the 2020 ACM/IEEE International Conference on Human-Robot Interaction_ , pages 299–308, 2020.
  * Claure et al. [2022] Houston Claure, Mai Lee Chang, Seyun Kim, Daniel Omeiza, Martim Brandao, Min Kyung Lee, and Malte Jung.  Fairness and transparency in human-robot interaction.  In _2022 17th ACM/IEEE International Conference on Human-Robot Interaction (HRI)_ , pages 1244–1246. IEEE, 2022.
  * Claure et al. [2023] Houston Claure, Seyun Kim, René F Kizilcec, and Malte Jung.  The social consequences of machine allocation behavior: Fairness, interpersonal perceptions and performance.  _Computers in Human Behavior_ , 146:107628, 2023.
  * Claure et al. [2024] Houston Claure, Kate Candon, Olivia Clark, and Marynel Vázquez.  Multiplayer space invaders: A platform for studying evolving fairness perceptions in human-robot interaction.  In _Companion of the 2024 ACM/IEEE International Conference on Human-Robot Interaction_ , pages 347–350, 2024.
  * Fehr and Schmidt [1999] Ernst Fehr and Klaus M Schmidt.  A theory of fairness, competition, and cooperation.  _The quarterly journal of economics_ , 114(3):817–868, 1999.
  * Gombolay et al. [2015] Matthew C Gombolay, Reymundo A Gutierrez, Shanelle G Clarke, Giancarlo F Sturla, and Julie A Shah.  Decision-making authority, team efficiency and human worker satisfaction in mixed human–robot teams.  _Autonomous Robots_ , 39:293–312, 2015.
  * Jung et al. [2020] Malte F Jung, Dominic DiFranzo, Solace Shen, Brett Stoll, Houston Claure, and Austin Lawrence.  Robot-assisted tower construction—a method to study the impact of a robot’s allocation behavior on interpersonal dynamics and collaboration in groups.  _ACM Transactions on Human-Robot Interaction (THRI)_ , 10(1):1–23, 2020.
  * Mutlu et al. [2009] Bilge Mutlu, Toshiyuki Shiwa, Takayuki Kanda, Hiroshi Ishiguro, and Norihiro Hagita.  Footing in human-robot conversations: how robots might shape participant roles using gaze cues.  In _Proceedings of the 4th ACM/IEEE international conference on Human robot interaction_ , pages 61–68, 2009.
  * Nair et al. [2022] Suraj Nair, Aravind Rajeswaran, Vikash Kumar, Chelsea Finn, and Abhinav Gupta.  R3m: A universal visual representation for robot manipulation.  _arXiv preprint arXiv:2203.12601_ , 2022.
  * Raghavan et al. [2020] Manish Raghavan, Solon Barocas, Jon Kleinberg, and Karen Levy.  Mitigating bias in algorithmic hiring: Evaluating claims and practices.  In _Proceedings of the 2020 conference on fairness, accountability, and transparency_ , pages 469–481, 2020.
  * Ranz et al. [2017] Fabian Ranz, Vera Hummel, and Wilfried Sihn.  Capability-based task allocation in human-robot collaboration.  _Procedia Manufacturing_ , 9:182–189, 2017.
  * Strohkorb Sebo et al. [2018] Sarah Strohkorb Sebo, Margaret Traeger, Malte Jung, and Brian Scassellati.  The ripple effects of vulnerability: The effects of a robot’s vulnerable behavior on trust in human-robot teams.  In _Proceedings of the 2018 ACM/IEEE International Conference on Human-Robot Interaction_ , pages 178–186, 2018.
  * Tennent et al. [2019] Hamish Tennent, Solace Shen, and Malte Jung.  Micbot: A peripheral robotic object to shape conversational dynamics and team performance.  In _2019 14th ACM/IEEE International Conference on Human-Robot Interaction (HRI)_ , pages 133–142. IEEE, 2019.
  * Wilson et al. [2019] Benjamin Wilson, Judy Hoffman, and Jamie Morgenstern.  Predictive inequity in object detection.  _arXiv preprint arXiv:1902.11097_ , 2019.
  * Yew [2021] Gary Chan Kok Yew.  Trust in and ethical design of carebots: the case for ethics of care.  _International Journal of Social Robotics_ , 13(4):629–645, 2021.


Lehrstuhl für Data Science

Time Series Classification using Convolutional Neural Network on Imbalanced
Datasets

Masterarbeit von

Syed Rawshon Jamil

## Abstract

Time Series Classification (TSC) has drawn a lot of attention in literature
because of its broad range of applications for different domains, such as
medical data mining, weather forecasting. Although TSC algorithms are designed
for balanced datasets, most real-life time series datasets are imbalanced. The
Skewed distribution is a problem for time series classification both in
distance-based and feature-based algorithms under the condition of poor class
separability. To address the imbalance problem, both sampling-based and
algorithmic approaches are used in this paper. Different methods significantly
improve time series classification’s performance on imbalanced datasets.
Despite having a high imbalance ratio, the result showed that F score could be
as high as 97.6% for the simulated TwoPatterns Dataset.