# On the Rényi–Ulam Game with Restricted Size Queries

Ádám X. Fraknói  Institute of Mathematics
Eötvös Loránd University
Pázmány Péter sétány 1/C,
H-1117 Budapest
Hungary  Dávid Á. Márton  Bolyai Institute
University of Szeged
Aradi vértanúk tere 1,
H-6720 Szeged
Hungary  Dániel G. Simon  Faculty of Mathematics
University of Cambridge
Wilberforce Road,
Cambridge CB3 0WA
United Kingdom
Dániel A. Lenger  Institute of Mathematics
Eötvös Loránd University
Pázmány Péter sétány 1/C,
H-1117 Budapest
Hungary  MTA-ELTE Lendület Combinatorial Geometry Research Group

###### Abstract

We investigate the following version of the well-known Rényi–Ulam game. Two
players — the Questioner and the Responder — play against each other. The
Responder thinks of a number from the set $\\{1,\ldots,n\\}$ and the
Questioner has to find this number. To do this, he can ask if the sought
number is an element of a subset of $\\{1,\ldots,n\\}$ with at most $k$
elements. The Responder answers with YES or NO immediately, but during the
game he may lie at most $\ell$ times. The minimal number of queries needed for
the Questioner to find the unknown element in the worst case is denoted by
$RU_{\ell}^{k}(n)$. First, we develop a highly effective tool, which we call
Convexity Lemma. Using this, we give a general lower bound of
$RU_{\ell}^{k}(n)$ with an error at most $2\ell+1$, and we also give its exact
value when $n$ is sufficiently large with respect to $k$. With this, we manage
to improve and generalize the results obtained by Meng, Lin and Yang in a 2013
paper about the case $\ell=1$.
Keywords: combinatorial searching, adaptive searching, Rényi–Ulam liar game,
small sets
MSC: 91A46

##  1 Introduction

We investigate a modified version of the following combinatorial searching
problem. Two players — the Questioner and the Responder — play against each
other. The Responder thinks of a number from the set $\\{1,\ldots,n\\}$ and
the Questioner has to find this number. To do this, he can ask if the sought
number is an element of a subset of $\\{1,\ldots,n\\}$, to which the Responder
answers with YES or NO.

The game can be adaptive or non-adaptive. In the non-adaptive version the
Questioner has to ask all of his questions in advance, and the Responder
answers them all together only after that. Whereas in the adaptive game the
Questioner can ask one question at a time, to which the Responder has to
answer immediately.

Regarding the adaptive version it is a well-known result that the Questioner
only needs at most $\lceil\log_{2}n\rceil$ rounds to find the number, and that
in the worst case he actually has to ask that many questions.

Rényi and Ulam came up independently with the version where the Responder may
lie during the game at most $\ell$ times. Let us denote the minimal number of
queries needed for the Questioner in the worst case by $RU_{\ell}(n)$. We have
already mentioned that $RU_{0}(n)=\lceil\log_{2}n\rceil$. Beside that, the
exact value of $RU_{\ell}(n)$ is known for all $n$ when $\ell=1,2,3$.
Furthermore, for all $\ell$ there exist a lower and an upper bound which
differ by at most $\ell$. For more details see [2, 6].

There are many different versions of the above-mentioned Basic Rényi–Ulam
Game. We consider here the one where the Questioner can ask about subsets with
at most $k$ elements, where $k<\left\lfloor\tfrac{n}{2}\right\rfloor$. Note
that if $k\geq\lfloor\frac{n}{2}\rfloor$, the Questioner can use the same
strategies as in the basic game, because in this case he can ask about all of
the subsets using complements.

For this game we denote the minimal number of questions needed in the worst
case by $RU_{\ell}^{k}(n)$. Its exact value is known when $\ell=0$, see Katona
[3]. There it is stated that
$RU_{0}^{k}(n)=\left\lfloor\tfrac{n}{k}\right\rfloor-1+\lceil\log_{2}(k+m_{1})\rceil$
with $m_{1}$ denoting the remainder of $n$ divided by $k$. Katona also gave
bounds for the non-adaptive version, see [4].

We started investigating this problem upon the suggestion of Katona, and now,
using the existing bounds for the Basic Rényi–Ulam Game, we give a generic
lower bound of $RU_{\ell}^{k}(n)$ with an error at most $2\ell+1$.
Furthermore, we give its exact value for all $\ell$ when $n\gg k$.

Meng, Lin and Yang had already published an article in 2013 concerning the
case $\ell=1$, see [5]. They gave a lower bound for $RU_{1}^{k}(n)$ with an
error at most $1$, and determined its exact value when $k^{2}\leq n$. We
generalize their results here for arbitrary $\ell$, and determine the exact
value for smaller values of $n$, too. They also made a conjecture regarding
the Questioner’s optimal strategy. In the last section, we disprove their
conjecture with a counterexample.

We note that investigating this problem could also help in the development of
testing strategies. Indeed, we can imagine our model the following way. We
know that only one person is infected with a virus, and we want to find that
person. We use the so-called pooling strategy, where at most $k$ samples can
be examined together at once. We also know that our tests are not perfect.
However, they are relatively accurate, so we can assume that they make a
mistake at most $\ell$ times during the process.

##  2 Notation and Main Results

Let $RU_{\ell}(n)$ denote the minimal number of queries needed for the
Questioner to find the unknown element in the worst case, assuming that he can
ask an arbitrary subset of $\\{1,\ldots,n\\}$ and that the Responder may lie
at most $\ell$ times. Let $RU_{\ell}^{k}(n)$ denote the minimum number of
queries when the Questioner can only ask subsets with at most $k$ elements.

In this paper, $m_{i}$ denotes the remainder of $n\cdot i$ divided by $k$ for
every $i\geq 1$, and $\log x$ means $\log_{2}x$ for every
$x\in\mathbb{R}^{+}$.

The state of the game can be presented — as it was introduced by Berlekamp [1]
— with the vector $(x_{0},x_{1},\ldots,x_{\ell})$, where after each answer
$x_{i}$ denotes the number of the elements that received NO exactly $i$ times
for all $0\leq i\leq\ell$. To these elements we say that they are in the
$i$-th component of the game. Let $RU_{\ell}^{k}(x_{0},x_{1},\dots,x_{\ell})$
denote the minimum number of queries needed for the Questioner from the
starting state $(x_{0},x_{1},\ldots,x_{\ell})$.

We denote by $x_{\ell+1}$ the number of the elements that received NO at least
$\ell+1$ times. These elements can be excluded from the remaining search
process, because the sought number cannot be one of them. When describing a
state, for clarity, we will sometimes use the notation
$(x_{0},\ldots,x_{\ell}|x_{\ell+1})$. Note that the game ends exactly when
every element except one got a NO (at least) $\ell+1$ times, that is when
$\sum_{i=0}^{\ell}x_{i}=1$.

First, we present the most important tool used throughout the paper, which we
call Convexity Lemma.

######  Lemma 1.

(Convexity Lemma) Let $\ell\geq 1$, $1\leq i\leq j\leq\ell$, such that
$x_{i},x_{j}\geq 1$, and let $1\leq a\leq\min\\{i,\ell-j+1\\}$. Then, except
for the case where $\sum_{i=0}^{\ell}x_{i}=2$ and $a=\ell-j+1$,

$RU_{\ell}^{k}(x_{0},\dots,x_{i},\dots x_{j},\dots,x_{\ell}|x_{\ell+1})\leq
RU_{\ell}^{k}(x_{0},\dots,x_{i-a}+1,\dots,x_{i}-1,\dots,x_{j}-1,\dots,x_{j+a}+1,\dots,x_{\ell}|x_{\ell+1})$.

The above lemma allows us to prove our main results, which are presented in
the following theorem — the main theorem of the article.

######  Theorem 2.

Let $\ell\geq 0$, $k,n\geq 1$, such that
$1<k<\left\lfloor\frac{n}{2}\right\rfloor$, and let

$L_{\ell}^{k}(n)\coloneqq\max_{0\leq
p\leq\ell}\left(\left\lfloor\frac{(p+1)n}{k}\right\rfloor-1+RU_{\ell-p}(k)\right).$

Then it is true that

  1. (i)

$L_{\ell}^{k}(n)\leq RU_{\ell}^{k}(n)\leq L_{\ell}^{k}(n)+\ell+1.$

  2. (ii)

Furthermore if $\ell\geq 1$, $n\geq\max\\{k(\ell+5),k(\log\log
2k+6),k(\log\log 2k+2\log\ell+5)\\}$ then

$RU_{\ell}^{k}(n)=\left\lfloor\frac{(\ell+1)n}{k}\right\rfloor-1+\left\lceil\log(k+m_{\ell+1})\right\rceil.$

Note that the first part of the theorem is merely theoretical, since the exact
value of $RU_{\ell}(k)$ is unknown for $\ell\geq 4$. For an always calculable
bound see Corollary 4. We also note that, clearly,
$RU_{\ell}^{1}(n)=(\ell+1)n-1$ for arbitrary $\ell\geq 0$, $n\geq 1$, and — as
already mentioned —
$RU_{0}^{k}(n)=\left\lfloor\tfrac{n}{k}\right\rfloor-1+\lceil\log(k+m_{1})\rceil$
for all $k,n\geq 1$.

At each $(x_{0},\ldots,x_{\ell})$ state, every query can be presented by a
vector $(q_{0},q_{1},\ldots,q_{\ell})$, where $0\leq q_{i}\leq x_{i}$ is the
number of the elements from the $i$-th component which are being queried. If
the answer is YES to the question then the new state of the game is
$(q_{0},q_{1}+(x_{0}-q_{0}),\ldots,q_{\ell}+(x_{\ell-1}-q_{\ell-1}))$, and if
it is NO then the new state is
$(x_{0}-q_{0},(x_{1}-q_{1})+q_{0},\ldots,(x_{\ell}-q_{\ell})+q_{\ell-1})$.

##  3 Some Useful Lemmas

In this section we introduce previous results and also some new lemmas, which
are required to prove Theorem 2.

It is a commonly used statement that for an arbitrary state
$(x_{0},\ldots,x_{\ell})$ and for any $0\leq i<j\leq\ell+1$, if one element is
shifted from the $i$-th component to the $j$-th one, the arising state can be
solved by as many queries as the previous one. Note that if an element enters
the $(\ell+1)$-th component, then it can be removed from the search process.

The weight is a well-known function of the topic. Given a state
$(x_{0},\ldots,x_{\ell})$, assuming that the Questioner needs $q$ queries to
solve it in the worst case, its weight is
$w_{q}(x_{0},\ldots,x_{\ell})\coloneqq\binom{q}{\leq\ell}x_{0}+\binom{q}{\leq\ell-1}x_{1}+\cdots+\binom{q}{\leq
0}x_{\ell}$, where $\binom{q}{\leq i}\coloneqq\sum_{j=0}^{i}\binom{q}{j}$.

It can be shown that after each question the sum of the weights of the two
possible arising states is equal to the weight of the state preceding the
question. Therefore the Responder can always achieve that after each query the
weight decreases by no more than its half. Clearly, when the Questioner finds
the unknown element, the weight is $1$, since he needs zero query then. From
these follows the lower bound of Lemma 3. The upper bound is due to Rivest et
al. [7], for proofs see [2, 7].

######  Lemma 3.

Let $\ell\geq 0$, $n\geq 1$, and define the _weight bound_ as

$W_{\ell}(n)\coloneqq\min\left\\{q:n\leq\frac{2^{q}}{\binom{q}{0}+\dots+\binom{q}{\ell}}\right\\}.$

Then $W_{\ell}(n)\leq RU_{\ell}(n)\leq W_{\ell}(n)+\ell.$

Note that above defined weight bound is the same as the well-known Hamming
bound in the field of coding theory.

Applying Lemma 3, we get bounds for $L_{\ell}^{k}(n)$, which yield the
following always calculable bounds of $RU_{\ell}^{k}(n)$.

######  Corollary 4.

Let $\ell\geq 0$, $k,n\geq 1$, such that
$1<k<\left\lfloor\frac{n}{2}\right\rfloor$, and

$\hat{L}_{\ell}^{k}(n):=\max_{0\leq
p\leq\ell}\left(\left\lfloor\frac{(p+1)n}{k}\right\rfloor-1+W_{\ell-p}(k)\right).$

Then $\hat{L}_{\ell}^{k}(n)\leq
RU_{\ell}^{k}(n)\leq\hat{L}_{\ell}^{k}(n)+2\ell+1$.

We give bounds for $RU_{\ell}(n)$ based on the weight bound. Similar results
can be found in [7] — without the determination of the constants.

######  Lemma 5.

For every $\ell\geq 1,n\geq 2$ we have that

$\log n+\ell\log\log 2n-\ell\log\ell\leq RU_{\ell}(n)\leq\log n+\ell\log\log
2n+2\ell\log\ell+\ell+2.$

  * Proof.

First, let us consider the upper bound. We estimate the denominators in the
weight bound as

$\binom{q}{0}+\dots+\binom{q}{\ell}\leq 1+q+\dots+q^{\ell}\leq(q+1)^{\ell},$
(1)

and take the following modified version of $W_{\ell}(n)$, where we now take
the minimum for non-negative real values of $q$:

$W^{\prime}_{\ell}(n)\coloneqq\min\left\\{q:n\leq\frac{2^{q}}{(q+1)^{\ell}}\right\\}.$

Note that by (1) we have that $W_{\ell}(n)\leq\lceil
W_{\ell}^{\prime}(n)\rceil\leq W_{\ell}^{\prime}(n)+1$. From this and Lemma 3
it follows that $RU_{\ell}(n)\leq W^{\prime}_{\ell}(n)+\ell+1$. Our goal now
is to give an upper bound for $W^{\prime}_{\ell}(n)$, meaning we want to find
a real number $q$ satisfying $n\leq\tfrac{2^{q}}{(q+1)^{\ell}}$. Let us search
it in the form $q=\log{n}+\log{x}$, where $x>1$. Then it is enough to find an
$x$ with

$n\leq\frac{nx}{(\log{n}+\log{x}+1)^{\ell}},$

or, equivalently, with $(\log{n}+\log{x}+1)^{\ell}\leq x$.

If $x=\left((\ell+1)\log n+\ell^{2}+1\right)^{\ell}$, this condition is
fulfilled. Indeed, after substituting we get

$(\log n+\ell\log((\ell+1)\log n+\ell^{2}+1)+1)^{\ell}\leq((\ell+1)\log
n+\ell^{2}+1)^{\ell},$

which can be simplified to

$\log((\ell+1)\log n+\ell^{2}+1)\leq\log n+\ell$

and then to

$(\ell+1)\log n+\ell^{2}+1\leq 2^{\ell}\cdot n,$

with the last one being clearly true for all $n\geq 2$, $\ell\geq 1$. Thus we
have that

$\displaystyle RU_{\ell}(n)$ $\displaystyle\leq
W^{\prime}_{\ell}(n)+\ell+1\leq\log n+\ell\cdot\log((\ell+1)\log
n+\ell^{2}+1)+\ell+1$ $\displaystyle\leq\log n+\ell\log(\ell^{2}(\log
n+1))+\ell+2$ $\displaystyle=\log n+\ell\log\log 2n+2\ell\log\ell+\ell+2.$

Now, let us consider the lower bound. We claim that the following estimation
holds for the denominators in the weight bound when $\ell\geq 2$:

$\sum_{i=0}^{\ell}\binom{q}{i}\geq
1+\sum_{i=0}^{\ell}\frac{\binom{\ell}{i}q^{i}}{\ell^{\ell}}=1+\frac{(q+1)^{\ell}}{\ell^{\ell}}.$
(2)

Indeed, compare the members of the sums for $i\geq 2$ respectively using

$\binom{q}{i}=\frac{q}{i}\cdot\frac{q-1}{i-1}\cdots\frac{q-i+1}{1}\geq\left(\frac{q}{i}\right)^{i}\geq\frac{q^{i}}{\ell^{i}}=\frac{\ell^{\ell-i}q^{i}}{\ell^{\ell}}\geq\frac{\binom{\ell}{\ell-i}q^{i}}{\ell^{\ell}}=\frac{\binom{\ell}{i}q^{i}}{\ell^{\ell}}.$

Using this, it is sufficient to show that

$\binom{q}{0}+\binom{q}{1}\geq
1+\frac{\binom{\ell}{0}q^{0}}{\ell^{\ell}}+\frac{\binom{\ell}{1}q^{1}}{\ell^{\ell}}$

to prove (2). This is equivalent to $q\ell(\ell^{\ell-1}-1)\geq 1$, which is
obviously true for all $\ell\geq 2$, since $q\geq 1$.

Now, because we are searching for a lower bound for the weight bound, we look
for a real number $q$ satisfying

$n\geq\frac{2^{q}}{\frac{(q+1)^{\ell}}{\ell^{\ell}}+1}.$

Similarly as above, we search it in the form $q=\log{n}+\log{x}$, where $x>1$.
Substituting this, we get the condition $x\leq\frac{(\log n+\log
x+1)^{\ell}}{\ell^{\ell}}+1$. Let $x\coloneqq\left(\frac{\log
2n}{\ell}\right)^{\ell}+1$, then we get

$\frac{(\log n+1)^{\ell}}{\ell^{\ell}}+1\leq\frac{(\log n+\log
x+1)^{\ell}}{\ell^{\ell}}+1,$

which is clearly fulfilled, since $x>1$. From this reasoning it follows that

$RU_{\ell}(n)\geq\log{n}+\log{\left(\frac{\log 2n}{\ell}\right)^{\ell}}=\log
n+\ell\log\log 2n-\ell\log\ell.$

We still need to consider the case $\ell=1$. For $q=\log n+\log\log 2n$ we
have that $n\geq\frac{2^{q}}{q+1}$, which yields that $\log n+\log\log 2n\leq
RU_{1}(n)$, indeed. ∎

######  Lemma 6.

Consider either the Basic or the Modified Rényi–Ulam Game for some $\ell,k\geq
1$ and for any starting state $(x_{0},\ldots,x_{\ell})$ with
$\sum_{i=0}^{\ell}x_{i}\geq 2$. Let the Questioner play a certain strategy
which uses $q$ queries in its worst case. Then if, along this strategy, the
game ends with the state
$(x_{0},\ldots,x_{i-1},x_{i},x_{i+1}\ldots,x_{\ell})=(0,\ldots,0,1,0\ldots,0)$,
we know that the Questioner used at most $q-(\ell-i)$ queries, where $0\leq
i\leq\ell$.

  * Proof.

Let $r$ denote the number of queries used in the case described above. Then
the penultimate state after $r-1$ questions was either
$(0,\dots,0,1,0,\dots,a)$ or $(0,\dots,1,0,0,\dots,a)$ for some $a\geq 1$.

We want to show that from here the Responder can always achieve a play where
the Questioner needs to ask at least $\ell-i+1$ more. We consider the state
$(0,\ldots,0,1,0,\ldots,a)$, since it is clearly worse for the Responder. We
will show that from here the Responder can achieve, after an arbitrary query,
that the next state is one of the followings: $(0,\ldots,0,0,1,\ldots,b)$ or
$(0,\ldots,0,1,0,\ldots,a)$, where $0<b\leq a$.

If the Questioner asks all the elements then the Responder can achieve the
second case with a YES. If the Questioner asks $(0,\ldots,0,1,0,\ldots,a-b)$
or $(0,\ldots,0,0,0,\ldots,b)$ then the Responder can achieve the first case
with a NO or a YES, respectively.

Using the same argument $\ell-i$ times, we conclude that the Responder can
achieve a not easier state than $(0,\ldots,c)$, where $c\geq 2$. From here the
Questioner needs at least one more question.

Now it follows that $(r-1)+(\ell-i+1)\leq q$, meaning the Questioner used at
most $q-(\ell-i)$ queries, indeed. ∎

We present here a statement similar to Lemma 1, which was concerning the
Modified Rényi–Ulam Game, whereas the following lemma deals with the basic
game.

######  Lemma 7.

(Convexity Lemma) Let $\ell\geq 1$, $1\leq i\leq j\leq\ell$, such that
$x_{i},x_{j}\geq 1$, and let $1\leq a\leq\min\\{i,\ell-j+1\\}$. Then, except
for the case where $\sum_{i=0}^{\ell}x_{i}=2$ and $a=\ell-j+1$,

$RU_{\ell}(x_{0},\dots,x_{i},\dots x_{j},\dots,x_{\ell}|x_{\ell+1})\leq
RU_{\ell}(x_{0},\dots,x_{i-a}+1,\dots,x_{i}-1,\dots,x_{j}-1,\dots,x_{j+a}+1,\dots,x_{\ell}|x_{\ell+1})$.

  * Proof.

Let us call the two games starting from the states $(x_{0},\dots,x_{i},\dots
x_{j},\dots,x_{\ell}|x_{\ell+1})$ and
$(x_{0},\dots,x_{i-a}+1,\dots,x_{i}-1,\dots,x_{j}-1,\dots,x_{j+a}+1,\dots,x_{\ell}|x_{\ell+1})$
Game 1 and Game 2, respectively.

Let us think about these games the following way. There are two elements of
$\\{1,\ldots,n\\}$, say $A$ and $B$, that are in the $i$-th and $j$-th
component of the starting state of Game 1, respectively. In the starting state
of Game 2, $A$ is transferred to the $(i-a)$-th and $B$ is transferred to the
$(j+a)$-th component.

We will show that every questioning strategy for Game 2 which uses $q$ queries
in its worst case can be converted into a questioning strategy for Game 1 with
the same property.

Let us play the two games in parallel, such that in Game 1 we are the
Questioner and we have an opponent, called Opponent 1, who is the Responder,
while in Game 2 we are the Responder and our another opponent, called Opponent
2, is the Questioner.

Assume that Opponent 2 plays a questioning strategy that uses $q$ queries in
its worst case. What we want is to convert this into a questioning strategy
for Game 1. We do this using the following method.

First, we wait for the question of Opponent 2. We can assume that Opponent 2
does not ask any element that is in the $(\ell+1)$-th component of Game 2,
otherwise we just ignore it. Then, accordingly, we ask in Game 1 as defined
next.

We ask exactly the same elements as Opponent 2, except for $A$ and $B$. If
Opponent 2 asks both $A$ and $B$ then we do, too, and if he only asks one of
them then we ask the one being in the component with the smaller index — if
both are in the same component, let us ask $B$. Otherwise, we ask none of
them. Note that this method is well-defined, and that we use as many queries
in Game 1 as many is used in Game 2.

Second, we wait for the answer of Opponent 1 to the constructed query, and
then answer the same in Game 2.

Let $s_{1}(A)$, $s_{1}(B)$ denote the indices of the components containing $A$
and $B$ in Game 1, and $s_{2}(A)$, $s_{2}(B)$ in Game 2. Note that these
indices can be even $\ell+1$. At the beginning of the game we have that
$s_{1}(A)=i$, $s_{1}(B)=j$, $s_{2}(A)=i-a$, $s_{2}(B)=j+a$. It follows from
the definition of our method that the equality

$s_{1}(A)+s_{1}(B)=s_{2}(A)+s_{2}(B)$ (3)

and the inequalities

$\min\\{s_{2}(A),s_{2}(B)\\}\leq s_{1}(A)\leq
s_{1}(B)\leq\max\\{s_{2}(A),s_{2}(B)\\}$ (4)

always hold true. We note that for any other element the index of its
component is equal in Game 1 and Game 2.

From (3) and (4), if at least one of $A$ or $B$ is not in the $(\ell+1)$-th
component of Game 2 then at least one of them is not in the $(\ell+1)$-th
component of Game 1. Furthermore, if neither $A$ nor $B$ fall out from the
search — meaning they got less than $\ell+1$ NO — up to a point in Game 2 then
neither one of them did in Game 1.

Opponent 2 wins when $\sum_{i=0}^{\ell}x_{i}=1$ in Game 2, which he surely
achieves after at most $q$ queries. When he wins, one of the following cases
occur.

Case 1: Both $A$ and $B$ are in the $(\ell+1)$-th component of Game 2.
According to (3), then they are in the $(\ell+1)$-th component of Game 1, too.
Thus $\sum_{i=0}^{\ell}x_{i}=1$ in Game 1, meaning we have won there.

Case 2: One of $A$ or $B$ is in the $(\ell+1)$-th, while the other one is in
the $\ell$-th component of Game 2. Using (3), this is clearly true for Game 1,
meaning $\sum_{i=0}^{\ell}x_{i}=1$ there, too.

Case 3: One of $A$ or $B$ is in the $(\ell+1)$-th, while the other one is in
the $i$-th component of Game 2, where $i\leq\ell-1$. According to Lemma 6,
this can happen after at most $q-(\ell-i)$ rounds. Note that we can actually
use Lemma 6, since we excluded the case $\sum_{i=0}^{\ell}x_{i}=2$ and
$a=\ell-j+1$. Now we have that $1\leq\sum_{i=0}^{\ell}x_{i}\leq 2$, meaning we
have not necessarily won in Game 1. However, from (3) and (4), we also know
that either $s_{1}(A)=i$ or $s_{1}(A)>i$, where the former one yields that
$\sum_{i=0}^{\ell}x_{i}=1$. When the latter one occurs, we can surely win in
Game 1 after querying $A$ $\ell-i$ times. Therefore, we only need at most $q$
queries in this case, too.

Assuming that Opponent 2 plays an optimal questioning strategy — which uses
exactly

$RU_{\ell}(x_{0},\dots,x_{i-a}+1,\dots,x_{i}-1,\dots,x_{j}-1,\dots,x_{j+a}+1,\dots,x_{\ell}|x_{\ell+1})$

queries — in Game 2, we get the statement of the lemma. ∎

Lemma 1 — which, clearly, can be proven with exactly the same method — will be
used in our paper numerously. It allows us to prove our main theorem and also
the following additional lemmas.

We call a query _optimal_ for the Questioner at the state
$(x_{0},\ldots,x_{\ell})$ if he can find the sought number from both of the
resulting states using at most $RU_{\ell}^{k}(x_{0},\ldots,x_{\ell})-1$
queries.

######  Lemma 8.

Consider the Modified Rényi–Ulam Game for some $\ell\geq 0$, $k,n\geq 1$.
Suppose that the Questioner knows that the Responder will answer NO to his
next question when he is at the state $(x_{0},\ldots,x_{\ell})$. Then the
query $(q_{0},\ldots,q_{\ell})$ with
$q_{i}\coloneqq\min\left\\{x_{i},k-\sum_{j=0}^{i-1}x_{j}\right\\}$ for all
$0\leq i\leq\ell$ is optimal.

  * Proof.

Let $X\coloneqq\sum_{i=0}^{\ell}x_{i}$, and
$Q\coloneqq\sum_{i=0}^{\ell}q_{i}$. It is easy to see that $Q=\min\\{k,X\\}$.
Take an arbitrary optimal question for the conditions described above, say
$(r_{0},\ldots,r_{\ell})$, and let $R\coloneqq\sum_{i=0}^{\ell}r_{i}$.

We can assume that $R=Q$. Because otherwise, since the Responder will answer
NO, the Questioner asking $Q-R$ many of the elements not being queried
alongside can only result a state that is not harder. Note that when $\ell=0$,
we are done.

For $\ell\geq 1$, clearly, either $r_{0}=q_{0}$ or $r_{0}<q_{0}$. In the
latter case there has to exist an index $1\leq i\leq\ell$ with the property
$r_{i}>q_{i}$, since $R=Q$. Consider the one with the largest index. Then the
question $(r_{0}+1,\ldots,r_{i}-1,\ldots,r_{\ell})$ is optimal for the
investigated case, too. Indeed, its resulting state after the NO answer is

$(x_{0}-r_{0}-1,x_{1}-r_{1}+r_{0}+1,\ldots,x_{i}-r_{i}+r_{i-1}+1,x_{i+1}-r_{i+1}+r_{i}-1,\ldots,x_{\ell}-r_{\ell}+r_{\ell-1}),$

which, according to the Convexity Lemma, is no worse for the Questioner than
the state following $(r_{0},\ldots,r_{\ell})$, that is
$(x_{0}-r_{0},x_{1}+r_{0}-r_{1},\ldots,x_{\ell}-r_{\ell}+r_{\ell-1})$.

Repeating the argument $q_{0}-r_{0}$ times, we reach an optimal query
$(r_{0}^{\prime},\ldots,r_{\ell}^{\prime})$ with $r_{0}^{\prime}=q_{0}$ and
$\sum_{i=0}^{\ell}r_{i}^{\prime}=Q$.

Now, in exactly the same way, compare $r_{1}^{\prime}$ to $q_{1}$, and so on.
See, that it is actually possible to do that. Indeed, let us assume that we
have an arbitrary query $(s_{0},\ldots,s_{\ell})$ satisfying
$\sum_{i=0}^{\ell}s_{i}=Q$ and $s_{i}=q_{i}$ for all $0\leq i\leq j$, where
$0\leq j\leq\ell-1$. Then it follows from the definition of
$(q_{0},\ldots,q_{\ell})$ that $s_{j+1}\leq q_{j+1}$.

The above-described process after $\ell$ steps gives an optimal state
$(\hat{r}_{0},\ldots,\hat{r}_{\ell})$ with $\hat{r}_{i}=q_{i}$ for all $0\leq
i\leq\ell-1$. We also know that $\sum_{i=0}^{\ell}\hat{r}_{i}=Q$, thus
$\hat{r}_{\ell}=q_{\ell}$, yielding that $(q_{0},\ldots,q_{\ell})$ is optimal,
indeed. ∎

The statement of the following lemma is highly intuitive. We present it here
because its proof also shows the utility of Lemma 8.

######  Lemma 9.

For all $\ell\geq 0$, $k,n\geq 1$ it is true that $RU^{k}_{\ell+1}(n)\geq
RU^{k}_{\ell}(n)+\left\lfloor\frac{n}{k}\right\rfloor$. In other words, if one
more lie is available for the Responder then at least
$\left\lfloor\frac{n}{k}\right\rfloor$ more questions are required for the
Questioner.

  * Proof.

Consider the game with $\ell+1$ lie, and assume that the Responder answers NO
for the first $\left\lfloor\frac{n}{k}\right\rfloor$ questions. Then we know
from Lemma 8 that the Questioner arrives at a state that is not better than
$(m_{1},n-m_{1},0,\dots,0)$, since — for him — the optimal question will
always be $(k,0,\ldots,0)$. This is an even harder state than
$(0,n,0,\dots,0)$, which requires $RU_{\ell}^{k}(n)$ questions to solve. ∎

######  Lemma 10.

If the Modified Rényi–Ulam Game — for some $\ell\geq 0$, $k,n\geq 1$ — is at a
state $(x_{0},\ldots,x_{\ell})$ with $x_{0}\geq 2k$ then $(k,0,\ldots,0)$ is
an optimal query for the Questioner, with the NO answer resulting the worse
state.

  * Proof.

Assume that the Questioner asks the query $(q_{0},\ldots,q_{\ell})$. Then the
resulting state after a YES is
$(q_{0},q_{1}+x_{0}-q_{0},\ldots,q_{\ell}+x_{\ell-1}-q_{\ell-1})$. Using the
Convexity Lemma alongside the facts that $\sum_{i=0}^{\ell}q_{i}\leq k$ and
$x_{0}\geq 2k$, it is easy to see that
$(x_{0}-q_{0},x_{1}-q_{1}+q_{0},\ldots,x_{\ell}-q_{\ell}+q_{\ell-1})$ is a
harder state to solve. Indeed,

$\displaystyle
RU_{\ell}^{k}(x_{0}-q_{0},x_{1}-q_{1}+q_{0},\ldots,x_{\ell}-q_{\ell}+q_{\ell-1})\geq$
$\displaystyle
RU_{\ell}^{k}\left(x_{0}-\sum_{i=0}^{\ell}q_{i},x_{1}+\sum_{i=0}^{\ell}q_{i},x_{2},\ldots,x_{\ell}\right)$
$\displaystyle\geq$ $\displaystyle
RU_{\ell}^{k}(q_{0},x_{1}+x_{0}-q_{0},x_{2},\ldots,x_{\ell})$
$\displaystyle\geq$ $\displaystyle
RU_{\ell}^{k}(q_{0},q_{1}+x_{0}-q_{0},\ldots,q_{\ell}+x_{\ell-1}-q_{\ell-1}).$

Therefore it suffices to consider the case where the Responder surely answers
NO. From this, it follows — using Lemma 8 — that $(k,0,\ldots,0)$ is an
optimal question, indeed. ∎

######  Lemma 11.

Let $\ell\geq 0$, $n\geq 2$ and $x,y\leq n$, such that $0<x<y\leq 2x$. Then

$RU_{\ell}(y,n-y,0,\dots,0)-RU_{\ell}(x,n-x,0,\dots,0)\leq 1$

  * Proof.

At the state $(y,n-y,0,\dots,0)$ let the Questioner ask $(y-x,0,\dots,0)$.
Then the NO answer results exactly the state $(x,n-x,0,\dots,0)$, whereas the
YES answer results the state $(y-x,x,n-y,\ldots,0)$, which is even better for
the Questioner, since $y\leq 2x$. ∎

##  4 Proof of the Bounds

In this section, we show that $L_{\ell}^{k}(n)$ is a lower bound of
$RU_{\ell}^{k}(n)$, and then we prove that they differ by at most $\ell+1$.

  * Proof of Theorem 2 (i).

First, let us prove that

$L_{\ell}^{k}(n)\coloneqq\max_{0\leq
p\leq\ell}\left(\left\lfloor\frac{(p+1)n}{k}\right\rfloor-1+RU_{\ell-p}(k)\right)$

is a lower bound. Imagine ourselves in the Questioner’s place, and assume that
we know that the Responder will answer NO for the first
$\left\lfloor\frac{(p+1)n}{k}\right\rfloor-1$ questions. Then, from Lemma 8,
we know that we will get to a state that is no better than
$(0,\dots,k+m_{p+1},n-k-m_{p+1},\dots,0)$. Even from this state we need at
least

$\displaystyle\begin{split}RU_{\ell}^{k}(0,\dots,k+m_{p+1},n-k-
m_{p+1},\dots,0)&\geq RU_{\ell}^{k}(0,\dots,k+m_{p+1},0,\dots,0)\\\ &\geq
RU_{\ell-p}^{k}(k)=RU_{\ell-p}(k)\end{split}$ (5)

queries. It follows that
$\left\lfloor\frac{(p+1)n}{k}\right\rfloor-1+RU_{\ell-p}(k)$ is a lower bound
for every $0\leq p\leq\ell$, indeed.

Second, we prove the upper bound by induction on $\ell$ with fixed values of
$k$ and $n$. To be exact, we will prove that the above-mentioned lower bound
differs from the exact value by at most $\ell+1$.

For the base case $\ell=0$ we need
$RU^{k}_{0}(n)-L_{0}^{k}(n)=\lceil\log{(k+m_{1})}\rceil-\lceil\log{k}\rceil\leq
1$, which clearly holds true. Now, for the induction step, we must prove that
if $RU_{\ell-p}^{k}(n)-L_{\ell-p}^{k}(n)\leq\ell-p+1$ for all $1\leq
p\leq\ell$ then $RU_{\ell}^{k}(n)-L_{\ell}^{k}(n)\leq\ell+1$.

With $\left\lfloor\frac{n}{k}\right\rfloor$ queries we can always reach a
state that is no worse than $(k,n-k,0,\dots,0)$ if we always ask $k$ elements
from the zeroth component. From this state let us ask the $k$ elements of the
zeroth component until one of the following cases occur.

Case 1: The $n-k$ elements from the first component fall out from the
searching, while the $k$ elements from the zeroth arrive at the $p$-th
component, where $0\leq p\leq\ell-1$. This results the state
$(0\dots,0,k,0,\dots,0)$ after altogether
$\left\lfloor\frac{n}{k}\right\rfloor+\ell+p$ questions. From here, we still
need $RU_{\ell-p}(k)$ queries.

Now we define
$a_{\ell,p}\coloneqq(p+1)\left\lfloor\frac{n}{k}\right\rfloor-1+RU_{\ell-p}(k)$
and
$b_{\ell,p}\coloneqq\left\lfloor\frac{n}{k}\right\rfloor+\ell+p+RU_{\ell-p}(k)$,
where $0\leq p\leq\ell-1$. It is clear that $a_{\ell,p}\leq L_{\ell}^{k}(n)$
for all $p$. Furthermore, $\max_{0\leq p\leq\ell-1}b_{\ell,p}$ is an upper
bound for the questions needed altogether in Case 1, because here we can find
the unknown element with that many queries. Let us now compare
$L_{\ell}^{k}(n)$ and $b_{\ell,p}$. Then we see that

$b_{\ell,p}-L_{\ell}^{k}(n)\leq
b_{\ell,p}-a_{\ell,p}=p\cdot\left(1-\left\lfloor\frac{n}{k}\right\rfloor\right)+\ell+1\leq\ell+1,$

since $\left\lfloor\frac{n}{k}\right\rfloor\geq 2$. Therefore $b_{\ell,p}\leq
L_{\ell}^{k}(n)+\ell+1$ for every $p$, thus $L_{\ell}^{k}(n)+\ell+1$ is an
upper bound in this case, indeed.

Case 2: The $k$ elements of the zeroth component merge with the $n-k$ elements
of the first one at the $p$-th component, where $1\leq p\leq\ell$. Note that
in this case $\ell\geq 1$. This results the state $(0\dots,0,n,0,\dots,0)$
after altogether $\left\lfloor\frac{n}{k}\right\rfloor+2p-1$ questions. From
here we still need $RU^{k}_{\ell-p}(n)$ queries.

Now, similarly as above, we define $c_{\ell,p}\coloneqq
p\cdot\left\lfloor\frac{n}{k}\right\rfloor+L_{\ell-p}^{k}(n)$ and
$d_{\ell,p}\coloneqq\left\lfloor\frac{n}{k}\right\rfloor+2p-1+RU_{\ell-p}^{k}(n)$
for all $1\leq p\leq\ell$. It is clear that $\max_{1\leq p\leq\ell}d_{\ell,p}$
is an upper bound for the questions needed altogether in Case 2. We will also
show later that for all $1\leq p\leq\ell$

$c_{\ell,p}\leq L_{\ell}^{k}(n).$ (6)

Using (6) and the induction hypothesis we have that — since
$\left\lfloor\frac{n}{k}\right\rfloor\geq 2$ —

$d_{\ell,p}-L_{\ell}^{k}(n)\leq
d_{\ell,p}-c_{\ell,p}\leq(1-p)\cdot\left(\left\lfloor\frac{n}{k}\right\rfloor-1\right)+\ell+1\leq\ell+1,$

meaning $L_{\ell}^{k}(n)+\ell+1$ questions are enough in this case, too.

The proof is now almost complete, it only remains to verify (6). That is, we
want to show that if $\ell\geq 1$ then
$p\cdot\left\lfloor\frac{n}{k}\right\rfloor+L_{\ell-p}^{k}(n)\leq
L_{\ell}^{k}(n)$ holds for all $1\leq p\leq\ell$. After substitution, we want
to have that

$p\cdot\left\lfloor\frac{n}{k}\right\rfloor+\max_{0\leq
r\leq\ell-p}\left(\left\lfloor\frac{(r+1)n}{k}\right\rfloor-1+RU_{(\ell-p)-r}(k)\right)\leq\max_{0\leq
r\leq\ell}\left(\left\lfloor\frac{(r+1)n}{k}\right\rfloor-1+RU_{\ell-r}(k)\right).$

Comparing the appropriate members of the maximums — for all $0\leq
r\leq\ell-p$ compare the $r$-th term from the left hand side with $(r+p)$-th
one from the right hand side —, we get that

$p\cdot\left\lfloor\frac{n}{k}\right\rfloor+\left\lfloor\frac{(r+1)n}{k}\right\rfloor-1+RU_{(\ell-p)-r}(k)\leq\left\lfloor\frac{(r+p+1)n}{k}\right\rfloor-1+RU_{\ell-(r+p)}(k)$

for all $0\leq r\leq\ell-p$, which yields that (6) is indeed true, concluding
our proof. ∎

######  Remark.

The following statement can be proven with a very similar method. With the
conditions of Theorem 2, let

$\tilde{L}_{\ell}^{k}(n)\coloneqq\max_{0\leq
p\leq\ell}\left(\left\lfloor\frac{(p+1)n}{k}\right\rfloor-1+RU_{\ell-p}(k+m_{p+1},n-k-
m_{p+1},0,\dots,0)\right).$

Then $\tilde{L}_{\ell}^{k}(n)\leq
RU_{\ell}^{k}(n)\leq\tilde{L}_{\ell}^{k}(n)+\ell$.

Note that if we substitute $\ell=1$, we get a lower bound with an error at
most $1$, just as Meng, Lin and Yang [5]. However, $RU_{\ell-p}(k+m_{p+1},n-k-
m_{p+1},0,\dots,0)$ is unknown in the general case, just as $RU_{\ell-p}(k)$ —
furthermore, there is no known useful bound of it.

The proof goes by division into cases, just as the proof described in details
above — the only plus tool needed is Lemma 11. Thus, we omit it from our
paper.

##  5 Proof of the Exact Value

In this section we sketch a strategy for the Questioner, which — assuming that
$n$ is sufficiently large with respect to $k$ — uses as many questions as our
lower bound, hence proves the second part of Theorem 2.

  * Proof of Theorem 2 (ii).

As seen before in (5), $\max_{0\leq
p\leq\ell}\left(\left\lfloor\tfrac{(p+1)n}{k}\right\rfloor-1+RU_{\ell-p}(k+m_{p+1})\right)$
is a lower bound of $RU_{\ell}^{k}(n)$. Therefore
$\left\lfloor\tfrac{(\ell+1)n}{k}\right\rfloor-1+RU_{0}(k+m_{\ell+1})=\left\lfloor\tfrac{(\ell+1)n}{k}\right\rfloor-1+\left\lceil\log(k+m_{\ell+1})\right\rceil$
is a lower bound, too.

Imagine ourselves in the Questioner’s place, and let us play the following
questioning strategy. We ask $k$ elements from the components with the
smallest possible indices until we receive a YES. That is, we ask $k$ elements
from the first non-zero component if that is possible, otherwise we ask all of
the elements there and the remaining ones from the next component.

It is clear that if we always receive a NO until the
$\left(\left\lfloor\tfrac{(\ell+1)n}{k}\right\rfloor-1\right)$-th question,
the state of the game is $(0,\ldots,0,k+m_{\ell+1})$. Here we switch to an
optimal strategy for the case $\ell=0$. Thus we will use at most
$RU_{0}^{k}(k+m_{\ell+1})=RU_{0}(k+m_{\ell+1})=\left\lceil\log(k+m_{\ell+1})\right\rceil$
questions. Therefore
$\left\lfloor\tfrac{(\ell+1)n}{k}\right\rfloor-1+\left\lceil\log(k+m_{\ell+1})\right\rceil$
queries are indeed enough in this case.

Moreover, if we get a YES earlier, but when the first non-zero component is
the $\ell$-th one, we arrive at the state $(0,\ldots,0,k)$. This is solvable
with at most $\lceil\log k\rceil$ questions, meaning we need less than
$\left\lfloor\frac{(\ell+1)n}{k}\right\rfloor-1+\left\lceil\log(k+m_{\ell+1})\right\rceil$
questions in this case.

There are two ways of getting a YES even more earlier — up to the
$\left\lceil\tfrac{\ell\cdot n}{k}\right\rceil$-th question. Let $0\leq
s\leq\ell-1$ denote the index of the first non-zero component before the
question receiving the first YES.

Case A: There are at least $k$ elements in the $s$-th component. Then $k$
elements remain in the $s$-th component, and all the elements of the
$(s+1)$-th go to the $(s+2)$-th. All the other elements go to the $(s+1)$-th
component. So we arrive at the state

$(x_{0},\ldots,x_{s-1},x_{s},x_{s+1},x_{s+2},x_{s+3},\ldots,x_{\ell})=(0,\ldots,0,k,x,n-k-x,0,\ldots,0),$

where $m_{s+1}\leq x\leq n-k$ and $x\equiv m_{s+1}$ modulo $k$. From here, we
ask about the $x$ elements in the $(s+1)$-th component, querying only $k$ at a
time when possible and $m_{s+1}$ for the last time. It is actually enough to
consider only this strategy, since for these plus questions the NO answer
always results the worse state for us. Indeed, using the Convexity Lemma, we
see that if $k\leq x\leq n-k$, the state

$(x_{0},\ldots,x_{s-1},x_{s},x_{s+1},x_{s+2},x_{s+3},x_{s+4},\ldots,x_{\ell})=(0,\ldots,0,0,2k,x-k,n-k-x,0,\ldots,0)$

is easier than $(0,\ldots,0,k,x-k,n-x,0,0,\ldots,0)$. Similarly, if
$x=m_{s+1}$ then $(0,\ldots,0,0,k+m_{s+1},0,n-k-m_{s+1},0,\ldots,0)$ is a
better state for us than $(0,\ldots,0,k,0,n-k,0,0,\ldots,0)$. So we can
conclude that in this case — using altogether
$\left\lceil\tfrac{(s+1)n}{k}\right\rceil$ queries — we arrive at a state that
is no worse than $(0,\ldots,0,k,0,n-k,0,0,\ldots,0)$.

Case B: There are less than $k$ — thus $m_{s+1}$ — elements in the $s$-th
component, meaning we get the first YES for the
$\left\lceil\tfrac{(s+1)n}{k}\right\rceil$-th question. Note that in this case
$m_{s+1}>0$. The resulting state is
$(0,\ldots,0,m_{s+1},k-m_{s+1},n-k,0,\ldots,0)$, which is better than
$(0,\ldots,0,k,0,n-k,0,\ldots,0)$.

In summary, if we get the first YES after a query that is preceded by a state
in which the first non-zero component is the $s$-th one, we need at most
$\left\lceil\tfrac{(s+1)n}{k}\right\rceil+RU_{\ell}^{k}(0,\ldots,0,k,0,n-k,0\ldots,0)$
questions, where $0\leq s\leq\ell-1$.

Now consider the state $(0,\ldots,0,k,0,n-k,0\ldots,0)$. Here we always ask
the $k$ elements from the $s$-th component. After each answer either the $k$
or the $n-k$ elements move to the next component. We do this until one of the
followings occur.

Case 1: The elements from the $s$-th component merge with the elements from
the $(s+2)$-th in the $p$-th component, where $s+2\leq p\leq\ell$. This can
happen after $2p-2s-2$ queries. The resulting state is solvable with at most
$RU_{\ell-p}^{k}(n)$ questions, which — according to the first part of the
theorem — is no more than $\max_{0\leq
q\leq\ell-p}\left(\left\lfloor\frac{(q+1)n}{k}\right\rfloor-1+RU_{\ell-
p-q}(k)\right)+\ell-p+1$.

Case 2: The elements from the $(s+2)$-th component fall out from the
searching, and the elements from the $s$-th arrive at the $p$-th component,
where $s\leq p\leq\ell-1$. This can happen after $\ell+p-2s-1$ queries. The
resulting state is solvable with at most $RU_{\ell-p}(k)$ questions.

In the first case, using Lemma 5, we can bound the queries needed altogether
in the following way:

$\displaystyle\begin{split}&\left\lceil\frac{(s+1)n}{k}\right\rceil+2p-2s-2+\max_{0\leq
q\leq\ell-p}\Bigg{(}\left\lfloor\frac{(q+1)n}{k}\right\rfloor-1+\log k+(\ell-
p-q)\log\log 2k\\\ &\quad+2(\ell-p-q+1)\log(\ell-p-q+1)+(\ell-
p-q)+2\Bigg{)}+\ell-p+1\end{split}$ $\displaystyle\begin{split}\leq\text{
}&\frac{(s+1)n}{k}+2\ell-2s+1+\log k+(\ell-p)\log\log 2k\\\ &\quad+\max_{0\leq
q\leq\ell-p}\Bigg{(}\frac{(q+1)n}{k}-q\log\log 2k+2(\ell-p-q+1)\log(\ell-
p-q+1)-q\Bigg{)}.\end{split}$

Let us think of $q$ as a real number and of the expression in the latter
maximum as its continuous function on $[0,\ell-p]$. Consider the derivative of
this function. It is $\tfrac{n}{k}-\log\log 2k-2\log(\ell-p-q+1)-\tfrac{2}{\ln
2}-1$, so at least $\tfrac{n}{k}-\log\log 2k-2\log\ell-4$, which is non-
negative if $n\geq k(\log\log 2k+2\log\ell+4)$. So when $n$ satisfies this
condition, our upper bound is maximal if $q=\ell-p$. Substituting this, we get
the upper bound

$\frac{(s+1)n}{k}+\frac{(\ell-p+1)n}{k}+\log k+\ell+p-2s+1.$

It is clear — since $\tfrac{n}{k}\geq 1$ — that with respect to $p$ this
expression is monotonically decreasing, therefore it is maximal when $p=s+2$.
Substituting this, we get $\tfrac{\ell\cdot n}{k}+\log k+\ell-s+3$, which is
clearly maximal when $s=0$.

Therefore we use at most $\tfrac{\ell\cdot n}{k}+\log k+\ell+3$ queries in the
first case. Compare this to $\tfrac{(\ell+1)n}{k}-2+\log k$, which is a lower
bound of
$\left\lfloor\tfrac{(\ell+1)n}{k}\right\rfloor-1+\left\lceil\log(k+m_{\ell+1})\right\rceil$.
We can see that if $n\geq k(\ell+5)$ then $\tfrac{\ell\cdot n}{k}+\log
k+\ell+3\leq\tfrac{(\ell+1)n}{k}-2+\log k$. Thus in this case
$\left\lfloor\tfrac{(\ell+1)n}{k}\right\rfloor-1+\left\lceil\log(k+m_{\ell+1})\right\rceil$
questions are indeed enough.

Very similarly, in the second case we can estimate the number of queries,
using Lemma 5, in the following way:

$\displaystyle\left\lceil\frac{(s+1)n}{k}\right\rceil+\ell+p-2s-1+\log
k+(\ell-p)\log\log 2k+2(\ell-p)\log(\ell-p)+(\ell-p)+2$
$\displaystyle\leq\text{ }$ $\displaystyle\frac{(s+1)n}{k}+\log
k+2\ell-2s+2+(\ell-p)\log\log 2k+2(\ell-p)\log(\ell-p).$

It is clear that the latter one is monotonically decreasing with respect to
$p$, so we substitute $p=s$ and get

$\frac{(s+1)n}{k}+\log k+2\ell-2s+2+(\ell-s)\log\log
2k+2(\ell-s)\log(\ell-s).$ (7)

Now consider this as a continuous function of $s$ on $[0,\ell-1]$. Its
derivative is then

$\frac{n}{k}-2-\log\log 2k-2\log(\ell-s)-\frac{2}{\ln
2}\geq\frac{n}{k}-\log\log 2k-2\log\ell-5.$

The latter one — so the derivative, too — is non-negative if $n\geq k(\log\log
2k+2\log\ell+5)$. Therefore when $n$ satisfies this condition, (7) is
monotonically increasing with respect to $s$, so it is maximal if $s=\ell-1$.
Using this, it is now enough to have that $\tfrac{\ell\cdot n}{k}+\log
k+\log\log 2k+4\leq\frac{(\ell+1)n}{k}-2+\log k$, which is true if $n\geq
k(\log\log 2k+6)$. Thus
$\left\lfloor\frac{(\ell+1)n}{k}\right\rfloor-1+\left\lceil\log(k+m_{\ell+1})\right\rceil$
questions are enough in the second case, too.

In summary, we saw that if $n\geq\max\\{k(\ell+5),k(\log\log 2k+6),k(\log\log
2k+2\log\ell+5)\\}$, the Questioner can find the sought number using at most
$\left\lfloor\frac{(\ell+1)n}{k}\right\rfloor-1+\left\lceil\log(k+m_{\ell+1})\right\rceil$
queries, which is also a lower bound of $RU_{\ell}^{k}(n)$, concluding our
proof. ∎

######  Remark.

Look at $\left\lfloor\frac{\ell\cdot n}{k}\right\rfloor-1+RU_{1}(k)$, which —
according to Theorem 2 — is a lower bound of $RU_{\ell}^{k}(n)$. Using Lemma
5, if $n<k(\log\log 2k-3)$,

$\displaystyle\left\lfloor\frac{\ell\cdot n}{k}\right\rfloor-1+RU_{1}(k)$
$\displaystyle>\frac{\ell\cdot n}{k}-2+\log k+\log\log 2k$
$\displaystyle>\frac{(\ell+1)n}{k}+1+\log
k\geq\left\lfloor\frac{(\ell+1)n}{k}\right\rfloor-1+\left\lceil\log(k+m_{\ell+1})\right\rceil.$

So in the second part of Theorem 2, the magnitude of the condition on $n$
cannot be improved. Indeed, if $n<k(\log\log 2k-3)$ then, as seen above,
$RU_{\ell}^{k}(n)>\left\lfloor\frac{(\ell+1)n}{k}\right\rfloor-1+\left\lceil\log(k+m_{\ell+1})\right\rceil$.
This also means that for the herein described strategy — for relatively small
values of $n$ — an earlier YES leads to more questions — unlike for larger
values of $n$. Moreover, our strategy is not optimal in general, as we will
see in the next section.

##  6 Remarks on the Questioner’s Optimal Strategy

As a consequence of Lemma 10, the strategy described in the last section is
optimal up to the $\left(\left\lfloor\frac{n}{k}\right\rfloor-1\right)$-th
question. After that, it is not clear what should the Questioner do when $n$
is relatively small. It seems almost impossible to give an optimal question
for an arbitrary state — even in the case $\ell=1$. Meng, Lin and Yang
conjectured the following in [5] about the optimal query.

######  Conjecture.

Let $k\geq 1$, $a,b\geq 0$, such that $2k>a$, $a+b\geq 2$, and
$ch(a,b)\coloneqq\min\big{\\{}q:(q+1)a+b\leq 2^{q}\big{\\}}$. Using the
notations

$\displaystyle C$
$\displaystyle\coloneqq\max\big{\\{}ch(a,b),RU_{0}^{k}(2a+b)\big{\\}},$
$\displaystyle\chi_{0}$
$\displaystyle\coloneqq\max\big{\\{}x:RU_{1}^{k}(x,a-x)\leq C-1,x\leq a,x\leq
k\big{\\}},$ $\displaystyle\chi_{1}$
$\displaystyle\coloneqq\max\big{\\{}y:RU_{1}^{k}(\chi_{0},y+a-\chi_{0})\leq
C-1,y\leq b,y\leq k-\chi_{0}\big{\\}},$

it is true that
$RU_{1}^{k}(a,b)=\max\big{\\{}C,1+RU_{1}^{k}(a-\chi_{0},b-\chi_{1}+\chi_{0})\big{\\}}$.

We have found a counterexample using a program that calculates all the optimal
questioning strategies for small values of $k$ and $n$. It showed that with
$k=16$ and $n=56$ the Questioner reaches the state $(10,44)$ after three
optimal queries. This state is solvable within seven questions, and for
$a=10$, $b=44$ we have that $C=7$. Therefore the question
$(\chi_{0},\chi_{1})$ has to be optimal, where we know that
$(\chi_{0},\chi_{1})=(8,6)$. However, the optimal query for this state is only
$(7,9)$. This example also shows that our strategy is not optimal for small
values of $n$.

## Acknowledgements

We would like to thank here Gyula Katona for proposing the problem. We are
also tremendously grateful to Dömötör Pálvölgyi for helping us as a
supervisor, and for organizing the REU 2020 program, which provided us the
opportunity to research.

## References

  * [1] E.R. Berlekamp, Block coding for the binary symmetric channel with noiseless, delayless feedback, in: Error Correcting Codes, Wiley, New York, 1968, 61–85.
  * [2] D. Du & F.K. Hwang, Combinatorial Group Testing and Its Applications, World Scientific, Singapore, 2000.
https://doi.org/10.1142/4252

  * [3] G. Katona, Combinatorial search problems, in: Survey of Combinatorial Theory, North-Holland Publishing Company, Amsterdam, 1973, 285--308.
https://doi.org/10.1016/C2013-0-11898-3

  * [4] G. Katona, On separating systems of a finite set, Journal of Combinatorial Theory 1:2, 1966, 174--194.
https://doi.org/10.1016/S0021-9800(66)80024-8

  * [5] K. Meng, C. Lin & Y. Yang, Minimum number of queries for an adaptive liar search game with small sets, Discrete Optimization 10:4, 2013, 233--240.
https://doi.org/10.1016/j.disopt.2013.07.002

  * [6] A. Pelc, Searching games with errors—fifty years of coping with liars, Theoretical Computer Science 270:1–2, 2002, 71--109.
https://doi.org/10.1016/S0304-3975(01)00303-6

  * [7] R.L. Rivest, A.R. Meyer, D.J. Kleitman, K. Winklmann & J. Spencer, Coping with errors in binary search procedures, Journal of Computer and System Sciences 20:3, 1980, 396--404.
https://doi.org/10.1016/0022-0000(80)90014-8


070001 2015 C. S. O’Hern M. Pica Ciamarra, Nanyang Technological University,
Singapore. 070001

We implement the Wang–Landau algorithm to sample with equal probabilities the
static configurations of a model granular system. The “non-interacting rigid
arch model” used is based on the description of static configurations by means
of splitting the assembly of grains into sets of stable arches. This technique
allows us to build the entropy as a function of the volume of the packing for
large systems. We make a special note of the details that have to be
considered when defining the microstates and proposing the moves for the
correct sampling in these unusual models. We compare our results with previous
exact calculations of the model made at moderate system sizes. The technique
opens a new opportunity to calculate the entropy of more complex granular
models.

# Wang–Landau algorithm for entropic sampling of arch-based microstates in the
volume ensemble of static granular packings

D. Slobinsky  [inst1, inst2] Luis A. Pugnaloni[inst1, inst2] E-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS>
(19 January 2015; 25 February 2015)

††volume: 7

99 inst1 Departamento de Ingeniería Mecánica, Facultad Regional La Plata,
Universidad Tecnológica Nacional, Av. 60 Esq. 124, 1900 La Plata, Argentina.
inst2 Consejo Nacional de Investigaciones Científicas y Técnicas (CONICET),
Argentina.

##  1 Introduction

In the study of static packings there exists still a lack of predictive
capabilities of the available theories. Assemblies of objects that pack (such
as grains) can generally sample such packed configurations only by the
external excitation of the system. These packings can be built by repeating a
given packing protocol (e.g., homogeneous compression or deposition under an
external field against a confining boundary) on an initial random
configuration. Also, a Markovian or non-Markovian series can be constructed by
exciting the system from the previous packing configuration. To what extent
the series of packings obtained (using either type of protocol) can be modeled
without information on the dynamics that drives the system to the packed
configuration is still uncertain. The main reason for this is that the few
statistical approaches that attempt to do this are strongly hinder by the poor
current ability to generate such packed structures without using a dynamics to
build the packings.

One might expect that the packing fraction and its fluctuations, among other
properties, could be obtained from basic statistics without resourcing to a
full molecular dynamic type of simulations (also known as “discrete element
method”, DEM). Although these types of simulations are powerful enough to
predict the behaviour of most systems that pack, it is desirable to find a
description that could neglect the detailed dynamics between consecutive
packed configurations.

The use of the tools provided by the ensemble theory of statistical mechanics
in problems of granular matter is still limited. Although many studies perform
statistical analysis of configurations of a granular sample obtained during
careful preparations in the laboratory or in molecular dynamic-type
simulations, very rarely sampling in a particular statistical ensemble is
carried out either via an analytic or a computational calculation of a model
system. This has prevented a direct assessment as to whether ensemble theory
is appropriate to describe the behaviour of these peculiar systems.

One pioneering contribution to the topic is the idea that granular systems at
mechanical equilibrium could be treated as ensemble members, putting forward
the conjecture that the mean values of measurable quantities could be
calculated using statistical mechanics for these ensembles [1]. In this
scheme, each of the thermodynamic variables finds a counterpart, the volume
taking the place of the energy, and the compactivity that of the temperature,
amongst other transformations. However beautiful this description may seem,
the computational challenges to generate ensemble samples in this context are
extraordinaries [2, 3, 4, 5].

One complication that prevents to a large extent the use of the machinery of
statistical mechanics in this case is the fact that configurations, unlike in
traditional liquid theories, have to be checked for the constraint of
mechanical equilibrium. In a previous work [6], we have made a proposal on how
to deal with this, at least in a first approximation, by describing the
excitations of static granular systems under gravity in terms of its arches.
Since arches are sets of grains that stabilize each other, these are the basic
units of mechanically stable structures in the packing. Any static
configuration can be described in terms of the arches formed by its grains,
their arch shape, position, orientations, etc. We have considered, as an
example, a model of a two-dimensional (2D) granular system composed of disks
where arches are assumed to take a single possible structure and the arch–arch
interactions (due to the interlocking of arches) is neglected. We calculated
the exact entropy of this model (the non-interacting rigid arch model, NIRA)
by constructing all possible configurations for moderate system sizes. Of
course, generating each state is a cumbersome task if the system size is
increased or if the number of degrees of freedoms (DoF) is increased by using
more realistic models. Therefore, an alternative approach based on sampling
the phase space with the desired probability is necessary.

In the present work, we will calculate the entropy of the NIRA model in the
microcanonical ensemble [7] using entropic sampling through the Wang–Landau
(WL) algorithm [8, 9, 10, 11]. This approach allows us to obtain the entire
entropy function for all possible volumes of the system in one single
simulation for larger systems and potentially for more complex models. All
derived properties, such as compactivity and volume fluctuations, can then be
calculated through numerical differentiation. We pay particular attention to
the different descriptions that can be realized for the NIRA model. Some of
these representations do not provide a direct way of sampling the
configuration space uniformly.

This work is organized as follows: in section 2, we will review the WL
algorithm. In section 3, we will review the NIRA model and discuss different
ways of representing it, along with the issues related to uniform sampling of
the configurations. We then present a representation that allows very fast
calculations of the entropy and we compare the results with the exact counting
of all configurations for systems of moderate size. Finally, we discuss future
directions to refine the arch-based ensemble volume function towards capturing
detailed features of more realistic systems.

##  2 Wang-Landau algorithm

The WL method has revolutionized computational statistical mechanics [8, 9,
10, 11]. WL is a pure statistical method that can retrieve the density of
states (DoS) (hence the entropy) over a bounded region of the energy spectrum
from the sole knowledge of the energy function. The spectacular computational
performance achieved by this method stems from the fact that it presents no
limitations for the system to tunnel between potential barriers, in stark
contrast with classical Monte Carlo methods that underperform when they
encounter deep valleys in the energy landscape.

WL finds the entropy of the system by means of a Markov chain in the energy
landscape which is conveniently biased towards the less probable energies in a
strongly history dependent manner. This is achieved by using the
multicanonical approach [12] in which each possible configuration is sampled
with a probability given by the inverse of the density of states for its given
energy. Specifically, WL aims to obtain a flat histogram of visited energies
$E$ by forcing the system to go through all configurations with a probability
which is inverse to the previous occurrence of that energy in the Markov
chain. The method is ergodic and asymptotically fulfils the detailed balance
condition [13]. There exists extensive literature on the WL algorithm but
here, we only summarize its most relevant steps. In the following sections, we
will refer to a _configuration_ of the system as a fixed set of values of all
its DoF.

In WL, one defines two histograms that are continuously updated as the Markov
chain proceeds. These histograms are the entropy $S(E)$, which is the output
of the algorithm, and a control histogram $H(E)$. After initializing $H(E)=0$,
$S(E)=1$ and a starting configuration with energy $E_{0}$, the rules to update
these histograms are:

  1. I

Propose a new configuration and calculate its energy $E_{1}$. The new
configuration is generally derived from the previous configuration by a change
in the value of one of its DoF.

  2. II

Accept the new configuration according to a probability given by:
$\min\left[1,\exp(S(E_{0})-S(E_{1}))\right]$.

  3. III

Update the two histograms in the correct energy bin $E$ ($E_{1}$ if the new
configuration is accepted and $E_{0}$ if otherwise), accordingly:
$H(E)=H(E)+1$ for the control histogram, and $S(E)=S(E)+f$ for the entropy.
Here, $f$ is a correction that controls the precision of the algorithm, which
will be decreased (see next step), usually starting at $f=1$.

  4. IV

If the control histogram $H(E)$ is flat enough according to some arbitrary
criterion, decrease $f$ (for instance by making $f=f/2$) and reset all entries
of $H(E)$ to zero.

  5. V

If $f>\epsilon$ (with $\epsilon$ a prescribed tolerance), return to step I,
otherwise stop.

After each reduction of the correction term $f$, the entropy histogram is
built with a finer grained precision. However, to speed up the initial
estimates of $S(E)$, $f$ is set to a high initial value. Different approaches
are followed to accelerate the final stages of refinement by decreasing $f$
with alternative criteria [14].

In Monte Carlo approaches, the detailed balance condition ensures that the
Markov chain has a limiting distribution [15]. Detailed balance can be stated
as follows:

$p_{\mu}P(\mu\rightarrow\nu)=p_{\nu}P(\nu\rightarrow\mu)$ (1)

where $p_{\mu}$ is the probability distribution of configuration $\mu$ and
$P(\mu\rightarrow\nu)$ the transition probability from configuration $\mu$ to
configuration $\nu$ which can be written as:

$P(\mu\rightarrow\nu)=S_{P}(\mu\rightarrow\nu)A_{P}(\mu\rightarrow\nu)$ (2)

with $S_{P}(\mu\rightarrow\nu)$ the selection probability, which is the
probability that the algorithm generates a trial configuration $\nu$ starting
from configuration $\mu$; and $A_{P}(\mu\rightarrow\nu)$ the acceptance
probability, i.e., the probability that the algorithm will accept the trial
configuration $\nu$. Hence, since the target distribution in the entropic
sampling is the inverse of the DoS, i.e., $p_{\mu}\propto
g(E_{\mu})^{-1}=\exp[-S(E_{\mu})]$, Eqs. (1) and (2) implies

$\frac{A_{P}(\mu\rightarrow\nu)}{A_{P}(\nu\rightarrow\mu)}=\exp[S(E_{\mu})-S(E_{\nu})]\frac{S_{P}(\nu\rightarrow\mu)}{S_{P}(\mu\rightarrow\nu)}$
(3)

In WL, detailed balance is not fulfilled in general. During the construction
of entropy, the acceptance probability given in step II above (i.e.,
$A_{P}(\mu\rightarrow\nu)=\min\left[1,\exp(S(E_{\mu})-S(E_{\nu}))\right]$)
evolves and it is only when the entropy gets sufficiently refined that
detailed balance is met.

Notice that the form chosen for $A_{P}$ requires that the selection
probability be symmetric (i.e.,
$S_{P}(\mu\rightarrow\nu)=S_{P}(\nu\rightarrow\mu)$). Although this condition
is simple to comply with in models like Ising, for arch-based descriptions of
static granular packs this is non-trivial. Therefore, one must be careful to
represent a system in such a way that trial moves between different
configurations have the same backward and forward selection probability.

After reviewing the main characteristics of the arch-based ensemble in the
next section, we will show that some natural representations of the
microstates lead to non-symmetric selection probability schemes. We present,
however, a way of representing the configurations that does allow for the
direct use of WL. In all the WL simulations, we have used $300$ bins for the
histograms. The tolerance for the $f$ correction was set to
$\epsilon=2^{-15}$. The histogram $H(E)$ is considered flat (see step IV)
whenever $(H_{max}-H_{min})/H_{max}<0.2$, with $H_{max}$ and $H_{min}$ the
maximum and minimum height of the histogram.

##  3 Arch-based microstates

In Ref. [6], we have introduced a way of describing the microstate of a static
granular system under gravity by considering the arches that the grains form
instead of the more traditional approach of using the particle positions.
Arches are defined as sets of mutually stable grains. All other particles
being fixed, the removal of any of the grains in the arch would induce the
destabilization of the rest of the set. Any assembly of grains, static under
gravity, can be split into a number of arches which are mutually exclusive
[16, 17].

The major difficulty in sampling static granular configurations is the fact
that these are sparse (with zero measure) in the overwhelming number of
possible particle positions. Moreover, there are not recipes to generate a
static configuration from another static configuration by simply moving a
grain from its position.

Since each arch is stable on its own right, the arch-based description
warrants that any configuration proposed fulfils a basic stability constraint;
i.e., that each set of grains identified as an arch has internal contacts that
keep it stable. The problem is now moved to generating all possible
combination of arches, including how many of them are of a given size, shape,
orientation and position and also generating all arrangements of these that
can be stable resting on each other. Of course, all of these DoF can be
represented with different levels of approximation.

In Ref. [6], we have described the five general steps necessary to carry out
an Edwards entropy calculation (i.e., the number of states associated to each
given volume of the packing) within an arch-based scheme. These are:

  1. 1.

Define the microstate of the system in terms of arches.

  2. 2.

Define the external constraints imposed to arches.

  3. 3.

Define a volume function that yields the total volume of the microstate in
terms of the arches.

  4. 4.

Define an algorithm to generate all microstates defined in step 1 that comply
with the external constraints of step 2. Or sample microstates with equal
probabilities.

  5. 5.

Calculate the volume of each microstate generated in step 4 using the function
in step 3 and build the DoS.

Step 4 may constitute a significant limitation to the real possibility of
calculating the density of states for systems of reasonable size. Generating
all configurations is certainly impractical for most models (especially if
they have continuous DoF). This paper demonstrates how to sample
configurations by using WL (rather than generating all of them) to accomplish
step 4.

We will focus on a model we have already solved exactly by counting every
single possible configurations so as to have a reference system to compare
with the WL algorithm results. This is the “non-interacting rigid arch model”
(NIRA). In this model, only the number of arches $n_{i}$ of each size $i$ (in
number of grains) that form part of the packing is used to describe the
microstate. All arches consisting of the same number of grains are considered
to occupy the same volume (hence one single possible shape is assumed for each
arch size; this is implied in the word “rigid” used to name the model). The
total volume of the system is assumed to be the sum of the volume of the
individual arches and the arch–arch interlocking DoF is not taken into account
(hence the word “non-interacting”). To represent a two-dimensional pack of
equal-sized disks, we have taken the volume $v_{i}$ of an arch of $i$ grains
to be the area under the regular polygon that inscribes all disks in a
“regular” arch. The special cases of “arches” of one particle and two-particle
arches are considered separately [6]. The total volume $V[\\{n_{i}\\}]$ of the
system is

$V[\\{n_{i}\\}]=\sum_{i=1}^{N}{v_{i}n_{i}}\mathrm{\ where\
}v_{1}=\frac{\sqrt{3}d^{2}}{2},\mathrm{\ }v_{2}=2.1v_{1},$ (4)
$v_{i}=\frac{Nd^{2}}{4}\tan\frac{\pi}{2N}\left[1+\left(\tan\frac{\pi}{2N}\right)^{-1}\right]^{2}\mathrm{\
for\ }i>2.$

Where $N$ is the total number of disks of diameter $d$ in the system.

It is important to mention that, typically, the maximum size that an arch can
take is physically bounded (e.g., due to the size of the container that holds
the granular sample). Hence, we will put a cutoff $C$ to the largest arch
allowed in the system. The cutoff $C$ is an external constraint (that is
imposed in step 2, above). Importantly, this cutoff imposes a limit to the
correlations in the system which leads to an extensive entropy (see Ref. [6])

In counting microstates, one has to bear in mind that arches of the same size
are indistinguishable in the NIRA model, whereas arches of a different size
can be distinguished. Hence, if there are $n_{i}$ arches of $i$ grains in a
configuration (with $i=1,...C$, being $C$ the size cutoff), then the number of
permutation of arches that yield distinguishable microstates with these arches
is

$N_{A}!/(n_{1}!...n_{C}!),$ (5)

where $N_{A}=\sum_{i}n_{i}$ is the total number of arches of the configuration
(including those “arches” of size 1).

(a)

(b)

Figure 1: (a) Entropy as a function of volume for the NIRA model in 2D
calculated by counting all possible configurations for 500 disks [6] using
different arch size cutoffs. (b) The corresponding compactivity calculated by
numerical differentiation.

Despite all the simplifications, the model applied to a 2D system of equal-
sized disks yields qualitative agreement with DEM simulations of tapped disks
[6]. The NIRA model is in many respects similar to an ideal gas of excitations
or quasi-particles (the arches) with a single DoF (their size).

Figure 1(a) shows the entropy $S$ calculated by counting all possible
microstates for $500$ disks using different $C$ for the largest arch allowed
[6]. As it is expected, if $C$ increases, looser configurations are possible
and hence states with higher volumes become more significant. However, the
entropy for low volumes rapidly converges to a well defined curve. Part (b) of
Fig. 1 shows the compactivity $\chi$ defined as $\chi^{-1}=\partial S/\partial
V$. This is the analogue to the temperature in thermal systems [1]. The
entropy presents a maximum as observed by others [2, 3]. States for volumes
beyond this maximum correspond to negative compactivities [see Fig. 1(b)].
This is caused by the inversion population of these volume bounded systems.
Some authors suggest these negative $\chi$ macrostates may be inaccessible,
however, this does not need to be the case; some preparation protocols may
indeed lead to very low packing fractions [3, 18]. An interesting prediction
of the NIRA model is that systems constrained by different $C$ achieve the
same $\chi$ at different specific volume $V/N$ (i.e., at different packing
fractions). As a consequence, two samples of grains “equilibrated” to the same
compactivity will show distinct packing fractions if the maximum arch size
possible in each sample is different. Different values of $C$ in practice may
be achieved by using narrow containers or by changing the static friction
coefficient of the grains. There have been some progress in the study of the
equilibration of vibrated granular samples in “contact” [19]. However, there
are still no attempts to couple static granular packs under gravity. Further
developments in this direction may help validating this prediction of the NIRA
model.

The configurations of the NIRA model are compatible with different
representations. In the following subsections we will discuss some of these
representations and their suitability for the implementation of the WL
algorithm.

###  3.1 The arch size distribution representation

In our previous paper [6], we have used a vector $\\{n_{i}\\}$ that represents
the number of arches consisting of $i$ grains in the configuration, i.e.,
$\\{n_{i}\\}=(n_{1},n_{2},...,n_{C})$, with $C$ the largest arch allowed in
the system and $n_{1}$ the number of grains not forming arches. As an example,
a possible configuration in a system of $N=10$ grains and a cutoff arch length
of $C=6$ represented in this way could be:

$(3,1,0,0,1,0).$ (6)

In this example, there are three grains not forming arches, two grains forming
an arch of size two, and five grains forming another arch of size 5.

In Ref. [6], we have swept all possible configurations and multiplied each by
its analytical degeneration due to the different permutations of arches with
repetitions given by Eq. (5).

It is difficult to propose an algorithm to move between configurations
represented in this way and yet comply with the symmetry of the selection
probability required by the WL algorithm. For example, consider a move that
consists in removing a grain from one arch of size $k$ and adding it to
another arch of size $k^{\prime}$. Such move would require subtracting 1 from
the coordinate $k$ of $\\{n_{i}\\}$ and adding 1 to the coordinate $k-1$,
since this arch will now be smaller by one grain. Additionally, the coordinate
$k^{\prime}$ of $\\{n_{i}\\}$ needs to be reduced in 1 and the coordinate
$k^{\prime}+1$ increased in 1, since this arch will now be part of the set of
arches larger by one grain. There are different ways of selecting a grain to
be moved and to select its arch of destination.

Let us consider, for instance, that all grains and destination arches are
chosen with same probability. Now consider a move in the Markov chain that
takes configuration (6) [i.e., $\mu=(3,1,0,0,1,0)$] into configuration
$\nu=(2,1,0,0,0,1)$. This corresponds to taking one grain that was not forming
an arch and inserting it in the five-particle arch to make it a six-particle
arch. The probability of selecting a particle from an “arch of size one” in
this case is $3/10$. The probability of choosing the arch of size five as the
destination is $1/5$ (there are four other arches in configuration $\mu$ plus
the possibility of leaving the grain on its own without forming an arch with
others). Hence the selection probability is $S_{P}(\mu\rightarrow\nu)=3/50$. A
similar analysis shows that to return to the original configuration
$S_{P}(\nu\rightarrow\mu)=6/10\times 1/4=3/20$ (there are 6 grains out of ten
that can be taken from the six-grain arch and there are three possible other
destination arches plus the case with the grain not forming an arch in the new
configuration). Clearly, this selection probabilities are non-symmetric as
they should be to apply the algorithm of section II.

A possible workaround to the previous representation is to multiply each
coordinate of the vector $\\{n_{i}\\}$ by the corresponding arch size.
Therefore, each coordinate now indicates how many grains are involved in all
arches of the given size. In this new representation, the configuration of Eq.
(6) (10 particles with a cutoff $C=6$) is written as

$\\{n^{\prime}_{i}\\}=(3,2,0,0,5,0)$ (7)

In this case, a trial move may consist in randomly transferring a grain from
one coordinate $k$ to another coordinate $k^{\prime}$. This is done simply by
subtracting 1 to $\\{n^{\prime}_{k}\\}$ and adding 1 to
$\\{n^{\prime}_{k^{\prime}}\\}$. In this representation, the selection
probability of moving a particle from one arch of size $k$ to another of size
$k^{\prime}$ is $S_{P}(\mu\rightarrow\nu)=1/N\times 1/(C-1)$ irrespective of
$k$ and $k^{\prime}$. Hence, the selection probability is symmetric and
suitable to implement the entropic sampling using WL.

Unfortunately, the representation of Eq. (7) does not tell apart two
microstates that differ only in the permutation of two arches of different
sizes. Therefore, the corresponding degeneracy given by Eq. (5) cannot be
accounted for 111One is tempted to add to the degeneracy factor (5) to correct
the entropy in step III of the algorithm. However, the algorithm compensates
this factor in order to obtain a flat histogram. Therefore this is not a
viable solution.. More importantly, the change of representations from Eq. (6)
to Eq. (7) is not an exact mapping because these newly proposed moves allow
for “fractions of arches” to exist since we do not request that the
coordinates of $\\{n^{\prime}_{i}\\}$ be a multiple of $i$ after each move.
For instance, the configuration $(0,0,0,0,0,10)$ is allowed in representation
(7) but does not exist in representation (6). In the new representation such
configuration implies that there is one arch of size $6$ plus a fraction of an
arch of size six. We can still treat these “fracrtions of arches” by assigning
to them a fraction of the arch volume. However, there is a large number of new
unrealistic configurations (there are many ways of chosing a numbers that are
not conmensurate with the arch size) in this representation that will bias the
result for the entropy.

Figure 2 shows the entropy for the NIRA model using representation (7) for
different maximum arch sizes $C$ compared with the exact result obtained by
counting all configurations and all permutations [6]. As we can see, not
including all distinguishable permutations and including the new “fractional
arches” gives a wrong entropy function.

Figure 2: Entropy as a function of volume for the NIRA model calculated using
the WL algorithm (symbols) for representation (7) for $4<C<8$. The full lines
represent the exact results for $200$ grains.

###  3.2 The arch listing representation

As previously discussed, other ways of representing the system should be
carefully chosen in order to ensure that there exist moves that sample the
different configurations uniformly. An alternative natural representation
consists of using a vector, $\\{m_{i}\\}$, with $N$ coordinates, where each
coordinate $m_{i}$ can take any value from $0$ to $C$, the cutoff for the arch
size, provided that $\sum_{i}m_{i}=N$. The content of each coordinate
indicates that the configuration has an arch of that size. The configuration
of Eq. (6) in these representations can be expressed, for example, as

$(5,0,0,1,0,1,2,0,1,0).$ (8)

There are, of course, multiple permutations in Eq. (8) that lead to the same
distribution of arch sizes compatible with Eq. (6).

Trial moves in the system represented in this way can be done by subtracting
one from a non-zero $m_{i}$ and adding one to any other coordinate that has a
value smaller than $C$. This is equivalent to reducing the size of one arch in
one particle and either creating a new arch of size one (if the new coordinate
had a zero value) or increasing the size of another arch. Unfortunately, this
algorithm has a non-symmetric selection probability. $S_{P}=1/N_{A}\times
1/(N-N_{C})$, where $N_{A}$ is the number of arches (i.e., the number of non-
zero coordinates in the configuration) and $N_{C}$ is the number of arches
with the maximum allowed size $C$. Therefore, $S_{P}$ will depend on the total
number of arches and the number of arches of size $C$.

Besides the non-symmetric $S_{P}$, the system represented in this way and
sampled with these trial moves clearly overestimates the number of states of a
given volume. This is because, apart from the $N_{A}!/(n_{1}!...n_{C}!)$
permutations of the distinguishable arches [see Eq. (5)], there are
$N!/(N-N_{A})!$ additional permutations due to the zeros in a given vector in
Eq. (8) (there are $N-N_{A}$ zeros).

One can, in principle, resolve these issues. The selection probability may be
turned into a symmetric one by adapting the acceptance probability in Eq. (3).
The degeneracy due to the presence of zeros in the representation (8) can be
handled by switching to a representation without including these, and allowing
for a vector of variable length. However, although less intuitive, there is a
much simpler, suitable representation that we discuss in the next section.

###  3.3 The binary arch representation

Figure 3: Entropy as a function of volume for the NIRA model with cutoff
$4\leq C\leq 8$ (symbols as in Fig. 2) using the binary arch representation to
carry out the entropic sampling through the WL algorithm for $200$ grains. The
solid lines correspond to the exact counting of microstates from Ref. [6].

Finally, we present a representation that comply with the symmetric selection
probability and simultaneously account for the permutation of distinguishable
arches.

In this case, the system is chosen to be represented by a vector of $N$
coordinates with binary values (zeros and ones). These coordinates are not
associated to specific particles 1, 2, 3, etc. Rather, as we move along the
vector from left to right, we can think the ones as representing a first grain
in an arch (whatever its identity) and the following zeroes as the remaining
particles. For instance, the configuration in equation 6 in this new
representation can be given by

$(\underbrace{1,0,0,0,0}_{5},\underbrace{1}_{1},\underbrace{1}_{1},\underbrace{1,0}_{2},\underbrace{1}_{1}).$
(9)

In this representation, all permutations of arches of different sizes are
accounted for naturally. The sections of the vector representing an arch
[underbraced in Eq. (9)] can be permuted to yield all distinguishable
configurations [see Eq. (5)], which correspond to different vectors in this
binary representation. Indistinguishable configurations corresponding to
permutations of arches of same size are also indistinguishable for the binary
vector.

The number $N_{A}$ of arches in a configuration is simply the sum of all the
elements of the vector. Note that the underbraced numbers coincide in value
and order with the non-zero figures of the vector described by Eq. (8).

The trial moves consist in picking a coordinate and changing the state of that
coordinate (if 1 change to 0 and vice versa). This results in a symmetric
selection probability of
$S_{P}(\mu\rightarrow\nu)=S_{P}(\nu\rightarrow\mu)=1/N$. In each move, the
constraint imposed by the cutoff $C$ must be checked and the trial
configuration must be rejected whenever the constraint is not complied with.

In Fig. 3, the result for this representation and sampling strategy is plotted
along with the exact result showing a remarkable agreement.

##  4 Conclusions

We have been able to compute the entropy of a system of non-interacting rigid
arches using a WL algorithm in the volume ensemble in different
representations.

We have exposed the difficulties in dealing with different representations of
the configurations of arches and the mechanisms used to propose trial moves
for the WL algorithm. These difficulties appear during the choice of a simple
sampling scheme that ensure a symmetric selection probability of
configurations. Additionally, the degeneracy due to distinguishable
permutations of arches pose a further complication in the use of WL. The most
suitable representation that we found for a non-interacting system of rigid
arches resulted in a binary vector.

We believe that entropic sampling of arches through the WL algorithm has a
great potential for testing the granular statistical mechanics hypothesis
(such as equiprobability and ergodicity). Having a sampling algorithm like WL
adapted for these types of models is crucial to continue the road map towards
the refinement of an arch-based framework for static granular packs. In
particular, the non-interacting condition is clearly a crude approximation and
should be lifted, along with the introduction of a more accurate volume
function.

## References

  * [1] S Edwards, R Oakeshott, Theory of powders, Physica A 157, 1080 (1989).
  * [2] S McNamara, P Richard, S K De Richter, G Le Caër, R Delannay, Measurement of granular entropy, Phys. Rev. E 80, 031301 (2009).
  * [3] M P Ciamarra, A Coniglio, Random very loose packings, Phys. Rev. Lett. 101, 128001 (2008).
  * [4] D Asenjo, F Paillusson, D Frenkel, Numerical calculation of granular entropy, Phys. Rev. Lett. 112, 098002 (2014).
  * [5] C S O’Hern, L E Silbert, A J Liu, S R Nagel, Jamming at zero temperature and zero applied stress: The epitome of disorder, Phys. Rev. E 68, 011306 (2003).
  * [6] D Slobinsky, L A Pugnaloni, Arch-based configurations in the volume ensemble of static granular systems, J. Stat. Mech. P02005 (2015).
  * [7] J Lee, New Monte Carlo algorithm: Entropic sampling, Phys. Rev. Lett. 71, 211 (1993).
  * [8] F Wang, D P Landau, Efficient, multiple-range random walk algorithm to calculate the density of states, Phys. Rev. Lett. 86, 2050 (2001).
  * [9] F Wang, D P Landau, Determining the density of states for classical statistical models: A random walk algorithm to produce a flat histogram, Phys. Rev. E 64, 056101 (2001).
  * [10] C Zhou, R N Bhatt, Understanding and improving the Wang-Landau algorithm, Phys. Rev. E 72, 025701 (2005).
  * [11] S Trebst, D A Huse, M Troyer, Optimizing the ensemble for equilibration in broad-histogram Monte Carlo simulations, Phys. Rev. E 70, 046701 (2004).
  * [12] B A Berg, T Neuhaus, Multicanonical ensemble: A new approach to simulate first-order phase transitions, Phys. Rev. Lett. 68, 9 (1992).
  * [13] D P Landau, K Binder, A Guide to Monte Carlo Simulations in Statistical Physics, 2nd ed., Cambridge University Press (2005).
  * [14] R E Belardinelli, V D Pereyra, Fast algorithm to calculate density of states, Phys. Rev. E 75, 046701 (2007).

  * [15] M E Newman, G T Barkema, Monte Carlo methods in statistical physics, Vol. 13, pp. 36-42, Clarendon Press Oxford (1999).
  * [16] L A Pugnaloni, G Barker, A Mehta, Multi-particle structures in non-sequentially reorganized hard sphere deposits, Adv. Complex Syst. 4, 289 (2001).
  * [17] R Arévalo, D Maza, L A Pugnaloni, Identification of arches in two-dimensional granular packings, Phys. Rev. E 74, 021303 (2006).
  * [18] L A Pugnaloni, M Mizrahi, C M Carlevaro, F Vericat, Nonmonotonic reversible branch in four model granular beds subjected to vertical vibration, Phys. Rev. E 78, 051305 (2008).
  * [19] J G Puckett, K E Daniels, Equilibrating temperaturelike variables in jammed granular subsystems, Phys. Rev. Lett. 110, 058001 (2013).