# Quantification of Actual Road User Behavior
on the Basis of Given Traffic Rules

Daniel Bogdoll1,∗, Moritz Nekolla1,∗, Tim Joseph1, J. Marius Zöllner1 1FZI
Research Center for Information Technology, Karlsruhe, Germany<EMAIL_ADDRESS>
###### Abstract

Driving on roads is restricted by various traffic rules, aiming to ensure
safety for all traffic participants. However, human road users usually do not
adhere to these rules strictly, resulting in varying degrees of rule
conformity. Such deviations from given rules are key components of today’s
road traffic. In autonomous driving, robotic agents can disturb traffic flow,
when rule deviations are not taken into account. In this paper, we present an
approach to derive the distribution of degrees of rule conformity from human
driving data. We demonstrate our method with the Waymo Open Motion dataset and
Safety Distance and Speed Limit rules.

**footnotetext: These authors contributed equally

##  I Introduction

Human traffic participants have the ability to slightly bend traffic rules in
order to keep traffic flowing or to react to special situations. While strong
violations of rules are unacceptable, slight twists regarding the rule
conformity (RC) are socially accepted. Especially in corner case situations
[1], a flexibility that goes beyond enforced traffic rules is often necessary.
Unfortunately, this knowledge about human behavior is not freely available but
can be extracted from datasets. In informed machine learning [2, 3] such
knowledge can be of great value. While Deep Learning brought unmatched
performance, many questions such as rule enforcement, explainability or
plausibility checks remain open, driving the field of informed machine
learning. For example, an autonomous vehicle system can be enriched with
knowledge about human behavior to improve the overall traffic flow. However,
prior knowledge needs to be picked carefully. If it narrows down the landscape
of solutions too much, the benefits of deep learning diminish.

While there are traffic rules that offer a lot of room for interpretation and
can only be used as a source of knowledge in a more complex way, many traffic
rules are directly quantifiable and therefore a suitable knowledge source.
However, human drivers do not strictly follow these rules in the real world.
Their behavior differs from situation to situation, since they utilize their
prior experience. That process of valuing the importance of each rule at any
given time enables humans to properly deal with a wide variety of situations.
Therefore, static traffic rules can be formally enriched based on human
interpretation. Collin et al. [4] provide a framework based on [5] for rule-
based planning which incorporates rule deviations. However, this allowed
“degree of violation […] with respect to the rule” is not described and left
to the user to set. This open research question is a core motivation for our
work.

Figure 1: Scenario 1, scene 71 in the validation.tfrecord-00018-of-00150 file
from the Waymo Open Motion Dataset shows traffic at an intersection.
$\varphi_{1}$ represents the Safety Distance rule and $\varphi_{2}$ refers to
Speed Limit rule. The histograms show the degrees of rule conformity for
selected vehicles.

Research Gap. Existing research most often extracts knowledge from data
without being able to examine certain aspects of it [6, 7]. The only closely
related work from Cho and Oh [8] that addresses the specific topic of degrees
of rule conformity does only perform the quantification based on an in-house
simulation that does not provide data about actual human behavior.
Additionally, they neither disclose their algorithms nor the results.

Contribution. Quantifying knowledge about human behavior in respect to traffic
rules is the core contribution of this paper. For this purpose, we demonstrate
our method by analyzing the expert behavior from the Waymo Open Motion dataset
[9] based on the rules Safety Distance and Speed Limits. The code is available
at https://url.fzi.de/iv2022

In Chapter II, we give an overview over previous work. In Chapter III, we
describe the traffic rules and how we extracted human behavior distributions
regarding these rules from the dataset. Finally, in chapter IV we discuss the
results.

##  II Related Work

Figure 2: Overview of the quantification process for the Safety Distance rule.
Within every scenario $s$ of the dataset, which consist of $T$ frames each, we
first calculate the score $RC^{dist}_{n,t}$ per vehicle $n$ and frame $t$.
Then, we compute the average score $RC^{dist}_{n,s}$ for each vehicle $n$ over
all frames. Now, we are able to compute the average over all vehicles
$RC^{dist}_{s}$ as the average of a whole scenario. Finally, this allows us to
compute the average score for the whole dataset $RC^{dist}_{total}$. The
intermediate steps allow us to describe single vehicles, sceneOverviews,
scenarios and to generate the behavioral distribution for the whole dataset.

In autonomous driving, datasets are in many ways the backbone of current
developments, be it for their usage as training data or their ability to
benchmark algorithms and models. Since the release of the KITTI dataset [10]
in 2012, many more datasets with increased size and variety have emerged [11].
The process of analyzing datasets to gain further insights has a wide range of
applications, often with the aim to extract knowledge from them. To develop
autonomous vehicles that show more human-like behavior, which includes
enhanced flexibility in many types of situations, datasets can be utilized to
extract the observed human behavior in the data.

Abstract Knowledge Extraction. There exist many ways to utilize knowledge from
datasets for the planning task of an autonomous vehicle. Supervised imitation
learning can utilize recordings as training data for Convolutional Neural
Networks (CNN) to learn to directly predict steering commands from sensor data
of the ego vehicle [6]. In the related field of Inverse Reinforcement Learning
[7], existing data is used to learn the reward function for a Reinforcement
Learning agent based on the observed behavior of road users. Prediction
methods [12] are among the most prominent methods in this field, as their core
task is to predict human behavior. Predictions can also be applied to the ego-
vehicle as a reference trajectory to follow or as an additional input for the
planning module [13], since own actions and the actions of other road users
are intertwined. In [14], constraints were extracted from human driving
trajectories. These constraints can be combined with simple cost functions in
motion planning, enabling interpretability and more human-like behavior. In
contrast to these approaches, which only extract abstract behavior, our method
is able to quantify and assign knowledge to general concepts, such as traffic
rules.

Traffic Rule Violations. The intent of violating traffic rules was first
analyzed in [15] based on questionnaires, not representing actual behavior
from recorded data. In [16], data from the “Automated Enforcement System” in
China was analyzed. This system can detect 12 different traffic rule violation
types. The authors focus on the location-based type and frequency of such
violations. Similarly, in [17], the frequency of violations in a simulation
was analyzed. These methods focus on geographical distributions of traffic
rule violations. While similar to the aforementioned methods in the sense that
they deal with traffic rule violations, our approach is directly linked to the
behavior of individuals and the scenarios they act in. This allows for an
analysis of the severity of violations related to drivers.

Rule-based Learning. In [18, 19], the idea of rule-based learning from
demonstrations was investigated. The authors rated expert demonstrations based
on given rules, formulated with the signal temporal logic language. This way,
it was possible to only learn primarily from demonstrations that fulfil a
defined quality. They demonstrated their approach with small, self-designed
experiments instead of applying it to real-world data. The idea of “data
driven rule books” was explored in [20], where “a model may be generated based
on human driving behavior that governs how an autonomous vehicle maneuvers in
that scenario”. Unfortunately, there is no scientific work based on the patent
that would reveal more details about the procedure. The idea of deriving
values for rule conformity from given traffic rules was originally developed
in [8] and continued in [21] in order to overcome dilemma situations and
generate more human-like behavior. The authors formulated traffic rules as
signal temporal logic (STL) formulas, which enables the generation of
satisfaction margins for any given rule. This margin or “robustness slackness”
is calculated by observing expert behavior. Their quantification is based on
an in-house simulation that does not provide data about actual human behavior.
Beyond their conceptual approach, our work enables behavioral analysis of
human drivers based on real data and discusses the distribution of driving
behaviors in the Waymo Open Motion Datasets.

##  III Method

The core of our work is the ability to derive the distribution of human
behavior in relation to given rules from real world datasets. For this
quantification, we distinguish between global and local rule conformity. While
local rule conformity is dependent on a specific situation, that lead to the
deviation of a rule, the global degree of conformity is the distribution over
a whole scenario or dataset. In this work, we propose a method for the
quantification of global rule conformity. Rule conformity describes the degree
of compliance with a traffic rule.

In our work, our aim is to provide global rule conformity distributions and
average values $RC$ on scenario- and dataset levels. These describe the
compliance with which the drivers have followed traffic rules. In this paper,
we exemplarily calculated the scores for the Waymo Open Motion Dataset [9] as
shown in Figure 2. It consists of 103,354 segments, each containing 20 seconds
of footage from urban to suburban terrain from six different cities among the
USA. The segments were further broken down into scenarios of different
lengths. We follow the definitions of scene and scenario by Ulbrich et al.
[22], where a scene is a single frame $t$, and a scenario $s$ consists of
successive scenes.

The Waymo dataset consists of detailed object lists with corresponding map
data. While we are generally also interested in behavior on German roads,
there is no large-scale motion data set with corresponding map data that has
been recorded in Germany. While we are aware of motion datasets (partly)
recorded in Germany, such as [23, 24, 25], these are insufficient in size and
variety for our quantification approach. However, since the traffic laws in
the USA are similar to those in Germany, we deem the Waymo dataset
appropriate, keeping the domain gap small. For performance reasons, we analyze
the dataset at a rate of 1 Hz instead of the provided 10 Hz. Since our code is
open-source, all parameters can be adjusted to rerun the analysis for enhanced
precision.

###  III-A Rule Conformity for Safety Distances

A Safety Distance between vehicles in Germany is regulated in the road traffic
regulations (Straßenverkehrs-Ordnung (StVO)), §4 cl. 1: “As a rule, the
distance to a vehicle in front must be large enough to allow stopping behind
it even if it brakes suddenly.” [26]. To fulfil this requirement, we
implemented the three-second rule [27], which is a recommended practice in the
USA, thus bridging the domain gap between German laws and data recorded in the
USA. Mathematically expressed, in a scenario $s$ at time $t$, for each driver
$n$, their position $P^{n}_{t}$ is multiplied by three times their velocity
vector $\vec{v}_{n,t}$ to receive the future position $P^{n}_{t+1}$. $P$
denotes the center foremost point of a vehicle. That forms the vector
$\vec{z}_{n,t}=(P^{n}_{t},P^{n}_{t+1})$ which expresses the distance the
vehicle would travel in one direction within three seconds at constant speed.
A violation occurs if there exists an intersection between the area
$A_{P^{k}_{t}}$ covered by another vehicle $k$ with position $P^{k}_{t}$ and
$\vec{z}_{n}$. Then, $c_{n,k,t}$ denotes the distance between $P^{n}_{t}$ and
the intersection point of $\vec{z}_{n}$ and $A_{P^{k}_{t}}$. In case of
multiple intersections, the closest vehicle is taken into account. As shown in
Figure 3, we calculate the rule conformity degree $RC^{dist}_{n,t}$ for driver
$n$ as follows:

$RC^{dist}_{n,t}=\begin{cases}\begin{aligned}
&\frac{c_{n,k,t}}{|\vec{z}_{n,t}|}\quad\text{if }\,\exists
k:A_{P^{k}_{t}}\,\cap\,\vec{z}_{n,t}\mid k\neq n\\\ &1\hskip
25.00003pt\text{else}\end{aligned}\end{cases}$ (1)

The equation ensures that $RC^{dist}\in[0,1]$ at all times. Besides the center
point of each car, this procedure is repeated with the left and right edges as
well, as shown in Figure 3. That is, to take into account curves and cars that
are slightly offset from each other.

Figure 3: Computation of the Safety Distance rule conformity degree. In a), no
rule violation occurs. In b), a violation is shown, where
$|\vec{z}_{n}|=9~{}m$ is the distance according to the three-second-rule and
$c_{n}=8.5~{}m$ the distance between the ego vehicle and the intersection
point between $\vec{z}_{n}$ and the vehicle ahead.

Accumulating these individual values, we retrieve an average for every
scenario $s$ in the dataset including $N$ drivers in $T$ frames. A scenario
itself consists of a road graph with several frames that contains drivers and
their properties:

$RC^{dist}_{s}=\frac{1}{N}\sum_{n=0}^{N}\Bigl{(}\frac{1}{T}\sum_{t=0}^{T}RC^{dist}_{n,t}\Bigl{)}$
(2)

For the scene shown in Figure 4, $RC^{dist}_{s}\approx 0.9098$. In other
words, the drivers bend the Safety Distance rule, on average, by around 10%.

We apply several pre-processing steps on the data to avoid a distortion of the
resulting distribution. Vehicles below a velocity of $5~{}km/h$ are discarded
from the calculations, since they are typically either stuck in a traffic jam,
waiting at a red light or parking. Since the projected position for the
calculation of the Safety Distance does not incorporate lanes, only vehicles
that are heading in a similar direction are taken into account, allowing an
angular deviation of $20~{}\%$. Figure 4 shows an example: Even though the
projection $P^{n}_{t+1}$ of the vehicle, which currently turns right, ends in
another vehicle, it is not considered a violation.

Figure 4: Visualization of the Safety Distance rule analysis. Purple vectors
refer to the vehicle’s projected position three seconds into the future. If
these vectors intersect with another vehicle, under certain conditions a pink
line indicates a rule violation. The scene displays five drivers that are
disobeying the Safety Distance rule.

###  III-B Rule Conformity for Speed Limits

To assign the currently effective Speed Limit to individual vehicles, we took
center lines into account, as these are assigned lane speed limit information
in the Waymo map data. For every driver $n$, a lane $k$ is assigned based on
the minimum euclidean distance. Since Waymo represents lanes as polylines,
consisting of multiple points instead of defined vectors, it was necessary for
each driver $n$ to calculate the euclidean distance to all points of the
polylines. We filtered out vehicles that exceed a distance threshold of
$10~{}m$ to their assigned center line in order to avoid misclassifications.
This large threshold is due to the fact that some lanes in the map data do not
contain center lines. For instance, in figure 5, all vehicles have the correct
speed limit assigned even though center lines are missing. Furthermore, we
omit vehicles below $80\%$ of the speed limit to exclude parked or congested
vehicles. Afterwards, the Speed Limit Conformity degree $RC^{speed}_{n,t}$ for
driver $n$ at time $t$ is calculated:

$RC^{speed}_{n,t}=min(1,\frac{limit_{k}}{v_{n,t}})$ (3)

Here, $limit_{k}$ denotes the speed limit of lane $k$ that corresponds to
vehicle $n$ in state $t$. $v_{n}$ denotes the velocity of driver $n$.
Accumulating these individual values, we retrieve an average rule conformity
degree for every scenario in the dataset:

$RC^{speed}_{s}=\frac{1}{N}\sum_{n=0}^{N}\Bigl{(}\frac{1}{T}\sum_{t=0}^{T}RC^{speed}_{n,t}\Bigl{)}$
(4)

Figure 5: Visualization of the Speed Limit rule analysis. There are lanes in
two directions, where the lanes on the left side are crowded. These vehicles
are relatively slow and thus discarded from the quantification process and
marked yellow. On the right side, vehicles that drive according to the speed
limit appear violet, whereas cars above the limit are marked pink.

For the scene shown in Figure 5, $RC^{speed}_{s}\approx 0.9677$. It reveals
the underlying filter process, that discards the crowded left lane, because of
their slow velocity. On the right lane, the traffic is fluent and therefore
utilized for the algorithm.

##  IV Evaluation

In the previous sections we have introduced the Waymo Open Motion dataset, the
two traffic rules Safety Distance and Speed Limit and our quantification
methodology to derive the rule conformity per driver and scenario. In this
chapter, we will extend the evaluation to the complete data set to obtain a
general behavioral distribution. The process can be applied to any motion
dataset to determine these behavior distributions for other, such as country-
specific, domains.

After computing the average scores $RC^{dist}_{s}$, $RC^{speed}_{s}$ for each
scenario $s$, we can compute the average over the total number of scenarios
$S$ for both $RC^{dist}_{total}$ and $RC^{speed}_{total}$:

$RC_{total}=\frac{1}{S}\sum_{s=0}^{S}RC_{s}$ (5)

Since this value only represents the average over all scenarios per traffic
rule, a more meaningful insight is the distribution of behaviors. To compute
it, we performed the following steps per traffic rule:

  1. 1.

For each scenario, we calculated $RC_{n,t}$ for every driver $n$ at each frame
$t$

  2. 2.

For each driver $n$ in a scenario $s$, we determined their average
$RC_{s,n}=\frac{1}{T}\sum_{t=0}^{T}RC_{n,t}$ over all frames $t$

  3. 3.

We computed the distribution over all $RC_{s,n}$. Thus, every data point
represents the averaged behavior of a single driver in a specific scenario. We
visualized the data as histograms

###  IV-A Safety Distance

Figure 6: Distribution of the rule conformity in regard to Safety Distances.
In a), the absolute numbers of binned $RC$ values are shown on a logarithmic
scale. In b), the relative amount of $RC$ values is summarized in four bins.

A clear picture emerges from the behavioral analysis, where we analyzed
14,317,443 data points. With $RC^{dist}_{total}=0.867$, the data shows that
many drivers do not strictly follow the Safety Distance rule. This is in line
with prior assumptions from own experiences. Figure 6 a) shows the behavior
distribution regarding the compliance with the Safety Distance rule in
absolute numbers. We divided the $RC_{n,s}$ values into 20 bins and used a
logarithmic scale to obtain a suitable histogram. As you can see in the
histogram on the left, the numbers are slightly increasing again for the first
bin. Our analysis shows that there are perception errors in the Waymo Open
Motion data set. These scenes mostly show overlapping vehicle detections.
Since we only used generic rules for our pre-processing instead of correcting
dataset-specific errors, these also show up in the final distribution.

The rightmost bin at $1.0$ displays the number of drivers that follow Safety
Distance rule strictly, whereas the other bins visualize the magnitude of rule
bending. On the other side, there are hardly any deviations below a value of
$0.4$ .

In order to analyze the relative amount of local rule conformity scores, we
generated a percentage plot as shown in Figure 6 b). It shows with the
rightmost bar that over $50~{}\%$ of all drivers adhere to the rule strictly,
while drivers bend the distance rule to some extent in all other cases.
However, strong violations are rather seldom, since the interval $[0.75,1.0]$,
or the orange and pink bar respectively, add up to almost 80%. To conclude,
the distribution shows that most drivers follow the rule strictly or only with
minor deviations.

###  IV-B Speed Limit

Figure 7: Distribution of the rule conformity in regard to Speed Limits. In
a), the absolute numbers of binned $RC$ values are shown on a logarithmic
scale. In b), the relative amount of $RC$ values is summarized into four bins.

Unlike Safety Distance, Speed Limit is a highly controlled traffic rule. With
a $RC^{speed}_{total}=0.967$ the results of Figure 7 a) reveal that the global
degree of rule compliance is relatively close to $1.0$. Here, we analyzed
4,400,350 data points. The significantly lower magnitude of the bin height
compared to Figure 6 is a result of our extensive pre-processing. As mentioned
in III-B we filtered out most of the drivers, that are either waiting on red
lights or are stuck in traffic jam, which reduces the number of tracked
vehicles. In contrast to the Safety Distance rule, we encountered almost only
$RC$ values above $0.75$ among the dataset, as shown in Figure 7 b). Values
below this were rather rare. Thus, drivers usually drive no more than $25\%$
above the speed limit. Nevertheless, the relative plot in Figure 7 b) shows,
that in more than $60~{}\%$ of the time, the rule is strictly observed.
Contrary to the results of the Speed Limit rule, we did not expect this
behavior. The reasons for this could be a general speed limit and
significantly higher penalties for exceeding it. This indicates a domain gap
compared to the behavior on German roads. To conclude, the deviations in
regard to the Speed Limit rule are significantly lower than for the Safety
Distance rule. Especially severe violations are extremely rare among the
dataset.

##  V Conclusion

Traffic rules are static constructs that aim to guide road users safely
through traffic. In doing so, human road users usually do not adhere strictly
to these rules, but with certain deviations. In this work, we developed a
framework to quantify human behavior in respect to given traffic rules for
motion datasets. We demonstrated our approach based on the Waymo Open Motion
Dataset. We analyzed the behavior regarding two rules, namely Safety Distance
and Speed Limits, for which we extracted behavior distributions and averages
for scenarios and the whole dataset. In addition, we took some pre-processing
steps to keep the data as meaningful as possible and to remove noise. All our
code including extraction, pre-processing and visualization is publicly
available at https://url.fzi.de/iv2022.

We found that there is significantly more deviation in respect to the Safety
Distance rule than for the Speed Limit rule. In addition, the magnitude of
violations is larger in the Safety Distance rule, as there are more strong
violations. However, the Speed Limit rule is also frequently deviated from,
thus both rules are not strictly followed.

These results made us confident that additional knowledge on human behavior
instead of only relying on given, static traffic rules is necessary for
autonomous vehicles to perform more flexible and in a more human-like style.
When designing a system that is limited by rules, it is of utmost importance
to also analyze the degree of such restrictions. Such investigations reveal
the true importance of a rule, which could differ from biased developer
assumptions.

With parallelized algorithms, we want to analyze the complete data set instead
of the 1 Hz samples in the future. Additionally, the analysis in respect to
further rules is of interest, especially if a large and diverse dataset
recorded in Germany might be available in the future. Such extensions should
closely follow the approach presented in this paper. For this purpose, a
formal definition of the rules should be made in each case and these should be
made quantifiable. The extraction must be performed on as large dataset as
possible, e.g., from Waymo, in order to obtain a meaningful statement about
the underlying rule conformity of drivers. New rules can add a significant
amount of implementation overhead and significantly increase runtime.
Regarding applications of this framework, we envision many opportunities. The
detection of interesting scenes and scenario based on the scenario-based
degrees of rule conformity is one example. Also, based on the global
distribution, rewards in Reinforcement Learning can be shaped to improve
human-like behavior.

##  VI Acknowledgment

This work results partly from the project KI WISSEN (19A20020L), funded by the
German Federal Ministry for Economic Affairs and Climate Action (BMWK).

## References

  * [1] D. Bogdoll, J. Breitenstein, F. Heidecker, M. Bieshaar, B. Sick, T. Fingscheidt, and J. M. Zöllner, “Description of Corner Cases in Automated Driving: Goals and Challenges,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV) Workshops_ , 2021.
  * [2] L. von Rueden, S. Mayer, K. Beckh, B. Georgiev, S. Giesselbach, R. Heese, B. Kirsch, M. Walczak, J. Pfrommer, A. Pick, R. Ramamurthy, J. Garcke, C. Bauckhage, and J. Schuecker, “Informed Machine Learning - A Taxonomy and Survey of Integrating Prior Knowledge into Learning Systems,” _IEEE Transactions on Knowledge and Data Engineering_ , 2021.
  * [3] J. Wörmann et al., “Knowledge Augmented Machine Learning with Applications in Autonomous Driving: A Survey,” _arXiv preprint:2205.04712_ , 2022.
  * [4] A. Collin, A. Bilka, S. Pendleton, and R. D. Tebbens, “Safety of the intended driving behavior using rulebooks,” in _IEEE Intelligent Vehicles Symposium (IV)_ , 2020.
  * [5] A. Censi, K. Slutsky, T. Wongpiromsarn, D. Yershov, S. Pendleton, J. Fu, and E. Frazzoli, “Liability, ethics, and culture-aware behavior specification using rulebooks,” in _International Conference on Robotics and Automation (ICRA)_ , 2019.
  * [6] M. Bojarski, D. D. Testa, D. Dworakowski, B. Firner, B. Flepp, P. Goyal, L. D. Jackel, M. Monfort, U. Muller, J. Zhang, X. Zhang, J. Zhao, and K. Zieba, “End to End Learning for Self-Driving Cars,” _arXiv preprint:1604.07316_ , 2016.
  * [7] M. Kuderer, S. Gulati, and W. Burgard, “Learning driving styles for autonomous vehicles from demonstration,” _IEEE International Conference on Robotics and Automation (ICRA)_ , 2015.
  * [8] K. Cho and S. Oh, “Learning-Based Model Predictive Control Under Signal Temporal Logic Specifications,” in _IEEE International Conference on Robotics and Automation (ICRA)_ , 2018.
  * [9] P. Sun, H. Kretzschmar, X. Dotiwalla, A. Chouard, V. Patnaik, P. Tsui, J. Guo, Y. Zhou, Y. Chai, B. Caine _et al._ , “Scalability in perception for autonomous driving: Waymo open dataset,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020.
  * [10] A. Geiger, P. Lenz, and R. Urtasun, “Are we ready for Autonomous Driving? The KITTI Vision Benchmark Suite,” in _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2012.
  * [11] D. Bogdoll, F. Schreyer, and J. M. Zöllner, “ad-datasets: a meta-collection of data sets for autonomous driving,” _arXiv preprint:2202.01909_ , 2022.
  * [12] M. Ye, T. Cao, and Q. Chen, “Tpcn: Temporal point cloud networks for motion forecasting,” _IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2021.
  * [13] A. Venkatraman, “Forecasting for motion planning,” _Presentation at IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2021.
  * [14] K. Rezaee and P. Yadmellat, “How to not drive: Learning driving constraints from demonstration,” _arXiv preprint:2110.00645_ , 2021.
  * [15] E. D., “Theory of planned behavior and pedestrians’ intentions to violate traffic regulations,” _Transportation Research Part F: Traffic Psychology and Behaviour_ , 2002.
  * [16] Y. Li, M. Abdel-Aty, J. Yuan, Z. Cheng, and J. Lu, “Analyzing traffic violation behavior at urban intersections: A spatio-temporal kernel density estimation approach using automated enforcement system data,” _Accident Analysis & Prevention_, 2020.
  * [17] B. Helou, A. Dusi, A. Collin, N. Mehdipour, Z. Chen, C. Lizarazo, C. Belta, T. Wongpiromsarn, R. D. Tebbens, and O. Beijbom, “The reasonable crowd: Towards evidence-based and interpretable models of driving behavior,” _arXiv preprint:2107.13507_ , 2021.
  * [18] P. Aniruddh Gopinath, D. Jyotirmoy V., and N. Stefanos, “Learning from demonstrations using signal temporal logic,” in _CoRL_ , 2020.
  * [19] A. G. Puranic, J. V. Deshmukh, and S. Nikolaidis, “Learning From Demonstrations Using Signal Temporal Logic in Stochastic and Continuous Domains,” _IEEE Robotics and Automation Letters_ , 2021.
  * [20] A. Censi, K. Slutskyy, A. A. Devi, C. Z. Xuan, and Z. Chen, “Data driven rule books,” 2021.
  * [21] K. Cho, T. Ha, G. Lee, and S. Oh, “Deep Predictive Autonomous Driving Using Multi-Agent Joint Trajectory Prediction and Traffic Rules,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2019.
  * [22] S. Ulbrich, T. Menzel, A. Reschka, F. Schuldt, and M. Maurer, “Defining and Substantiating the Terms Scene, Situation, and Scenario for Automated Driving,” in _Proc. of ITSC_ , 2015.
  * [23] W. Zhan, L. Sun, D. Wang, H. Shi, A. Clausse, M. Naumann, J. Kümmerle, H. Königshof, C. Stiller, A. de La Fortelle, and M. Tomizuka, “INTERACTION Dataset: An INTERnational, Adversarial and Cooperative moTION Dataset in Interactive Driving Scenarios with Semantic Maps,” _arXiv:1910.03088 [cs, eess]_ , 2019.
  * [24] J. Bock, R. Krajewski, T. Moers, S. Runde, L. Vater, and L. Eckstein, “The ind dataset: A drone dataset of naturalistic road user trajectories at german intersections,” in _IEEE Intelligent Vehicles Symposium (IV)_ , 2020.
  * [25] T. Fleck, K. Daaboul, M. Weber, P. Sch”orner, M. Wehmer, J. Doll, S. Orf, N. Sußmann, C. Hubschneider, M. R. Zofka, F. Kuhnt, R. Kohlhaas, I. Baumgart, R. Z”ollner, and J. M. Z”ollner, “Towards large scale urban traffic reference data: Smart infrastructure in the test area autonomous driving baden-w”urttemberg,” in _Intelligent Autonomous Systems 15 - Proceedings of the 15th International Conference IAS-15_ , 2018.
  * [26] German Federal Ministry of Justice, “Straßenverkehrs-Ordnung (StVO),” 2013\.
  * [27] J. Karlsson, S. van Waveren, C. Pek, I. Torre, I. Leite, and J. Tumova, “Encoding Human Driving Styles in Motion Planning for Autonomous Vehicles,” in _IEEE International Conference on Robotics and Automation (ICRA)_ , 2021.


# Asynchronous Guessing Subject to Distortion

Shigeaki Kuzuoka  Wakayama University
Email<EMAIL_ADDRESS>
###### Abstract

The problem of guessing subject to distortion is considered, and the
performance of randomized guessing strategies is investigated. A one-shot
achievability bound on the guessing moment (i.e., moment of the number of
required queries) is given. Applying this result to i.i.d. sources, it is
shown that randomized strategies can asymptotically attain the optimal
guessing moment. Further, a randomized guessing scheme which is feasible even
when the block size is extremely large is proposed, and a single-letter
characterization of the guessing moment achievable by the proposed scheme is
obtained.

##  I Introduction

Consider the problem of guessing the realized value $x$ of a random variable
$X$ using a sequence of queries of the form “Is $X=x$?”. We are interested in
how many queries are required until an affirmative answer is obtained; the
number is called the _guesswork_. This guessing problem was introduced by
Massey [1], where the expectation of guesswork was investigated. Subsequently
Arikan [2] investigated the $\rho$-th moment $G_{\rho}$ of guesswork, which is
called the _guessing moment_. Further, Arikan and Merhav [3] extended Arikan’s
result [2] to the lossy case, where the value $x$ of $X$ is not necessarily
identified but it is required to find a value $\hat{x}$ satisfying
$d(x,\hat{x})\leq\Delta$ for given distortion measure $d$ and distortion level
$\Delta$.

Recently asynchronous guessing problem was introduced by Salamatian et al.[4]
as an information-theoretic model for brute-force botnet attacks. In the
asynchronous setting, the guesser is restricted so that it does not know which
queries were already asked. In [4], a modified variation $V_{\rho}$ of the
guessing moment $G_{\rho}$ attainable by asynchronous guessing strategies is
investigated. Their result implies that the optimal asynchronous guessing is
given by _randomized guessing_ , where the guesser choses a query according to
a certain probability distribution, and that the penalty of lack of
synchronization is asymptotically negligible.

The primary motivation of this work is to extend the study of [4] to the lossy
case. Specifically, randomized guessing subject to distortion is studied. Our
model provides a simplified mathematical model for brute-force attacks against
bio-metrics authentication, where attacker’s task is to find a query which is
sufficiently similar to the bio-metric data stored in the system.

###  I-A Contributions

Our first contribution is to give an achievability bound on $V_{\rho}$ in
terms of a variation of the Rényi entropy (Theorem 1). In particular, when the
order $\rho$ of the moment is an integer, we directly evaluate the guessing
moment $G_{\rho}$ and give an achievability bound (Theorem 2 and its
corollaries). Our achievability result reveals that there exists a
deterministic quantizer $\pi$ which does not depend on the parameter $\rho$
and the optimal guessing strategy is given by the tilted distribution of the
quantized $\hat{X}=\pi(X)$.

Next we apply our achievability bound to independent and identically
distributed (i.i.d.) sources, and then, show that synchronization is not
necessary to achieve the asymptotically optimal guessing moment. Furthermore,
for asymptotic case, we propose i.i.d. asynchronous guessing strategies, which
are simple and feasible even when the block size $n$ is extremely large. We
investigate the asymptotic performance of i.i.d. asynchronous guessing
strategies and give a single-letter characterization of the optimal guessing
moment achievable by i.i.d. strategies (Theorem 3 and its corollary).

###  I-B Related Work

The study of guessing was pioneered by Massey [1]. Arikan [2] demonstrated
that the Rényi entropy [5] characterizes the guessing moment (up to some
factor). Recently, tighter bounds on the guessing moment were given by Sason
and Verdú [6].

The guessing problem has been studied in various contexts such as guessing
allowing errors [7], guessing subject to distortion [3, 8], investigation of
large deviation perspective of guessing [9, 10], guesswork in multi-user
systems [11], and guesswork with distributed encoders [12] and so on.

Applications of guessing are around the information security, e.g., cracking
passwords; See the introduction of [4] and Section II of [13] for review on
guessing and security. To understand the impact of synchronization in botnet
attacks, Salamatian et al.[4] proposed a simplified model for distributed
brute-force attacks and introduced randomized guessing. Merhav and Cohen [13]
studied randomized guessing under source uncertainty and proposed the
universal randomized guessing strategy based on the LZ78 data compression
algorithm [14]. The problem of randomized guessing under the individual-
sequence approach was also investigated by Merhav [15].

###  I-C Organization

The rest of this paper is organized as follows. In Section II, we introduce a
variation of the Rényi entropy and its property. Section III describes our
main results; one-shot results are given in Section III-A and asymptotic
results for i.i.d. sources are given in Section III-B. All theorems are proved
in Section IV. Section V concludes the paper.

##  II Preliminary

Let $\mathcal{X}$ and $\hat{\mathcal{X}}$ be finite alphabets. Let
$d\colon\mathcal{X}\times\hat{\mathcal{X}}\to[0,\infty)$ be a distortion
measure and fix the distortion level $\Delta\geq 0$. For each
$x\in\mathcal{X}$, let
$\mathcal{A}_{\Delta}(x)\triangleq\\{\hat{x}\in\hat{\mathcal{X}}:d(x,\hat{x})\leq\Delta\\}$.
We assume that $\mathcal{A}_{\Delta}(x)\neq\emptyset$ for any
$x\in\mathcal{X}$.

In the discussion of one-shot guessing, we will use the quantity
$H_{\alpha}^{\Delta}(X)$, which was introduced in [8]. Let
$\mathcal{W}_{\Delta}$ be the set of conditional distributions $P_{\hat{X}|X}$
such that $\Pr\\{d(X,\hat{X})\leq\Delta\\}=1$ (or equivalently
$P_{\hat{X}|X}(\hat{x}|x)=0$ if $d(x,\hat{x})>\Delta$). Then
$H_{\alpha}^{\Delta}(X)$ is defined as follows.

###### Definition 1

For $\alpha\in(0,1)\cup(1,\infty)$,

$\displaystyle
H_{\alpha}^{\Delta}(X)\triangleq\inf_{P_{\hat{X}|X}\in\mathcal{W}_{\Delta}}H_{\alpha}(\hat{X})$
(1)

where $H_{\alpha}(\hat{X})$ is the Rényi entropy of $\hat{X}\sim
P_{\hat{X}}$:111Throughout the paper, $\log$ denotes the natural logarithm.

$H_{\alpha}(\hat{X})\triangleq\frac{1}{1-\alpha}\log\sum_{\hat{x}\in\hat{\mathcal{X}}}\left[P_{\hat{X}}(\hat{x})\right]^{\alpha}.$

As shown in Appendix A, the infimum in (1) can be achieved by a deterministic
quantizer.

###### Proposition 1

There exists a deterministic function
$\pi\colon\mathcal{X}\to\hat{\mathcal{X}}$ such that
$\pi(x)\in\mathcal{A}_{\Delta}(x)$ for all $x\in\mathcal{X}$ and that
$\hat{X}=\pi(X)$ satisfies, for all $\alpha\in(0,1)$,

$\displaystyle H_{\alpha}(\hat{X})=H_{\alpha}^{\Delta}(X).$ (2)

##  III Main Results

###  III-A One-Shot Bounds

Let us consider a random variable $X\sim P_{X}$ on $\mathcal{X}$. We
investigate the problem of guessing the realization value $x$ of $X$ subject
to the distortion measure $d$.

An asynchronous guessing strategy is determined by a distribution
$P_{\hat{X}}$ on $\hat{\mathcal{X}}$, which is independent of the realization
$x$ of $X$ but may depend on $P_{X}$. The guesser continues to emit i.i.d.
sequence of random variables $\hat{X}_{1},\hat{X}_{2},\dots$ according to
$P_{\hat{X}}$ as long as $d(x,\hat{X}_{i})>D$. The number of guesses
$G(x|P_{\hat{X}})$ is given by the first index $k$ such that
$d(x,\hat{X}_{k})\leq\Delta$ or equivalently
$\hat{X}_{k}\in\mathcal{A}_{\Delta}(x)$. It should be emphasized that, even
when $X=x$ is fixed, the number $G(x|P_{\hat{X}})$ of guesses is a random
variable. It is easily seen that the distribution of $G(x|P_{\hat{X}})$ is the
geometric distribution with the parameter
$P_{\hat{X}}(\mathcal{A}_{\Delta}(x))$, i.e.,

$\displaystyle\Pr\\{G(x|P_{\hat{X}})=k\\}$
$\displaystyle=\left[1-P_{\hat{X}}(\mathcal{A}_{\Delta}(x))\right]^{k-1}P_{\hat{X}}(\mathcal{A}_{\Delta}(x)).$

Thus, for a given parameter $\rho>0$, the $\rho$-th moment of the number of
guesses can be written as

$\displaystyle\mathbb{E}\left[G_{\rho}(X|P_{\hat{X}})\right]=\sum_{x\in\mathcal{X}}P_{X}(x)G_{\rho}(x|P_{\hat{X}})$

where222Note that $G_{\rho}(x|P_{\hat{X}})$ is not a random variable although
$G(x|P_{\hat{X}})$ is.

$\displaystyle
G_{\rho}(x|P_{\hat{X}})\triangleq\sum_{k=1}^{\infty}k^{\rho}\left[1-P_{\hat{X}}(\mathcal{A}_{\Delta}(x))\right]^{k-1}P_{\hat{X}}(\mathcal{A}_{\Delta}(x)).$

While our main interest is $\mathbb{E}\left[G_{\rho}(X|P_{\hat{X}})\right]$,
we first investigate the quantity333The idea of considering the modification
$V_{\rho}$ of the moment $G_{\rho}$ was introduced by Salamatian et al.[4].

$\displaystyle
V_{\rho}(x|P_{\hat{X}})\triangleq\mathbb{E}\left[\binom{G(x|P_{\hat{X}})+\rho-1}{\rho}\right],$

where the expectation $\mathbb{E}$ is taken with respect to the random
variable $G(x|P_{\hat{X}})$ and $\binom{a}{b}$ is the generalized binomial
coefficient defined in terms of the gamma function $\Gamma$, i.e.,

$\displaystyle\binom{a}{b}=\frac{\Gamma(a+1)}{\Gamma(b+1)\Gamma(a-b+1)}.$

The virtue of $V_{\rho}$ is that its value can be explicitly given as follows.

###### Proposition 2

For any guessing strategy $P_{\hat{X}}$ and $\rho>0$,

$\displaystyle
V_{\rho}(x|P_{\hat{X}})=\left(\frac{1}{P_{\hat{X}}(\mathcal{A}_{\Delta}(x))}\right)^{\rho},\quad\forall
x\in\mathcal{X}.$

###### Corollary 1

For any $P_{\hat{X}}$ and $\rho>0$,

$\displaystyle\mathbb{E}[V_{\rho}(X|P_{\hat{X}})]=\sum_{x\in\mathcal{X}}P_{X}(x)\left(\frac{1}{P_{\hat{X}}(\mathcal{A}_{\Delta}(x))}\right)^{\rho}.$

The proposition is proved in Appendix B.

Our one-shot achievability bound on $\mathbb{E}[V_{\rho}(X|P_{\hat{X}})]$ is
stated as follows.

###### Theorem 1

There exists a deterministic function
$\pi\colon\mathcal{X}\to\hat{\mathcal{X}}$ such that, for all $\rho>0$, the
tilted distribution

$\displaystyle
P_{\hat{X}_{\rho}^{*}}(\hat{x})\triangleq\frac{P_{\hat{X}}(\hat{x})^{\frac{1}{1+\rho}}}{\sum_{\hat{x}^{\prime}}P_{\hat{X}}(\hat{x}^{\prime})^{\frac{1}{1+\rho}}}$
(3)

of the distribution $P_{\hat{X}}$ of $\hat{X}=\pi(X)$ satisfies

$\displaystyle\log\mathbb{E}[V_{\rho}(X|P_{\hat{X}_{\rho}^{*}})]\leq\rho
H_{\frac{1}{1+\rho}}^{\Delta}(X).$

The theorem is proved in Section IV-A.

Now we investigate our main interest, i.e., the $\rho$-th moment
$\mathbb{E}[G_{\rho}(X|P_{\hat{X}})]$ of the number of guesses. In particular,
we consider the case where $\rho=1,2,\dots$ is a positive integer.444For non-
integer $\rho>0$, we may numerically evaluate the $\rho$-th moment by using
the technique recently developed in [16]. In this case, we can directly
evaluate $G_{\rho}(x|P_{\hat{X}})$ by using the moment generating function
$M(t)=p_{x}\mathrm{e}^{t}/(1-(1-p_{x})\mathrm{e}^{t})$ of the geometric
distribution with the parameter $p_{x}\triangleq
P_{\hat{X}}(\mathcal{A}_{\Delta}(x))$; e.g., the first four moments are

$\displaystyle G_{1}(x|P_{\hat{X}})$ $\displaystyle=1/p_{x},$ $\displaystyle
G_{2}(x|P_{\hat{X}})$ $\displaystyle=(2-p_{x})/p_{x}^{2},$ $\displaystyle
G_{3}(x|P_{\hat{X}})$ $\displaystyle=(p_{x}^{2}-6p_{x}+6)/p_{x}^{3},$
$\displaystyle G_{4}(x|P_{\hat{X}})$
$\displaystyle=(-p_{x}^{3}+14p_{x}^{2}-36p_{x}+24)/p_{x}^{4}.$

Further, we have upper and lower bounds on $G_{\rho}(x|P_{\hat{X}})$ as
follows.

###### Theorem 2

For any guessing strategy $P_{\hat{X}}$, any $x\in\mathcal{X}$, and any
positive integer $\rho$,

$\displaystyle V_{\rho}(x|P_{\hat{X}})\leq
G_{\rho}(x|P_{\hat{X}})\leq(\rho!)V_{\rho}(x|P_{\hat{X}}),$

or equivalently

$\displaystyle\left(\frac{1}{P_{\hat{X}}(\mathcal{A}_{\Delta}(x))}\right)^{\rho}\leq
G_{\rho}(x|P_{\hat{X}})\leq(\rho!)\left(\frac{1}{P_{\hat{X}}(\mathcal{A}_{\Delta}(x))}\right)^{\rho}.$

###### Corollary 2

For any $P_{\hat{X}}$ and positive integer $\rho$,

$\displaystyle\mathbb{E}[V_{\rho}(X|P_{\hat{X}})]\leq\mathbb{E}[G_{\rho}(X|P_{\hat{X}})]\leq(\rho!)\mathbb{E}[V_{\rho}(X|P_{\hat{X}})]$

and

$\displaystyle\sum_{x\in\mathcal{X}}P_{X}(x)\left(\frac{1}{P_{\hat{X}}(\mathcal{A}_{\Delta}(x))}\right)^{\rho}$
$\displaystyle\leq\mathbb{E}[G_{\rho}(X|P_{\hat{X}})]$
$\displaystyle\leq(\rho!)\sum_{x\in\mathcal{X}}P_{X}(x)\left(\frac{1}{P_{\hat{X}}(\mathcal{A}_{\Delta}(x))}\right)^{\rho}.$

The theorem is proved in Section IV-B.

From Theorems 1 and 2, we can obtain a one-shot achievability result in terms
of $\mathbb{E}[G(X|P_{\hat{X}})^{\rho}]$ as follows.

###### Corollary 3

There exists a deterministic function
$\pi\colon\mathcal{X}\to\hat{\mathcal{X}}$ such that, for any positive integer
$\rho$, the tilted distribution $P_{\hat{X}_{\rho}^{*}}$ defined as (3)
satisfies

$\displaystyle\log\mathbb{E}[G_{\rho}(X|P_{\hat{X}_{\rho}^{*}})]\leq\rho
H_{\frac{1}{1+\rho}}^{\Delta}(X)+\log(\rho!).$

Let us compare our result with that of synchronous case. A synchronous
guessing strategy is determined by a bijection
$\mathcal{G}\colon\hat{\mathcal{X}}\to\\{1,2,\dots,|\hat{\mathcal{X}}|\\}$,
and the number of guesses when $X=x$ is given by

$G^{\textsf{sync}}(x|\mathcal{G})\triangleq\min_{\hat{x}\in\mathcal{A}_{\Delta}(x)}\mathcal{G}(\hat{x}).$

According to [8], the optimal $\rho$-th moment achievable by synchronous
strategies satisfies

$\displaystyle\rho
H_{\frac{1}{1+\rho}}^{\Delta}(X)-\rho\log\log(1+\min\\{|\mathcal{X}|,|\hat{\mathcal{X}}|\\})$
$\displaystyle\leq\log\min_{\mathcal{G}}\mathbb{E}[G^{\textsf{sync}}(X|\mathcal{G})^{\rho}]$
$\displaystyle\leq\rho H_{\frac{1}{1+\rho}}^{\Delta}(X).$ (4)

Comparing (4) with Corollary 3, we can see that the penalty of lack of
synchronization is upper bounded by

$\displaystyle\log(\rho!)+\rho\log\log(1+\min\\{|\mathcal{X}|,|\hat{\mathcal{X}}|\\}).$

###  III-B Asymptotics for Stationary Memoryless Sources

In this subsection, we apply our one-shot results to i.i.d. sources and
investigate the asymptotic behavior of the $\rho$-th moment of the number of
guesses.555To simplify the argument, we assume that $\rho$ is a positive
integer. However, it is not hard to show that our argument is valid for non-
integer $\rho>0$; See Appendix C.

Let $\mathcal{X}^{n}$ (resp. $\hat{\mathcal{X}}^{n}$) is the $n$-fold
Cartesian product of $\mathcal{X}$ (resp. $\hat{\mathcal{X}}$). The distortion
between $\bm{x}\in\mathcal{X}^{n}$ and $\hat{\bm{x}}\in\hat{\mathcal{X}}^{n}$
per symbol is defined by
$d_{n}(\bm{x},\hat{\bm{x}})=(1/n)\sum_{i=1}^{n}d(x_{i},\hat{x}_{i})$. We
investigate the problem of guessing the realization value $\bm{x}$ of
$X^{n}=(X_{1},X_{2},\dots,X_{n})$ subject to the distortion measure $d_{n}$,
where $X_{1},\dots,X_{n}$ are independently generated according to an
identical distribution $P_{X}$ on $\mathcal{X}$.

As in the one-shot case, an asynchronous guessing strategy is determined by a
distribution $P_{\hat{X}^{n}}$ on $\hat{\mathcal{X}}^{n}$. As a direct
consequence of Corollary 3, there exists a deterministic function
$\pi_{n}\colon\mathcal{X}^{n}\to\hat{\mathcal{X}}^{n}$ such that the strategy
$P_{\hat{X}_{\rho}^{*n}}$ induced by $\pi_{n}$ satisfies

$\displaystyle\frac{1}{n}\log\mathbb{E}[G_{\rho}(X^{n}|P_{\hat{X}_{\rho}^{*n}})]\leq\frac{1}{n}\rho
H_{\frac{1}{1+\rho}}^{\Delta}(X^{n})+\zeta_{n}$

where $\zeta_{n}\triangleq(\rho!)/n\to 0$ as $n\to\infty$. This fact indicates
that synchronization is not necessary to achieve the asymptotically optimal
guessing moment.

However, the strategy $P_{\hat{X}_{\rho}^{*n}}$ may be not feasible when $n$
is large. In particular, it may not be easy to find and implement the function
$\pi_{n}$. Hence, we restrict the class of guessing strategies.

###### Definition 2

An asynchronous guessing strategy $P_{\hat{X}^{n}}$ is said to be an _i.i.d.
asynchronous guessing strategy_ if there exists a distribution $Q_{\hat{X}}$
on $\hat{\mathcal{X}}$ satisfying

$\displaystyle
P_{\hat{X}^{n}}(\hat{\bm{x}})=Q_{\hat{X}}^{n}(\bm{x})\triangleq\prod_{i=1}^{n}Q_{\hat{X}}(\hat{x}_{i}),\quad\forall\hat{\bm{x}}\in\hat{\mathcal{X}}^{n}.$

In the following, we investigate the optimal guessing moment asymptotically
achievable by i.i.d. asynchronous guessing strategies. To state our result, we
introduce some notation. We use the following standard information-theoretic
quantities [17]. For a distribution $P$ and a conditional distribution $V$,
let $H(P)$ be the entropy of $P$, $H(V|P)=\sum_{x}P(x)H(V(\cdot|x))$ be the
conditional entropy, and $I(P,V)=H(PV)-H(V|P)$ be the mutual information,
where $PV$ is the distribution such that
$PV(\hat{x})=\sum_{x}P(x)V(\hat{x}|x)$. For two distributions $P$ and $Q$, let
$D(P\|Q)$ be the divergence between $P$ and $Q$. Let
$\overline{\mathcal{W}}_{\Delta}(Q_{X})$ be the set of conditional
distributions satisfying
$\sum_{x,\hat{x}}Q_{X}(x)V(\hat{x}|x)d(x,\hat{x})\leq\Delta$.

###### Definition 3

For distributions $Q_{X}$ on $\mathcal{X}$ and $Q_{\hat{X}}$ on
$\hat{\mathcal{X}}$,

$\displaystyle
R(Q_{X},Q_{\hat{X}}|\Delta)\triangleq\min_{V\in\overline{\mathcal{W}}_{\Delta}(Q_{X})}[I(Q_{X},V)+D(Q_{X}V\|Q_{\hat{X}})]$

where $Q_{X}V$ is the distribution such that
$Q_{X}V(\hat{x})=\sum_{x}Q_{X}(x)V(\hat{x}|x)$.

The next theorem, which is proved in Section IV-C, is our main result of this
subsection.

###### Theorem 3

For any i.i.d. asynchronous guessing strategy $Q_{\hat{X}}$ and positive
integer $\rho$,

$\displaystyle\lim_{n\to\infty}\frac{1}{n}\log\mathbb{E}[G_{\rho}(X^{n}|Q_{\hat{X}}^{n})]$
$\displaystyle=\max_{Q_{X}}\left[\rho
R(Q_{X},Q_{\hat{X}}|\Delta)-D(Q_{X}\|P_{X})\right]$

where the maximum is taken over all distributions $Q_{X}$ on $\mathcal{X}$.

As a consequence of the theorem, we obtain the following result on the optimal
$\rho$-th moment achievable by i.i.d. asynchronous guessing strategies.

###### Corollary 4

The exponent of the optimal $\rho$-th moment achievable by i.i.d. asynchronous
guessing strategies is

$\displaystyle
E_{\rho}^{\textsf{i.i.d}}(P_{X}|\Delta)\triangleq\min_{Q_{\hat{X}}}\max_{Q_{X}}\left[\rho
R(Q_{X},Q_{\hat{X}})-D(Q_{X}\|P_{X})\right]$

where $\min$ (resp. $\max$) is taken over all distributions $Q_{\hat{X}}$ on
$\hat{\mathcal{X}}$ (resp. $Q_{X}$ on $\mathcal{X}$).

###### Remark 1

The corollary guarantees that we can find the optimal i.i.d. strategy by
solving the minimization in the definition of
$E_{\rho}^{\textsf{i.i.d}}(P_{X}|\Delta)$, which does not depend on $n$. So,
our strategy is feasible even when $n$ is extremely large.

###### Remark 2

It should be emphasized that Theorem 3 holds for any strategy $Q_{\hat{X}}$.
In other words, $Q_{\hat{X}}$ is not necessarily depend on $P_{X}$. Hence, it
can be easily applied to guessing under source uncertainty. Assume that the
guesser does not know the source distribution $P_{X}$ but it knows the fact
that $P_{X}\in\mathcal{P}$ for a subset $\mathcal{P}$ of distributions.
Theorem 3 shows that, under this setting, the exponent of the optimal
$\rho$-th guessing moment asymptotically achievable by i.i.d. strategies is

$\displaystyle\min_{Q_{\hat{X}}}\max_{P_{X}\in\mathcal{P}}\max_{Q_{X}}\left[\rho
R(Q_{X},Q_{\hat{X}})-D(Q_{X}\|P_{X})\right].$

Lastly, we investigate the penalty of restricting strategies to be i.i.d.

Let us define

$\displaystyle E_{\rho}(P_{X}|\Delta)\triangleq\max_{Q_{X}}\left\\{\rho
R(Q_{X}|\Delta)-D(Q_{X}\|P_{X})\right\\}$

where the maximum is taken over all distributions $Q_{X}$ on $\mathcal{X}$ and
$R(Q_{X}|\Delta)$ is the _rate-distortion function_ ; i.e.,

$\displaystyle
R(Q_{X}|\Delta)\triangleq\min_{V\in\overline{\mathcal{W}}_{\Delta}(Q_{X})}I(Q_{X},V).$

It is known that $E_{\rho}(P_{X}|\Delta)$ is the exponent of the optimal
$\rho$-th guessing moment asymptotically achievable by synchronous strategies
[3]; i.e.,

$\displaystyle E_{\rho}(P_{X}|\Delta)$
$\displaystyle=\lim_{n\to\infty}\frac{1}{n}\log\min_{\mathcal{G}_{n}\text{ on
}\hat{\mathcal{X}}^{n}}\mathbb{E}[G^{\textsf{sync}}(X^{n}|\mathcal{G}_{n})^{\rho}].$

Further, results of [8] implies that

$\displaystyle E_{\rho}(P_{X}|\Delta)$
$\displaystyle=\lim_{n\to\infty}\frac{\rho}{n}H_{\frac{1}{1+\rho}}^{\Delta}(X^{n}).$

On the other hand, since

$\displaystyle\min_{Q_{\hat{X}}}R(Q_{X},Q_{\hat{X}}|\Delta)=R(Q_{X}|\Delta),$

we have

$\displaystyle E_{\rho}^{\textsf{i.i.d}}(P_{X}|\Delta)$
$\displaystyle=\min_{Q_{\hat{X}}}\max_{Q_{X}}\left[\rho
R(Q_{X},Q_{\hat{X}}|\Delta)-D(Q_{X}\|P_{X})\right]$
$\displaystyle\geq\max_{Q_{X}}\min_{Q_{\hat{X}}}\left[\rho
R(Q_{X},Q_{\hat{X}}|\Delta)-D(Q_{X}\|P_{X})\right]$
$\displaystyle=E_{\rho}(P_{X}|\Delta).$

From this, we can see the suboptimality of i.i.d. strategies and evaluate the
penalty as

$\displaystyle\min_{Q_{\hat{X}}}\max_{Q_{X}}\left[\rho
R(Q_{X},Q_{\hat{X}}|\Delta)-D(Q_{X}\|P_{X})\right]$
$\displaystyle-\max_{Q_{X}}\min_{Q_{\hat{X}}}\left[\rho
R(Q_{X},Q_{\hat{X}}|\Delta)-D(Q_{X}\|P_{X})\right].$

##  IV Proofs

###  IV-A Proof of Theorem 1

Let $\pi$ be the function given in Proposition 1 and let $\hat{X}=\pi(X)$.
Since $\pi(x)\in\mathcal{A}_{\Delta}(x)$, we have
$P_{\hat{X}_{\rho}^{*}}(\mathcal{A}_{\Delta}(x))\geq
P_{\hat{X}_{\rho}^{*}}(\pi(x))$. Hence, letting
$\pi^{-1}(\hat{x})\triangleq\\{x\in\mathcal{X}:\pi(x)=\hat{x}\\}$, we have

$\displaystyle\mathbb{E}[V_{\rho}(X|P_{\hat{X}_{\rho}^{*}})]$
$\displaystyle=\sum_{x\in\mathcal{X}}P_{X}(x)\left(\frac{1}{P_{\hat{X}_{\rho}^{*}}(\mathcal{A}_{\Delta}(x))}\right)^{\rho}$
$\displaystyle\leq\sum_{x\in\mathcal{X}}P_{X}(x)\left(\frac{1}{P_{\hat{X}_{\rho}^{*}}(\pi(x))}\right)^{\rho}$
$\displaystyle=\sum_{\hat{x}\in\hat{\mathcal{X}}}\sum_{x\in\pi^{-1}(\hat{x})}P_{X}(x)\left(\frac{1}{P_{\hat{X}_{\rho}^{*}}(\hat{x})}\right)^{\rho}$
$\displaystyle=\sum_{\hat{x}\in\hat{\mathcal{X}}}P_{\hat{X}}(\hat{x})\left(\frac{1}{P_{\hat{X}_{\rho}^{*}}(\hat{x})}\right)^{\rho}$
$\displaystyle=\exp\left[\rho H_{\frac{1}{1+\rho}}(\hat{X})\right]$
$\displaystyle=\exp\left[\rho H_{\frac{1}{1+\rho}}^{\Delta}(X)\right]$

where the last equality follows from (2). ∎

###  IV-B Proof of Theorem 2

Since $\rho>1$, using Jensen’s inequality, we have

$\displaystyle G_{\rho}(x|P_{\hat{X}})$
$\displaystyle=\sum_{k=1}^{\infty}\Pr\\{G(x|P_{\hat{X}})=k\\}k^{\rho}$
$\displaystyle\geq\left\\{\sum_{k=1}^{\infty}\Pr\\{G(x|P_{\hat{X}})=k\\}k\right\\}^{\rho}$
$\displaystyle=\\{1/P_{\hat{X}}(\mathcal{A}_{\Delta}(x))\\}^{\rho}$ (5)

where the last equality follows from the fact that the distribution of
$G(x|P_{\hat{X}})$ is the geometric distribution with the parameter
$P_{\hat{X}}(\mathcal{A}_{\Delta}(x))$.

On the other hand, since $G(x|P_{\hat{X}})$ is an integer-valued random
variable and $\rho$ is an integer,

$\displaystyle\frac{G(x|P_{\hat{X}})^{\rho}}{\rho!}$
$\displaystyle\leq\frac{1}{\rho!}G(x|P_{\hat{X}})\times[G(x|P_{\hat{X}})+1]$
$\displaystyle\quad\times[G(x|P_{\hat{X}})+2]\times\dots\times[G(x|P_{\hat{X}})+\rho-1]$
$\displaystyle=\binom{G(x|P_{\hat{X}})+\rho-1}{\rho}.$

Taking the expectation with respect to $G(x|P_{\hat{X}})$ and multiply both
sides by $\rho!$, we have

$\displaystyle G_{\rho}(x|P_{\hat{X}})\leq(\rho!)V_{\rho}(x|P_{\hat{X}}).$ (6)

Combining (5) and (6) with Proposition 2, we have the theorem. ∎

###  IV-C Proof of Theorem 3

Before giving the proof, we introduce some notation.

For two positive sequences $a_{n}$ and $b_{n}$, we will write $a_{n}\doteq
b_{n}$ if $\lim_{n\to\infty}(1/n)\log(a_{n}/b_{n})=0$. Similarly, when $a_{n}$
and $b_{n}$ depend on a sequence $\bm{x}$, the notation $a_{n}(\bm{x})\doteq
b_{n}(\bm{x})$ means that

$\displaystyle\lim_{n\to\infty}\max_{\bm{x}\in\mathcal{X}^{n}}\left|\frac{1}{n}\log\frac{a_{n}(\bm{x})}{b_{n}(\bm{x})}\right|=0.$

In our proof, we use the _method of types_ [17]. For
$\bm{x}\in\mathcal{X}^{n}$, the _type_ $P_{\bm{x}}$ is the empirical
distribution of $\bm{x}=(x_{1},\dots,x_{n})$; i.e.,
$P_{\bm{x}}(a)=(1/n)|\\{1\leq i\leq n:x_{i}=a\\}|$ for all $a\in\mathcal{X}$.
Let $\mathcal{P}_{n}$ be the possible types of length $n$ sequences. For
$Q\in\mathcal{P}_{n}$, $\mathcal{T}_{Q}$ is the set of sequences $\bm{x}$ such
that $P_{\bm{x}}=Q$. For a conditional distribution
$V\colon\mathcal{X}\to\hat{\mathcal{X}}$ and $\bm{x}\in\mathcal{X}^{n}$,
$\mathcal{T}_{V}(\bm{x})$ denotes the set of sequences
$\hat{\bm{x}}=(\hat{x}_{1},\dots,\hat{x}_{n})\in\hat{\mathcal{X}}^{n}$
satisfying $V(b|a)=|\\{j:(x_{j},\hat{x}_{j})=(a,b)\\}|/|\\{i:x_{i}=a\\}|$ for
all $(a,b)\in\mathcal{X}\times\hat{\mathcal{X}}$.

###### Proof:

From Corollary 2, we have

$\displaystyle\mathbb{E}[G_{\rho}(X^{n}|Q_{\hat{X}}^{n})]\doteq\sum_{\bm{x}\in\mathcal{X}^{n}}P_{X^{n}}(\bm{x})[Q_{\hat{X}}^{n}(\mathcal{A}_{\Delta}(\bm{x}))]^{-\rho}$
(7)

where
$\mathcal{A}_{\Delta}(\bm{x})\triangleq\\{\hat{\bm{x}}\in\hat{\mathcal{X}}^{n}:d_{n}(\bm{x},\hat{\bm{x}})\leq\Delta\\}$.
So, we evaluate the exponent of the right-hand side of (7).

For any $\hat{\bm{x}}$ and $V$, we have

$\displaystyle Q_{\hat{X}}^{n}(\hat{\bm{x}})$
$\displaystyle=\exp\left\\{-n[H(P_{\hat{\bm{x}}})+D(P_{\hat{\bm{x}}}\|Q_{\hat{X}})]\right\\},$
$\displaystyle|\mathcal{T}_{V}(\bm{x})|$
$\displaystyle\doteq\exp\\{nH(V|P_{\bm{x}})\\}$

and thus,

$\displaystyle
Q_{\hat{X}}^{n}(\mathcal{T}_{V}(\bm{x}))\doteq\exp\left\\{-n[I(P_{\bm{x}},V)+D(P_{\bm{x}}V\|Q_{\hat{X}})]\right\\}$

where $P_{\bm{x}}V$ is the distribution on $\hat{\mathcal{X}}$ such that
$P_{\bm{x}}V(\hat{x})=\sum_{x}P_{\bm{x}}(x)V(\hat{x}|x)$.

Further, $\mathcal{A}_{\Delta}(\bm{x})$ can be written as

$\displaystyle\mathcal{A}_{\Delta}(\bm{x})=\bigcup_{\begin{subarray}{c}V:\\\
\sum_{x,\hat{x}}P_{\bm{x}}(x)V(\hat{x}|x)d(x,\hat{x})\leq\Delta\end{subarray}}\mathcal{T}_{V}(\bm{x}).$

Hence, we have

$\displaystyle Q_{\hat{X}}^{n}(\mathcal{A}_{\Delta}(\bm{x}))$
$\displaystyle\doteq\exp\left\\{-n\min_{V}[I(P_{\bm{x}},V)+D(P_{\bm{x}}V\|Q_{\hat{X}})]\right\\}$
$\displaystyle=\exp\left\\{-nR(P_{\bm{x}},Q_{\hat{X}}|\Delta)\right\\}.$ (8)

On the other hand, we have

$P_{X}(\mathcal{T}_{Q_{X}})\doteq\exp\\{-nD(Q_{X}\|P_{X})\\}$

for all $Q_{X}\in\mathcal{P}_{n}$. Combining this with (8), we have

$\displaystyle\sum_{\bm{x}\in\mathcal{X}^{n}}P_{X^{n}}(\bm{x})[Q_{\hat{X}}^{n}(\mathcal{A}_{\Delta}(\bm{x}))]^{-\rho}$
$\displaystyle=\sum_{Q_{X}\in\mathcal{P}_{n}}\sum_{\bm{x}\in\mathcal{T}_{Q_{X}}}P_{X^{n}}(\bm{x})[Q_{\hat{X}}^{n}(\mathcal{A}_{\Delta}(\bm{x}))]^{-\rho}$
$\displaystyle\doteq\sum_{Q_{X}\in\mathcal{P}_{n}}\exp\left\\{n\left[\rho
R(Q_{X},Q_{\hat{X}}|\Delta)-D(Q_{X}\|P_{X})\right]\right\\}$
$\displaystyle\doteq\exp\left\\{n\max_{Q_{X}}\left[\rho
R(Q_{X},Q_{\hat{X}}|\Delta)-D(Q_{X}\|P_{X})\right]\right\\}.$

∎

##  V Concluding Remarks

In this paper, randomized strategies for guessing subject to distortion was
studied. A one-shot achievability bound on the guessing moment was given.
Further, feasible i.i.d. asynchronous guessing scheme was proposed, and its
asymptotic performance was investigated.

Lastly, we give some comments regarding generalizations of our results.

  * •

It is not hard to extend the result to the case where side-information is
available at the guesser.

  * •

Our result shows that the behavior of

$-\frac{1}{n}\log Q_{\hat{X}}^{n}(\mathcal{A}_{\Delta}(\bm{x}))\simeq
R(P_{\bm{x}},Q_{\hat{X}}|\Delta)$

determines the guessing moment (See (8) and (7) in the proof of Theorem 3).
Since the behavior of $(-1/n)\log
Q_{\hat{X}}^{n}(\mathcal{A}_{\Delta}(\bm{x}))$ for sources with memory is well
studied in the context of the rate-distortion theory (see [18] and references
there in), we can apply those results. For example, our argument can also be
applied to stationary ergodic sources by using Theorem 3 of [19].

##  Appendix A Proof of Proposition 1

First we introduce the concept of majorization and Schur concavity, which play
important role in the proof.

Let $\mathbb{R}_{+}^{m}$ be the set of vectors with $m$ nonnegative
components. Given $\mathbf{p}=(p_{1},p_{2},\dots,p_{m})\in\mathbb{R}_{+}^{m}$,
denote by $p_{[1]}\geq p_{[2]}\geq\dots\geq p_{[m]}$ the permutation of the
components of $\mathbf{p}$ in the nonincreasing order.

###### Definition 4

We say that $\mathbf{q}\in\mathbb{R}_{+}^{m}$ majorizes
$\mathbf{p}\in\mathbb{R}_{+}^{m}$ (and write $\mathbf{p}\prec\mathbf{q}$) if

$\displaystyle\sum_{i=1}^{j}p_{[i]}\leq\sum_{i=1}^{j}q_{[i]},\quad\forall
j=1,2,\dots,m-1$

and

$\displaystyle\sum_{i=1}^{m}p_{[i]}\leq\sum_{i=1}^{m}q_{[i]}.$ (9)

###### Definition 5

A real valued function $h$ on $\mathbb{R}_{+}^{m}$ is said to be _Schur
concave_ if $h(\mathbf{p})\geq h(\mathbf{q})$ for any
$\mathbf{p},\mathbf{q}\in\mathbb{R}_{+}^{m}$ satisfying
$\mathbf{p}\prec\mathbf{q}$.

It is well known that $\phi(\mathbf{p})=\sum_{i=1}^{m}(h_{i})^{\alpha}$ for
$\alpha\in(0,1)$ is Schur concave; See, e.g. [20]. Thus, we can easily see
that the Rényi entropy of order $\alpha\in(0,1)$ is also Schur concave. Hence,
to prove Proposition 1, it is sufficient to prove the following lemma.
Although the same argument is given in the last page of [21], we give a proof
for the completeness.

###### Lemma 1

There exists a deterministic function
$\pi\colon\mathcal{X}\to\hat{\mathcal{X}}$ such that (i)
$d(x,\pi(x))\leq\Delta(x)$ for all $x\in\mathcal{X}$ and (ii) the distribution
$P_{\hat{X}}$ of $\hat{X}=\pi(X)$ majorizes any $P_{\tilde{X}}$ induced by
$P_{\tilde{X}|X}\in\mathcal{W}_{\Delta}$.

###### Proof:

Let $m\triangleq|\mathcal{X}|$ in this proof. For each
$\hat{x}\in\mathcal{X}$, let

$\displaystyle\mathcal{B}_{\Delta}(\hat{x})\triangleq\\{x\in\mathcal{X}:d(x,\hat{x})\leq\Delta\\}.$

We define the order $\hat{x}_{1},\hat{x}_{2},\dots,\hat{x}_{m}$ of symbols in
$\hat{\mathcal{X}}$ as follows. Let $\hat{x}_{1}$ be a symbol satisfying

$\displaystyle\Pr\\{X\in\mathcal{B}_{\Delta}(\hat{x}_{1})\\}=\max_{\hat{x}\in\hat{\mathcal{X}}}\Pr\\{X\in\mathcal{B}_{\Delta}(\hat{x})\\}.$

Then, for $i=2,3,\dots,m$, let
$\hat{x}_{i}\in\hat{\mathcal{X}}\setminus\\{\hat{x}_{1},\dots,\hat{x}_{i-1}\\}$
be a symbol such that

$\displaystyle\Pr\left\\{X\in\mathcal{B}_{\Delta}(\hat{x}_{i})\setminus\bigcup_{j=1}^{i-1}\mathcal{B}_{\Delta}(\hat{x}_{j})\right\\}$
$\displaystyle=\max_{\hat{x}\in\hat{\mathcal{X}}}\Pr\left\\{X\in\mathcal{B}_{\Delta}(\hat{x})\setminus\bigcup_{j=1}^{i-1}\mathcal{B}_{\Delta}(\hat{x}_{j})\right\\}.$

Let
$\mathcal{X}_{i}\triangleq\mathcal{B}_{\Delta}(\hat{x}_{i})\setminus\bigcup_{j=1}^{i-1}\mathcal{B}_{\Delta}(\hat{x}_{j})$
($i=1,\dots,m$). Then $\mathcal{X}_{1},\dots,\mathcal{X}_{m}$ give a partition
of $\mathcal{X}$, and thus, we can define
$\pi\colon\mathcal{X}\to\hat{\mathcal{X}}$ so that $\pi(x)=\hat{x}_{i}$ if
$x\in\mathcal{X}_{i}$. It is apparent that $d(x,\pi(x))\leq\Delta$ for all
$x\in\mathcal{X}$. Further, from the construction, the distribution
$P_{\hat{X}}$ of $\hat{X}=\pi(X)$ satisfies

$\displaystyle P_{\hat{X}}(\hat{x}_{1})\geq
P_{\hat{X}}(\hat{x}_{2})\geq\dots\geq P_{\hat{X}}(\hat{x}_{m}).$

We will prove that $\pi$ satisfies (ii) by contradiction. Assume that there
exists $P_{\tilde{X}|X}\in\mathcal{W}_{\Delta}$ such that $P_{\tilde{X}}$
induced by $P_{\tilde{X}|X}$ is _not_ majorized by $P_{\hat{X}}$. Let us
define another order $\tilde{x}_{1},\tilde{x}_{2},\dots,\tilde{x}_{m}$ in
$\hat{\mathcal{X}}$ so that

$\displaystyle P_{\tilde{X}}(\tilde{x}_{1})\geq
P_{\tilde{X}}(\tilde{x}_{2})\geq\dots\geq P_{\tilde{X}}(\tilde{x}_{m}).$

Since $P_{\tilde{X}}\not\prec P_{\hat{X}}$, there exists $k$ such that

$\displaystyle\sum_{i=1}^{k}P_{\tilde{X}}(\tilde{x}_{i})>\sum_{i=1}^{k}P_{\hat{X}}(\hat{x}_{i}).$

Hence, we have

$\displaystyle\Pr\\{d(X,\tilde{X})>\Delta\\}$
$\displaystyle\geq\sum_{x\in\mathcal{X}}\sum_{i=1}^{k}P_{X}(x)P_{\tilde{X}|X}(\tilde{x}_{i}|x)\bm{1}[d(x,\tilde{x}_{i})>\Delta]$
$\displaystyle=\sum_{i=1}^{k}P_{\tilde{X}}(\tilde{x}_{i})$
$\displaystyle\quad-\sum_{x\in\mathcal{X}}P_{X}(x)\sum_{i=1}^{k}P_{\tilde{X}|X}(\tilde{x}_{i}|x)\bm{1}[x\in\mathcal{B}_{\Delta}(\tilde{x}_{i})]$
$\displaystyle\stackrel{{\scriptstyle\text{(a)}}}{{\geq}}\sum_{i=1}^{k}P_{\tilde{X}}(\tilde{x}_{i})-\Pr\left\\{X\in\bigcup_{i=1}^{k}\mathcal{B}_{\Delta}(\tilde{x}_{i})\right\\}$
$\displaystyle\stackrel{{\scriptstyle\text{(b)}}}{{\geq}}\sum_{i=1}^{k}P_{\tilde{X}}(\tilde{x}_{i})-\Pr\left\\{X\in\bigcup_{i=1}^{k}\mathcal{B}_{\Delta}(\hat{x}_{i})\right\\}$
$\displaystyle=\sum_{i=1}^{k}P_{\tilde{X}}(\tilde{x}_{i})-\sum_{i=1}^{k}\Pr\left\\{X\in\mathcal{X}_{i}\right\\}$
$\displaystyle=\sum_{i=1}^{k}P_{\tilde{X}}(\tilde{x}_{i})-\sum_{i=1}^{k}P_{\hat{X}}(\hat{x}_{i})$
$\displaystyle>0,$

where $\bm{1}$ denotes the indicator function, (a) follows from
$\sum_{i=1}^{k}P_{\tilde{X}|X}(\tilde{x}_{i}|x)\bm{1}[x\in\mathcal{B}_{\Delta}(\tilde{x}_{i})]\leq\bm{1}[x\in\bigcup_{i=1}^{k}\mathcal{B}_{\Delta}(\tilde{x}_{i})]$
for all $x\in\mathcal{X}$, and (b) follows from the definition of the order
$\hat{x}_{1},\hat{x}_{2},\dots,\hat{x}_{m}$. This contradicts the fact
$P_{\tilde{X}|X}\in\mathcal{W}_{\Delta}$. ∎

##  Appendix B Proof of Proposition 2

The proposition can be proved in the same manner as [4, Lemma 2]. We give a
proof for the completeness.

###### Proof:

Letting $p_{x}\triangleq P_{\hat{X}}(\mathcal{A}_{\Delta}(x))$, we have

$\displaystyle V_{\rho}(x|P_{\hat{X}})$
$\displaystyle=\sum_{m=1}^{\infty}\binom{m+\rho-1}{\rho}\Pr\\{G(x|P_{\hat{X}})=m\\}$
$\displaystyle=p_{x}\sum_{m=1}^{\infty}\binom{m+\rho-1}{\rho}(1-p_{x})^{m-1}$
$\displaystyle\stackrel{{\scriptstyle\text{(a)}}}{{=}}p_{x}\sum_{m=1}^{\infty}\binom{-\rho-1}{m-1}[-(1-p_{x})]^{m-1}$
$\displaystyle=p_{x}\sum_{k=0}^{\infty}\binom{-\rho-1}{k}[-(1-p_{x})]^{k}$
$\displaystyle\stackrel{{\scriptstyle\text{(b)}}}{{=}}p_{x}[1-(1-p_{x})]^{-\rho-1}$
$\displaystyle=(p_{x})^{-\rho}$

where (a) follows from the relationship

$\displaystyle\binom{m+\rho-1}{\rho}=(-1)^{m-1}\binom{-\rho-1}{m-1},$

which is proved in the proof of Lemma 2 in [4], and (b) follows from the
binominal formula. ∎

##  Appendix C Asymptotics for non-integer $\rho$

We show that Theorem 3 also holds for non-integer $\rho>0$. From (8), for all
$\bm{x}\in\mathcal{X}^{n}$ and $Q_{\hat{X}}$,

$\displaystyle q_{\bm{x}}\triangleq
Q_{\hat{X}}^{n}(\mathcal{A}_{\Delta}(\bm{x}))\doteq\exp\left\\{-nR(P_{\bm{x}},Q_{\hat{X}}|\Delta)\right\\}.$

Assume that $R(P_{\bm{x}},Q_{\hat{X}}|\Delta)>0$. Then, since $q_{\bm{x}}<1/2$
for large $n$, (20) of [15] gives

$\displaystyle G_{\rho}(\bm{x}|Q_{\hat{X}}^{n})$
$\displaystyle=\sum_{k=1}^{\infty}k^{\rho}(1-q_{\bm{x}})^{k-1}q_{\bm{x}}$
$\displaystyle\geq\left(\frac{1-q_{\bm{x}}}{q_{\bm{x}}}\right)^{\rho}\exp\left\\{-\frac{1}{1-q_{\bm{x}}}\right\\}$
$\displaystyle\geq\frac{2^{-\rho}}{\mathrm{e}^{2}}q_{\bm{x}}^{-\rho}.$

Thus, we have

$\displaystyle\liminf_{n\to\infty}\frac{1}{n}\log\left|\frac{G_{\rho}(\bm{x}|Q_{\hat{X}}^{n})}{\exp\\{\rho
nR(P_{\bm{x}},Q_{\hat{X}}|\Delta)\\}}\right|\geq 0.$ (10)

On the other hand, by using Lemma 1 of [13] with
$a=R(P_{\bm{x}},Q_{\hat{X}}|\Delta)$, we can show that

$\displaystyle\limsup_{n\to\infty}\frac{1}{n}\log\left|\frac{G_{\rho}(\bm{x}|Q_{\hat{X}}^{n})}{\exp\\{\rho
nR(P_{\bm{x}},Q_{\hat{X}}|\Delta)\\}}\right|\leq 0.$ (11)

Combining (10) and (11), we have

$\displaystyle G_{\rho}(\bm{x}|Q_{\hat{X}}^{n})\doteq\exp\left\\{\rho
nR(P_{\bm{x}},Q_{\hat{X}}|\Delta)\right\\}$

and thus,

$\displaystyle\sum_{\bm{x}\in\mathcal{X}^{n}}P_{X^{n}}(\bm{x})G_{\rho}(\bm{x}|Q_{\hat{X}}^{n})$
$\displaystyle\doteq\sum_{Q_{X}\in\mathcal{P}_{n}}\exp\left\\{n\left[\rho
R(Q_{X},Q_{\hat{X}}|\Delta)-D(Q_{X}\|P_{X})\right]\right\\}$
$\displaystyle\doteq\exp\left\\{n\max_{Q_{X}}\left[\rho
R(Q_{X},Q_{\hat{X}}|\Delta)-D(Q_{X}\|P_{X})\right]\right\\}.$

## Acknowledgment

This work was supported in part by JSPS KAKENHI Grant Number 18K04141.

## References

  * [1] J. L. Massey, “Guessing and entropy,” in _Proc. 1994 IEEE Int. Symp. on Information Theory_ , p. 204.
  * [2] E. Arikan, “An inequality on guessing and its application to sequential decoding,” _IEEE Trans. Inf. Theory_ , vol. 42, no. 1, pp. 99–105, 1996\.
  * [3] E. Arikan and N. Merhav, “Guessing subject to distortion,” _IEEE Trans. Inf. Theory_ , vol. 44, no. 3, pp. 1041–1056, 1998.
  * [4] S. Salamatian, W. Huleihel, A. Beirami, A. Cohen, and M. Médard, “Why botnets work: Distributed brute-force attacks need no synchronization,” _IEEE Transactions on Information Forensics and Security_ , vol. 14, no. 9, pp. 2288–2299, 2019.
  * [5] A. Rényi, “On measures of entropy and information,” in _Proc. 4th Berkeley Symp. on Math. Stat. and Prob._ , 1961, pp. 547–561.
  * [6] I. Sason and S. Verdú, “Improved bounds on lossless source coding and guessing moments via Rényi measures,” _IEEE Trans. Inf. Theory_ , vol. 64, no. 6, pp. 4323–4346, 2018.
  * [7] S. Kuzuoka, “On the conditional smooth rényi entropy and its applications in guessing and source coding,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 3, pp. 1674–1690, 2020.
  * [8] S. Saito and T. Matsushima, “Non-asymptotic fundamental limits of guessing subject to distortion,” in _2019 IEEE International Symposium on Information Theory (ISIT)_ , 2019, pp. 652–656.
  * [9] M. K. Hanawal and R. Sundaresan, “Guessing revisited: A large deviations approach,” _IEEE Trans. Inf. Theory_ , vol. 57, no. 1, pp. 70–78, 2011.
  * [10] M. M. Christiansen and K. R. Duffy, “Guesswork, large deviations, and Shannon entropy,” _IEEE Trans. Inf. Theory_ , vol. 59, no. 2, pp. 796–802, 2013.
  * [11] M. M. Christiansen, K. R. Duffy, F. du Pin Calmon, and M. Médard, “Multi-user guesswork and brute force security,” _IEEE Trans. Inf. Theory_ , vol. 61, no. 12, pp. 6876–6886, 2015.
  * [12] A. Bracher, A. Lapidoth, and C. Pfister, “Guessing with distributed encoders,” _Entropy_ , vol. 21, no. 3, 2019.
  * [13] N. Merhav and A. Cohen, “Universal randomized guessing with application to asynchronous decentralized brute-force attacks,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 1, pp. 114–129, 2020.
  * [14] J. Ziv and A. Lempel, “Compression of individual sequences via variable-rate coding,” _IEEE Trans. Inf. Theory_ , vol. IT-24, no. 5, pp. 530–536, Sep. 1978.
  * [15] N. Merhav, “Guessing individual sequences: Generating randomized guesses using finite-state machines,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 5, pp. 2912–2920, 2020.
  * [16] N. Merhav and I. Sason, “Some useful integral representations for information-theoretic analyses,” _Entropy_ , vol. 22, no. 6, 2020.
  * [17] I. Csiszár and J. Körner, _Information Theory: Coding Theorems for Discrete Memoryless Systems_ , 2nd ed. Cambridge University Press, 2011.
  * [18] A. Dembo and I. Kontoyiannis, “Source coding, large deviations, and approximate pattern matching,” _IEEE Trans. Inf. Theory_ , vol. 48, no. 6, pp. 1590–1615, 2002.
  * [19] E. Yang and Z. Zhang, “On the redundancy of lossy source coding with abstract alphabets,” _IEEE Trans. Inf. Theory_ , vol. 45, no. 4, pp. 1092–1110, 1999\.
  * [20] A. W. Marshall, I. Olkin, and B. C. Arnold, _Inequalities: Theory of Majorization and Its Applications_ , 2nd ed. Springer, 2010.
  * [21] S. Saito, H. Yagi, and T. Matsushima, “Variable-length lossy compression allowing positive overflow and excess distortion probabilities,” in _2017 IEEE International Symposium on Information Theory (ISIT)_ , 2017, pp. 1568–1572.