text:
\section{Introduction}
\let\thefootnote\relax\footnote{
F.d.P.C. sponsored by the Department of Defense under Air
Force Contract FA8721-05-C-0002. Opinions, interpretations,
recommendations, and conclusions are those of the authors and are
not necessarily endorsed by the United States Government. Specifically,
this work was supported by Information Systems of ASD(R\&E). M.M.
and K.D. were supported in part by a Netapp faculty fellowship.}

The security of systems is often predicated on a user or application
selecting an object, a password or key, from a large list. If an
inquisitor who wishes to identify the object in order to gain access
to a system can only query each possibility, one at a time, then
the number of guesses they must make in order to identify the
selected object is likely to be large. If the object is selected
uniformly at random using, for example, a cryptographically secure
pseudo-random number generator, then the analysis of the distribution
of the number of guesses that the inquisitor must make is trivial.

Since the earliest days of code-breaking, deviations from perfect
uniformity have been exploited. For example, it has long since been
known that human-user selected passwords are highly non-uniformly
selected, e.g. \cite{malone12}, and this forms the basis of dictionary
attacks. In information theoretic security, uniformity of the string
source is typically assumed on the basis that the source has been
compressed. Recent work has cast some doubt on the appropriateness
of that assumption by establishing that fewer queries are required
to identify strings chosen from a typical set than one would
expect by a na\"ive application of the asymptotic equipartition
property. This arises by exploitation of the mild non-uniformity
of the distribution of strings conditioned to be in the typical set
\cite{Christiansen13a}.

If the string has not been selected perfectly uniformly, but with
a distribution that is known to the inquisitor, then the quantification
of security is relatively involved. Assume that a string, $W_1$,
is selected stochastically from a finite list, $ {\mathbb{A} } = \{0,\ldots,m-1\}$.
An inquisitor who knows the selection probabilities, ${P}(W_1=w)$
for all $w\in {\mathbb{A} }$, is equipped with a method to test one string
at a time and develops a strategy,
$G: {\mathbb{A} }\mapsto\{1,\ldots,m\}$,
that defines the order in which strings are guessed. As the string
is stochastically selected, the number of queries,
$G(W_1)$,
that must be made before it is identified correctly is also
a random variable, dubbed guesswork. Analysis of the distribution
of guesswork serves as a natural a measure of computational security
in brute force determination.

In a brief paper in 1994, Massey \cite{Massey94} established that
if the inquisitor orders his guesses from most likely to least
likely, then the Shannon entropy of the random variable $W_1$ bears
little relation to
the expected guesswork
$E(G(W_1))= \sum_{w\in {\mathbb{A} }} G(w) P(W_1=w)$,
the average number of guesses required to identify
$W_1$.
Arikan \cite{Arikan96} established
that if a string, $W_k$, is chosen from $ {\mathbb{A} }^k$ with i.i.d. characters,
again guessing strings from most likely to least likely, then the
moments of the guesswork distribution grow exponentially in $k$
with a rate identified in terms of the R\'enyi entropy of the
characters,
\begin{align*}
\lim_{k\to\infty} \frac 1k \log E(G(W_k)^\alpha)
	&= (1+\alpha) \log \sum_{w\in {\mathbb{A} }} P(W_1=w)^{1/(1+\alpha)}\\
	&= \alpha R\left(\frac{1}{1+\alpha}\right)
	\text{ for } \alpha>0,
\end{align*}
where $R((1+\alpha)^{-1})$ is the R\'enyi entropy of $W_1$ with
parameter $(1+\alpha)^{-1}$.
In particular, the average guesswork grows as the R\'enyi entropy
with parameter $1/2$, a value that is
lower bounded by Shannon entropy.

Arikan's result was subsequently extended significantly beyond
i.i.d. sources \cite{Malone042,Pfister04,Hanawal11}, establishing
its robustness. In the generalized setting, specific R\'enyi entropy,
the R\'enyi entropy per character, plays the r\^ole of R\'enyi
entropy. In turn, these results have been leveraged to prove that
the guesswork process $\{k^{-1}\log G(W_k)\}$
satisfies a Large Deviation Principle (LDP),
e.g. \cite{Lewis95,Dembo98},
in broad
generality \cite{Christiansen13}.
That is, there exists a lower semi-continuous function
$I:[0,\log(m)]\mapsto[0,\infty]$ such that for all
Borel sets $B$ contained in $[0,\log(m)]$
\begin{align}
-\inf_{x\in B^\circ} I(x) &\leq
        \liminf_{n\to\infty} \frac 1k \log
	P\left(\frac 1k \log G(W_k) \in B\right) \nonumber\\
&\leq
\limsup_{n\to\infty} \frac 1k \log
	P\left(\frac 1k \log G(W_k) \in B\right) \nonumber\\
        &\leq -\inf_{x\in \bar{B}} I(x),
	\label{eq:LDP}
\end{align}
where $B^\circ$ denotes the interior of $B$ and $\bar{B}$ denotes
its closure. Roughly speaking, this implies $dP(k^{-1} \log G(W_k)
\approx x)\approx \exp(-k I(x)) dx$ for large $k$. In \cite{Christiansen13}
this LDP, in turn, was used to provide direct estimates on the
guesswork probability mass function, $P(G(W_k)=n)$ for
$n\in\{1,\ldots,m^k\}$.  These deductions, along with others described
in Section \ref{sec:brief}, have developed a quantitative framework
for the process of brute force guessing a single string.

In the present work we address a natural extension in this investigation
of brute force searching: the quantification for multi-user systems.
We are motivated by both classical systems, such as the brute force
entry to a multi-user computer where the inquisitor need only
compromise a single account, as well as modern distributed storage
services where coded data is kept at distinct sites in a way where,
owing to coding redundancy, several, but not all, servers need to be
compromised to access the content \cite{oliveira12,Calmon12}.

\section{Summary of contribution}

Assume that $V$ users select strings independently from $ {\mathbb{A} }^k$. An
inquisitor knows the probabilities with which each user selects
their string, is able to query the correctness of
each
(user, string)
pair, and wishes to identify any
subset of size
$U$ of the $V$ strings. The first
question that must be addressed is what is the optimal strategy, the
ordering in which (user, string) pairs are guessed, for
the inquisitor. For the single user system, since the earliest
investigations \cite{Massey94,Arikan96,Merhav99,Pliam00} it has
been clear that the strategy of ordering guesses from
the
most to least likely string, breaking ties arbitrarily, is optimal
in any reasonable sense. Here we shall give optimality a specific
meaning: that the distribution of the number of guesses required
to identify the unknown object is stochastically dominated by all
other strategies. Amongst other results, for the multi-user guesswork
problem we establish the following:

\begin{itemize}
\item If $U<V$, the existence of optimal guessing strategies,
those that are stochastically dominated by all other strategies, is
no longer assured.
\item By construction, there exist asymptotically optimal strategies
as the strings become long.
\item For asymptotically optimal strategies, we prove a large
deviation principle for their guesswork. The resulting large deviations
rate function is, in general, not convex and so this result could
not have been established by determining how the moment generating
function of the multi-user guesswork distribution scales in
string-length.
\item
The non-convexity of the rate function shows that, if users' string
statistics are distinct, there may be no fixed ordering of weakness
amongst users. That is, depending on how many guesses are made
before the $U$ users' strings are identified, the collection of
users whose strings have been identified are likely to be
distinct.
\item If all $V$ strings are chosen with the same statistics, then
the rate function is convex and the exponential growth rate of the
average guesswork as string-length increases is the specific R\'enyi
entropy of the string source with parameter
\begin{align*}
\frac{V-U+1}{V-U+2}
\in\left\{\frac 12,\frac 23,\frac 34,\frac4 5,\frac 56,\ldots\right\}.
\end{align*}
\item For homogeneous users, from an inquisitor's point of view,
there is a law of diminishing returns for the expected guesswork
growth rate in excess number of users ($V-U$).
\item For homogeneous users, from a designer's point of view, coming full
circle to Massey's original observation that Shannon entropy has
little quantitative relationship to how hard it is to guess a single
string, the specific Shannon entropy of the source is a lower bound
on the average guesswork growth rate for all $V$ and $U$.
\end{itemize}

These results generalize both the original guesswork studies, where
$U=V=1$, as well as some of the results in \cite{Merhav99,Hanawal11a}
where, as a wiretap model, the case $U=1$ and $V=2$ with one of the
strings selected uniformly, is considered and scaling properties
of the guesswork moments are established. Interestingly, we shall
show that that setting is one where the LDP rate function is typically
non-convex, so while results regarding the asymptotic behavior of
the guesswork moments can be deduced from the LDP, the reverse is
not true. To circumvent the lack of convexity, we prove the main
result using the contraction principle, Theorem 4.2.1 \cite{Dembo98},
and the LDP established in \cite{Christiansen13}, which itself
relies on earlier results of work referenced above.

\begin{figure}
\includegraphics[scale=0.46]{u_of_v_ex0}
\includegraphics[scale=0.46]{u_of_v_ex1}
\caption{Strings created from i.i.d. letters are selected from a
binary alphabet with probability $p$ for one character. Given an
inquisitor wishes to identify $U$ of $V$ strings, the left panel
shows the average exponential guesswork growth rate as a function
of $V-U$, the excess number of guessable strings; the right panel
shows the theoretically predicted approximate average guesswork for
$168$ bit strings, as used in triple DES, as a function of $V-U$,
the excess number of guessable strings.
}
\label{fig:bernoulli_guess}
\end{figure}

\section{
The impact of the number of users on expected guesswork growth rate,
an example
}
\label{sec:firstexample}

As an exemplar that illustrates the reduction in security that comes
from having multiple users, the left panel in Figure
\ref{fig:bernoulli_guess} the average guesswork growth rate for an
asymptotically optimal strategy is plotted for the simplest case,
a binary alphabet with $V$ i.i.d.  Bernoulli string sources. In
order to be satisfied, the inquisitor wishes to identify $U\leq V$
of the strings. The x-axis shows the excess number of guessable
strings, $V-U$, and the y-axis is the $\log_2$ growth rate of the
expected guesswork in string length.  If the source is perfectly
uniform (i.e. characters are chosen with a Bernoulli $1/2$ process),
then the average guesswork growth rate is maximal and unchanging
in $V-U$. If the source is not perfectly uniform, then the growth
rate decreases as the number of excess guessable strings $V-U$
increases, with a lower bound of the source's Shannon entropy.

For a string of length $168$ bits, as used in the triple DES cipher,
and a Bernoulli $(0.25)$ source, the right panel in Figure
\ref{fig:bernoulli_guess} displays the impact that the change in
this exponent has, approximately, on the average number of guesses
required to determine $U$ strings. More refined results for a
broader class of processes can be found in later sections, including
an estimate on the guesswork distribution.

The rest of this paper is organized as follows. In Section
\ref{sec:brief}, we begin with a brief overview of results on
guesswork that we have not touched on so far. Questions of optimal
strategy are considered in Section \ref{sec:strategy}. Asymptotically
optimal strategies are established to exist in Section \ref{sec:asymptote}
and results for these strategies appear in Section \ref{sec:results}.
In Section \ref{sec:mismatch} we present examples where strings
sources have distinct statistics. In Section \ref{sec:ident} we
return to the setting where string sources have identical statistics.
Concluding remarks appear in Section \ref{sec:conc}.

\section{A brief overview of guesswork}
\label{sec:brief}
Since Arikan's introduction of the long string length asymptotic,
several generalizations of its fundamental assumptions have been
explored. Arikan and Boztas \cite{Arikan02} investigate the setting
where the truthfulness in response to a query is not certain. Arikan
and Merhav \cite{Arikan98} loosen the assumption that inquisitor
needs to determine the string exactly, assuming instead that they
only need to identify it within a given distance. That the inquisitor
knows the distribution of words exactly is relaxed by Sundaresan
\cite{Sundaresan07b}, \cite{Sundaresan06}
and by the authors of \cite{Beirami15}.

Motivated by a wiretap application, the problem of multiple users
was first investigated by Merhav and Arikan \cite{Merhav99} in the
$V=2$ and $U=1$ setting, assuming one of the users selects
their string uniformly on a reduced alphabet. In \cite{Hayashi06}
Hayashi and Yamamoto extend the results in \cite{Merhav99} to the
case if there is an additional i.i.d. source correlated to the
first, used for coding purposes, while Harountunian and Ghazaryan
\cite{Haroutunian00} extend the results in \cite{Merhav99} to the
setting of \cite{Arikan98}.  Harountunian and Margaryan
\cite{Haroutunian12} expand on \cite{Merhav99} by adding noise to
the original string, altering the distribution of letters. Hanawal
and Sundaresan \cite{Hanawal11a} extend the bounds in \cite{Merhav99}
to a pre-limit and to more general sources, showing that they are
tight for Markovian and unifilar sources.

Sundaresan \cite{Sundaresan07a} uses length functions to identify
the link between guesswork and compression. This result is extended
by Hanawal and Sundaresan \cite{Hanawal11b} to relate guesswork to
the compression of a source over a countably infinite alphabet. In
\cite{Christiansen13a} the authors prove that, if the string is
conditioned on being an element of a typical set the expected
guesswork, is growing
more slowly
than a simple uniform approximation
would suggest. In \cite{Christiansen13b} the authors consider the
impact of guessing over a noisy erasure channel showing that the
mean noise on the channel is not the significant moment in determining
the expected guesswork, but instead one determined by its R\'enyi
entropy with parameter $1/2$.
Finally, we mention that recent work by Bunte and Lapidoth
\cite{Bunte14} identifies a distinct operational meaning for R\'enyi
entropy in defining a rate region for a scheduling problem.

\section{Optimal strategies}
\label{sec:strategy}
In order to introduce the key concepts used to determine the optimal
multi-user guesswork strategy, we first reconsider the optimal guesswork
strategy in the single user case, i.e.
$U=V=1$.
Recall that $ {\mathbb{A} }=\{0,\ldots,m-1\}$ is a finite set.

\begin{definition}
A single user strategy, $S: {\mathbb{A} }^k\mapsto\{1,\ldots,m^k\}$, is a
one-to-one map that determines the order in which guesses are made.
That is, for a given strategy $S$ and a given string $w\in {\mathbb{A} }^k$,
$S(w)$ is the number of guesses made until $w$ is queried.
\end{definition}

Let $W_k$ be a random variable taking values in $ {\mathbb{A} }^k$. Assume that
its probability mass function, $P(W_k=w)$ for all $w\in {\mathbb{A} }^k$, is
known. Since the first results on the topic it has been clear that
the best strategy, which we denote $G$, is to guess from most likely
to least likely, breaking ties arbitrarily. In particular, $G$ is
defined by $G(w)<G(w')$ if $P(W_k=w)>P(W_k=w')$. We
begin by assigning optimality a precise meaning in terms of stochastic
dominance \cite{Lehmann55,denuit06}.

\begin{definition}
A strategy $S$ is optimal for $W_k$ if the random variable $S(W_k)$
is stochastically dominated by $S'(W_k)$, for all strategies $S'$.
That is, if $P(S(W_k)\leq n) \geq P(S'(W_k)\leq n)$ for all strategies
$S'$ and all $n\in\{1,\ldots,m^k\}$.
\end{definition}

This definition captures the stochastic aspect of guessing by stating
than an optimal strategy is one where the identification stopping
time is probabilistically smallest. One consequence of this definition
that explains its appropriateness is that for any monotone function
$\phi:\{1,\ldots,m^k\}\to {\mathbb{R} }$, it is the case that $E(\phi(S(W_k)))\leq
E(\phi(S'(W_k)))$ for an optimal $S$ and any other $S'$ (e.g.
Proposition 3.3.17, \cite{denuit06}). Thus $S(W_k)$ has the least
moments over all guessing strategies.
That guessing from most- to least-likely in the single user case is
optimal is readily established.
\begin{lemma}
\label{lem:1opt}
If $V=U=1$, the optimal strategies are those that guess from most
likely to least likely, breaking ties arbitrarily.
\end{lemma}
\begin{proof}
Consider the strategy $G$ defined above and any other strategy $S$.
By construction, for any $n\in\{1,\ldots,m^k\}$
\begin{align*}
P(G(W_k)\leq n) &= \sum_{i=1}^n P(G(W_k)=i) \\
	& = \max_{w_1,\ldots,w_n} \left(\sum_{i=1}^n P(W_k=w_i)\right)\\
	&\geq \sum_{i=1}^n P(S(W_k)=i) = P(S(W_k)\leq n).
\end{align*}
\end{proof}

In the multi-user case, where (user, string) pairs are queried, a
strategy is defined by the following.
\begin{definition}
A multi-user strategy is a one-to-one map
$S:\{1,\ldots,V\}\times {\mathbb{A} }^k\mapsto\{1,\ldots,Vm^k\}$ that orders
the guesses of (user, string) pairs.
\end{definition}

The expression for the number of guesses required to identify $U$
strings is a little involved as we must take into account that we
stop making queries about a user once
their string has been identified.
For a given strategy $S$, let
$ {N_S} :\{1,\ldots,V\}\times\{1,\ldots,Vm^k\}\mapsto\{1,\ldots,m^k\}$ be
defined by
\begin{align*}
 {N_S} (v,n) = |\{w\in {\mathbb{A} }^k:S(v,w)\leq n\}|,
\end{align*}
which computes the number of queries in the strategy up to $n$
that correspond to user $v$.

The number of queries that need to be made if $U$ strings are
to be identified is
\begin{align*}
{ T(U,V,\vw)}  =  {\text{U-min} } \left(S(1,w^{(1)}),\ldots,S(V,w^{(V)})\right),
\end{align*}
where $ {\text{U-min} } : {\mathbb{R} }^V\to {\mathbb{R} }$ and $ {\text{U-min} } ( {\vec{x}} )$ gives the $U^{\rm th}$
smallest component of $ {\vec{x}} $.
The
number of guesses required to identify $U$ components of $ {\vec{w}}
=(w^{(1)},\ldots,w^{(V)})$ is then
\begin{align}
\label{eq:GS}
 {G_S} (U,V, {\vec{w}} )=
\sum_{v=1}^V  {N_S} \left(v,
	\min\left(S(v,w^{(v)}),{ T(U,V,\vw)} \right) \right).
\end{align}
This apparently unwieldy object counts the number of queries made
to each user, curtailed either when
their
string is identified or
when $U$ strings of other users are identified.

If $U=V$, equation \eqref{eq:GS} simplifies significantly, as
$S(v,w^{(v)})\leq{ T(U,V,\vw)} $ for all
$v\in\{1,\ldots,V\}$, becoming
\begin{align}
\label{eq:U=V}
 {G_S} (V,V, {\vec{w}} )=
\sum_{v=1}^V  {N_S} \left(v, S(v,w^{(v)}) \right),
\end{align}
the sum of the number of queries required to identify each individual
word. In this case, we have the analogous result to Lemma \ref{lem:1opt},
which is again readily established.
\begin{lemma}
\label{lem:UVopt}
If $V=U$, the optimal strategies are those that employ individual
optimal strategies, but with users selected in any order.
\end{lemma}
\begin{proof}
For any multi-user strategy $S$, equation \eqref{eq:U=V} holds.
Consider an element in the sum on the right hand side,
$ {N_S} \left(v, S(v,w^{(v)}) \right)$.
It can be recognized to be the number of queries made to user $v$
until their string is identified. By Lemma \ref{lem:1opt}, for each
user $v$, for any $S$ this stochastically dominates the equivalent
single user optimal strategy. Thus the multi-user optimal strategies
in this case are the sum of individual user optimal strategies,
with users queried in any arbitrary order.
\end{proof}

The formula \eqref{eq:GS} will be largely side-stepped when we
consider asymptotically optimal strategies, but is needed to establish
that there is, in general, no stochastically dominant strategy if
$V>U$. With $ {\vec{W}} _k=(W_k^{(1)},\ldots,W_k^{(V)})$ being a random vector
taking values in $ {\mathbb{A} }^{kV}$ with independent, not necessarily identically
distributed, components, we are not guaranteed the existence of an
$S$ such that $P( {G_S} (U,V, {\vec{W}} _k)\leq n) \geq ( {G_{S'}} (U,V, {\vec{W}} _k)\leq n)$
for all alternate strategies $S'$.

\begin{lemma}
If $V>U$, a stochastically dominant strategy does not necessarily exist.
\end{lemma}
\begin{proof}
A counter-example suffices and so let $k=1$, $V=2$, $U=1$ and
$ {\mathbb{A} }=\{0,1,2\}$. Let the distributions of $W_1^{(1)}$ and $W_1^{(2)}$
be
\begin{center}
\begin{tabular}{|c|c|}
\hline
User 1 & User 2\\
\hline
$P(W_1^{(1)}=0)=0.6$ & $P(W_1^{(2)}=0)=0.5$  \\
$P(W_1^{(1)}=1)=0.25$ & $P(W_1^{(2)}=1)=0.4$ \\
$P(W_1^{(1)}=2)=0.15$ & $P(W_1^{(2)}=2)=0.1$\\
\hline
\end{tabular}
\end{center}
If a stochastically dominant strategy exists, its first guess must
be user $1$, string $0$, i.e. $S(1,0)=1$, so that $P( {G_S} (1, {\vec{W}} _1)=1) =
0.6$. Given this first guess, to maximize $P( {G_S} (1, {\vec{W}} _1)\leq2)$, the
second guess must be user $1$, string $1$, $S(1,1)=2$, so that
$P( {G_S} (1, {\vec{W}} _1)\leq 2) = 0.85$.

An alternate strategy with $S(2,0)=1$ and $S(2,1)=2$, however,
gives $P( {G_{S'}} (1, {\vec{W}} _1)=1)=0.5$ and $P( {G_{S'}} (1, {\vec{W}} _1)\leq 2)=0.9$.
While $P( {G_S} (1, {\vec{W}} _1)=1)>P( {G_{S'}} (1, {\vec{W}} _1)=1)$,
$P( {G_S} (1, {\vec{W}} _1)\leq2)<P( {G_{S'}} (1, {\vec{W}} _1)\leq2)$ and so there is
no strategy stochastically dominated by all others in this case.
\end{proof}

Despite this lack of universal optimal strategy, we shall show that
there is a sequence of random variables that are stochastically
dominated by the guesswork of all strategies and, moreover, there
exists a strategy with identical performance in Arikan's long string
length asymptotic.

\begin{definition}
A strategy $S$ is asymptotically optimal if $\{k^{-1}\log
 {G_S} (U,V, {\vec{W}} _k)\}$ satisfies a LDP
with the same rate function as a sequence
$\{k^{-1}\log \Upsilon(U,V, {\vec{W}} _k)\}$ where $\Upsilon(U,V, {\vec{W}} _k)$
is stochastically dominated by $ {G_{S'}} (U,V, {\vec{W}} _k)$ for all
strategies $S'$.
\end{definition}

Note that $\Upsilon(U,V,\cdot)$ need not correspond to the guesswork
of a strategy.

\section{An asymptotically optimal strategy}
\label{sec:asymptote}

Let $\{ {\vec{W}} _k\}$ be a sequence of random strings, with $ {\vec{W}} _k$ taking values in
$ {\mathbb{A} }^{kV}$, with independent components, $W_k^{(v)}$, corresponding
to strings selected by users $1$ through $V$, although each user's
string
may
not be constructed from i.i.d. letters.
For each individual
user, $v\in\{1,\ldots,V\}$, let $ {G^{(v)}} $ denote its single-user optimal
guessing strategy; that is, guessing from most likely to least likely.

We shall
show that the following random variable, constructed
using the $ {G^{(v)}} $, is stochastically
dominated by the guesswork distribution of all strategies:
\begin{align}
 {G_{\text{opt}} } (U,V, {\vec{W}} _k) =
 {\text{U-min} }  \left(G^{(1)}(W^{(1)}_k),\ldots,G^{(V)}(W^{(V)}_k)\right).
\label{eq:LB}
\end{align}
This can be thought of as allowing the inquisitor to query, for
each $n$ in turn, the $n^{\rm th}$ most likely string for all users
while only accounting for a single guess and so it does not
correspond to an allowable strategy.

\begin{lemma}
For any strategy $S$ and any $U\in\{1,\ldots,V\}$,
$ {G_{\text{opt}} } (U,V, {\vec{W}} _k)$ is stochastically dominated by $ {G_S} (U,V, {\vec{W}} _k)$.
That is, for any any $U\in\{1,\ldots,V\}$
and any
$n\in\{1,\ldots,m^k\}$
\begin{align*}
P( {G_{\text{opt}} } (U,V, {\vec{W}} _k)\leq n) \geq P( {G_S} (U,V, {\vec{W}} _k)\leq n).
\end{align*}
\end{lemma}
\begin{proof}
Using equation \eqref{eq:GS} and the positivity of its
summands, for any strategy $S$
\begin{align*}
&G_S(U, V,  {\vec{w}} )\\
&\ge {\text{U-min} }  ( {N_S} (1, S(1, w^{(1)})),\ldots,  {N_S} (V, S(V, w^{(V)}))).
\end{align*}
As for each $v\in\{1,\ldots,V\}$, $G^{(v)}(W_k^{(v)})$ is stochastically
dominated by all other strategies,
\begin{align*}
P(G^{(v)}(W_k^{(v)})\le n)\ge P( {N_S} (v, S(1, W_k^{(v)}))\le n).
\end{align*}
Using equation \eqref{eq:LB}, this implies that
\begin{align*}
&P( {G_{\text{opt}} } ( {\vec{W}} _k)\le n)\\
&\ge P( {\text{U-min} }  ( {N_S} (1, S(1, W_k^{(1)})),\ldots,  {N_S} (V, S(V, W_k^{(V)})))\le n)\\
&\ge P(G_S(U, V,  {\vec{W}} _k)\le n),
\end{align*}
as required.
\end{proof}

The strategy that we construct that will asymptotically meet the
performance of the lower bound is to round-robin the single user
optimal strategies. That is, to query the most likely string of one
user followed by the most likely string of a second user and so
forth, for each user in a round-robin fashion, before moving to the
second most likely string of each user. An upper bound on this
strategy's performance is to consider only stopping at the end of
a round of such queries, even if they reveal more than $U$ strings,
which gives
\begin{align}
V  {G_{\text{opt}} } (U,V, {\vec{W}} _k),
\label{eq:UB}
\end{align}
where $ {G_{\text{opt}} } (U,V, {\vec{W}} _k)$ is defined in \eqref{eq:LB}.

In large deviations parlance the stochastic processes
$\{k^{-1}\log {G_{\text{opt}} } (U,V, {\vec{W}} _k)\}$ and $\{k^{-1}\log(V {G_{\text{opt}} } (U,V, {\vec{W}} _k))\}$
arising from equations \eqref{eq:LB} and \eqref{eq:UB} are exponentially
equivalent, e.g. Section 4.2.2 \cite{Dembo98}, as $\lim_{k\to\infty}
k^{-1}\log V=0$. As a result, if one process satisfies the LDP
with a rate function that has compact level sets, then the other
does \cite{Dembo98}[Theorem 4.2.3]. Thus if
$\{k^{-1}\log {G_{\text{opt}} } (U,V, {\vec{W}} _k)\}$ can be shown to satisfy a LDP,
then the round-robin strategy is proved to be asymptotically optimal.

\section{Asymptotic performance of optimal strategies}
\label{sec:results}

We first recall what is known for the single-user setting.
For each individual user $v\in\{1,\ldots,V\}$, the
specific R\'enyi entropy of the sequence $\{ W^{(v)} _k\}$,
should it exist, is defined by
\begin{align*}
 {R^{(v)}} (\beta):=
	\lim_{k\to\infty} \frac 1k \frac{1}{1-\beta}
	\log \sum_{w_k\in {\mathbb{A} }^k} P( W^{(v)} _k=w_k)^\beta
\end{align*}
for $\beta\in(0,1)\cup(1,\infty)$, and for $\beta=1$,
\begin{align*}
 {R^{(v)}} (1)&:=\lim_{\beta\uparrow1}  {R^{(v)}} (\beta)\\
&= -\lim_{k\to\infty} \frac1k \sum_{w_k\in {\mathbb{A} }^k} P( W^{(v)} _k=w_k)\log P( W^{(v)} _k=w_k),
\end{align*}
the specific Shannon entropy. Should $ {R^{(v)}} (\beta)$ exist
for $\beta\in(0,\infty)$, then the specific min-entropy
is defined
\begin{align*}
 {R^{(v)}} (\infty)&=\lim_{\beta\to\infty} {R^{(v)}} (\beta) \\
&= -\lim_{k\to\infty}\frac1k \max_{w_k\in {\mathbb{A} }^k} \log P( W^{(v)} _k=w_k),
\end{align*}
where the limit necessarily exists.
The existence of $ {R^{(v)}} (\beta)$ for all $\beta>0$ and its relationship
to the scaled Cumulant Generating Function
(sCGF)
\begin{align}
 {\Lambda_G^{(v)}} (\alpha)
&= \lim_{k\to\infty} \frac 1k \log E(\exp(\alpha\log  {G^{(v)}} ( W^{(v)} _k))) \nonumber\\
	&=
	\begin{cases}
	\displaystyle
	\alpha  {R^{(v)}} \left(\frac{1}{1+\alpha}\right) & \text{ if } \alpha>-1\\
	- {R^{(v)}} (\infty) & \text{ if } \alpha\leq-1
	\end{cases}
\label{eq:sCGF}
\end{align}
has been established for the single user case for a broad class of
character sources that encompasses i.i.d., Markovian and general
sofic shifts that admit an entropy condition
\cite{Arikan96,Malone042,Pfister04,Hanawal11,Christiansen13}.
If, in addition, $ {R^{(v)}} (\beta)$ is differentiable
with respect to $\beta$
and has a continuous
derivative, it is established in \cite{Christiansen13} that the
process $\{k^{-1}\log  {G^{(v)}} ( W^{(v)} _k)\}$ satisfies a LDP,
i.e. equation \eqref{eq:LDP},
with a convex rate function
\begin{align}
\label{eq:rf}
 {\Lambda_G^{(v)}} ^*(x) = \sup_{\alpha\in {\mathbb{R} }}\left(x\alpha- {\Lambda_G^{(v)}} (\alpha)\right).
\end{align}
In \cite{Christiansen13}, this LDP is used to deduce an
approximation to the guesswork distribution,
\begin{align}
\label{eq:approx1}
P( {G^{(v)}} ( W^{(v)} _k)=n) \approx
\frac 1n \exp\left(-k {\Lambda_G^{(v)}} ^*\left(\frac 1k\log n\right)\right)
\end{align}
for large $k$ and $n\in\{1,\ldots,m^k\}$.

The following theorem establishes the fundamental analogues of these
results for an asymptotically optimal strategy, where
user strings may have distinct statistical properties.

\begin{theorem}
\label{thm:main}
Assume that the components of $\{ {\vec{W}} _k\}$ are independent and
that for each $v\in\{1,\ldots,V\}$ $ {R^{(v)}} (\beta)$ exists for
all $\beta>0$, is differentiable and has a continuous derivative,
and that equation \eqref{eq:sCGF} holds. Then the process
$\{k^{-1}\log {G_{\text{opt}} } (U,V, {\vec{W}} _k)\}$, and thus any asymptotically optimal
strategy, satisfies a Large Deviation Principle.
Defining
\begin{align*}
& {\delta^{(v)}} (x)=\begin{cases}
	 {\Lambda_G^{(v)}} ^*(x) & \text{ if }x\le  {R^{(v)}} (1)\\
	0 & \text{ otherwise}
	\end{cases}\\
&\text{  and }  {\gamma^{(v)}} (x)=\begin{cases}
	 {\Lambda_G^{(v)}} ^*(x) &\text{ if }x\ge  {R^{(v)}} (1)\\
	0 & \text{ otherwise}
\end{cases},
\end{align*}
the rate function is
\begin{align}
&\IGopt(U,V,x)=\nonumber\\
&\max_{v_1,\ldots, v_V}
\left( {\Lambda_G^{(v_1)}} ^*(x)+\sum_{i=2}^U \delta^{(v_i)}(x)
+\sum_{i=U+1}^V  {\gamma^{(v_i)}} (x)\right),
\label{eq:Iopt}
\end{align}
which is lower semi-continuous and has compact level sets, but
may not be convex. The sCGF capturing how the moments scale is
\begin{align}
\LambdaGopt(U,V,\alpha)
&= \lim_{k\to\infty} \frac 1k \log E(\exp(\alpha\log  {G_{\text{opt}} } (U,V, {\vec{W}} _k)))\nonumber\\
	&= \sup_{x\in[0,\log(m)]}\left(\alpha x -\IGopt(U,V,x)\right).
\label{eq:scgf}
\end{align}
\end{theorem}
\begin{proof}
Under the assumptions of the theorem,
for each $v\in\{1,\ldots,V\}$, $\{k^{-1}
\log  {G^{(v)}}  ( W^{(v)} _k) \}$ satisfies the LDP with the rate function
given in equation \eqref{eq:rf}. As users' strings are selected
independently, the sequence of vectors
\begin{align*}
\left\{\left(\frac 1k \log G^{(1)}(W_k^{(1)}), \ldots,
	\frac 1k \log G^{(V)}(W_k^{(V)}) \right)\right\}
\end{align*}
satisfies the LDP in $ {\mathbb{R} }^V$ with rate function $I(y^{(1)},\ldots,y^{(V)})
= \sum_{v=1}^V  {\Lambda_G^{(v)}} ^*(y^{(v)})$, the sum of the rate functions
given in equation \eqref{eq:rf}.

Within our setting, the contraction principle, e.g. Theorem 4.2.1
\cite{Dembo98}, states that if a sequence of random variables
$\{X_n\}$ taking values in a compact subset of $ {\mathbb{R} }^V$ satisfies a
LDP with rate function $I: {\mathbb{R} }^V\mapsto[0,\infty]$ and $f: {\mathbb{R} }^V\mapsto {\mathbb{R} }$
is a continuous function, then the sequence $\{f(X_n)\}$ satisfies
the LDP with rate function $\inf_{ {\vec{y}} }\{I( {\vec{y}} ):f( {\vec{y}} )=x\}$.

Assume, without loss of generality, that $ {\vec{x}} \in {\mathbb{R} }^V$ is such that
$x^{(1)}<x^{(2)}<\cdots<x^{(V)}$, so that $ {\text{U-min} } ( {\vec{x}} ) = x^{(U)}$,
and let
$ {\vec{x}} _n=(x^{(1)}_n,\ldots,x^{(V)}_n)\to {\vec{x}} $. Let
$\epsilon < \inf\{x^{(v)}-x^{(v-1)}:v\in\{2,\ldots,V\}\}$. There
exists $N_\epsilon$ such that $\max_{v=1,\ldots,V}
|x^{(v)}_n-x^{(v)}|<\epsilon$ for all $n>N_\epsilon$. Thus
for all $v\in\{2,\ldots,V\}$ and all $n>N_\epsilon$
$x^{(v)}_n-x^{(v-1)}_n > x^{(v)}-x^{(v-1)}-\epsilon>0$
and so
$| {\text{U-min} } ( {\vec{x}} _n)- {\text{U-min} } ( {\vec{x}} )|=|x_n^{(U)}-x^{(U)}|<\epsilon$.
Hence $ {\text{U-min} } : {\mathbb{R} }^V\to {\mathbb{R} }$ is a continuous function
and that a LDP
holds follows from an application of the contraction principle,
giving the rate function
\begin{align*}
\IGopt(U,V,x) = \inf\left\{
                \sum_{v=1}^V  {\Lambda_G^{(v)}} ^*(y_v): {\text{U-min} } (y_1,\ldots,y_V)=x
                \right\}.
\end{align*}
This expression simplifies to that in equation \eqref{eq:Iopt} by
elementary arguments.
The sCGF result follows from an
application of Varahadan's Lemma, e.g \cite[Theorem 4.3.1]{Dembo98}.
\end{proof}

The expression for the rate function in equation \eqref{eq:Iopt}
lends itself to a useful interpretation. In the long string-length
asymptotic, the likelihood that an inquisitor has identified $U$
of the $V$ users' strings after approximately $\exp(kx)$ queries
is contributed to by three distinct groups of identifiable users.
For given $x$, the argument in the first term $(v_1)$ identifies
the last of the $U$ users whose string is identified. The second
summed term is contributed to by the collection of users, $(v_2)$
to $(v_U)$, whose strings have already been identified prior to
$\exp(kx)$ queries, while the final summed term corresponds to those
users, $(v_{U+1})$ to $(v_V)$, whose strings have not been identified.

The reason for using the notation $\IGopt(U,V,\cdot)$ in lieu of
$\LambdaGopt^*(U,V,\cdot)$ for the rate function in Theorem
\ref{thm:main} is that $\IGopt(U,V,\cdot)$ is not convex in general,
which we shall
demonstrate by example, and so is not always the
Legendre-Fenchel transform of the sCGF $\LambdaGopt(U,V,\cdot)$.
Instead
\begin{align*}
\LambdaGopt^*(U,V,x) =
	\sup_\alpha\left(\alpha x -\LambdaGopt(U,V,\alpha)\right)
\end{align*}
forms the convex hull of $\IGopt(U,V,\cdot)$. In particular, this
means that we could not have proved Theorem \ref{thm:main} by
establishing properties of $\LambdaGopt(U,V,\cdot)$ alone, which
was the successful route taken for the $U=V=1$ setting, and instead
needed to rely on the LDP proved in \cite{Christiansen13}.
Indeed, in the setting considered in \cite{Merhav99, Hanawal11a}
with $U=1$, $V=2$, with one of the strings chosen uniformly, while
the authors directly identify $\LambdaGopt(1,2,\alpha)$ for $\alpha>0$,
one cannot establish a full LDP from this approach as the resulting
rate function is not convex.

Convexity
of the rate function defined in equation \eqref{eq:Iopt}
is ensured, however, if all
users select
strings
using the same stochastic properties, whereupon the
results in Theorem \ref{thm:main} simplify greatly.

\begin{corollary}
\label{cor:same}
If, in addition to the assumptions of Theorem \ref{thm:main},
$ {\Lambda_G^{(v)}} (\cdot)= {\Lambda_G} (\cdot)$ for all $v\in\{1,\ldots,V\}$ with
corresponding R\'enyi entropy $R(\cdot)$, then the rate function
in equation \eqref{eq:rf} simplifies to the convex function
\begin{align}
\LambdaGopt^*(U,V,x) &=
	\begin{cases}
	\displaystyle
	U {\Lambda_G} ^*(x) & \text{ if } x\leq R(1)\\
	\displaystyle
	(V-U+1) {\Lambda_G} ^*(x) & \text{ if } x\geq R(1)
	\end{cases}
\label{eq:rf2}
\end{align}
where $R(1)$ is the specific Shannon entropy, and the sCGF in equation
\eqref{eq:scgf} simplifies to
\begin{align}
\label{eq:scgf2}
\LambdaGopt(U,V,\alpha) &=
	\begin{cases}
	\displaystyle
	U {\Lambda_G} \left(\frac{\alpha}{U}\right) & \text{ if } \alpha\leq0\\
	\displaystyle
	(V-U+1) {\Lambda_G} \left(\frac{\alpha}{V-U+1}\right) & \text{ if } \alpha\geq0.
	\end{cases}
\end{align}
In particular, with $\alpha=1$ we have
\begin{align}
&\lim_{k\to\infty} \frac 1k \log E\left( {G_{\text{opt}} } (U,V, {\vec{W}} _k)\right)\nonumber\\
	&= \LambdaGopt(1)\nonumber\\
	&= (V-U+1) {\Lambda_G} \left(\frac{1}{V-U+1}\right)\nonumber\\
	&= R\left(\frac{V-U+1}{V-U+2}\right),
	\label{eq:average}
\end{align}
where $R((n+1)/(n+2))-R((n+2)/(n+3))$ is a decreasing
function of $n\in {\mathbb{N} }$.
\end{corollary}
\begin{proof}
The simplification in equation \eqref{eq:rf2} follows readily from
equation \eqref{eq:Iopt}. To establish that
$R((n+1)/(n+2))-R((n+2)/(n+3))$ is a decreasing function of $n\in {\mathbb{N} }$,
it suffices to establish that $R((x+1)/(x+2))$ is a convex, decreasing
function for $x\in {\mathbb{R} }_+$.

That $R(x)\downarrow R(1)$ as $x\uparrow1$ is a general property
of specific R\'enyi entropy. For convexity, using equation
\eqref{eq:average} it suffices to
show that $x {\Lambda_G} (1/x)$ is convex for $x>0$. This can be seen
by noting that for any $a\in(0,1)$ and $x_1,x_2>0$,
\begin{align*}
&(a x_1+(1-a)x_2)
 {\Lambda_G} \left(\frac{1}{a x_1+(1-a)x_2}\right)\\
&= (a x_1+(1-a)x_2)
	 {\Lambda_G} \left(\eta \frac{1}{x_1}+(1-\eta)\frac{1}{x_2}\right)\\
&\leq a x_1  {\Lambda_G} \left(\frac{1}{x_1}\right)
	+(1-a)x_2  {\Lambda_G} \left(\frac{1}{x_2}\right),
\end{align*}
where $\eta = a x_1/(a x_1+(1-a)x_2)\in(0,1)$ and we have used the
convexity of $ {\Lambda_G} $.
\end{proof}

As the growth rate, $R((n+1)/(n+2))-R((n+2)/(n+3))$, is decreasing
there is a law of diminishing returns for the inquisitor where the
greatest decrease in the average guesswork growth rate is through
the provision of one additional user.
From the system designer's point of view, the specific Shannon
entropy of the source is a universal lower bound on the exponential
growth rate of the expected guesswork that, while we cannot take
the limit to infinity, is tight for large $V-U$.

Regardless
of whether the rate function $\IGopt(U,V,\cdot)$ is
convex, Theorem \ref{lem:approx}, which follows, justifies the approximation
\begin{align*}
P( {G_{\text{opt}} } (U,V, {\vec{W}} _k)=n) \approx
	\frac 1n \exp\left(-k\IGopt\left(U,V,\frac 1k\log n\right)\right)
\end{align*}
for large $k$ and $n\in\{1,\ldots,m^k\}$. It is analogous to that
in equation \eqref{eq:approx1}, first developed in \cite{Christiansen13},
but there are additional difficulties that must be overcome to
establish it. In particular, if $U=V=1$, the likelihood that the
string is identified at each query is a decreasing function of guess
number, but this is not true in the more general case.

As a simple example, consider $U=V=2$, $ {\mathbb{A} }=\{0,1\}$, strings of
length $1$ and strings chosen uniformly. Here the probability of
guessing both strings in one guess is $1/4$, but at the second guess
it is $3/4$. Despite this lack of monotonicity, the approximation
still holds in the following sense.

\begin{theorem}
\label{lem:approx}
Under the assumptions of Theorem \ref{thm:main}, for any $x \in [0,
\log m)$ we have
\begin{align*}
&\lim_{\epsilon \downarrow 0}\liminf_{k\rightarrow \infty}
	\frac 1k \log \inf_{n \in K_k(x, \epsilon)}P( {G_{\text{opt}} } (U,V, {\vec{W}} _k)=n)\\
&=\lim_{\epsilon \downarrow 0}\limsup_{k\rightarrow \infty}
	\frac 1k \log \sup_{n \in K_k(x, \epsilon)}P( {G_{\text{opt}} } (U,V, {\vec{W}} _k)=n)\\
&=-I_{ {G_{\text{opt}} } }(U, V, x)-x,
\end{align*}
where
\begin{align*}
K_k(x, \epsilon)=\{n:n \in (\exp(k(x-\epsilon)), \exp((k(x+\epsilon)))\}
\end{align*}
is the collection of guesses made in a log-neighborhood of $x$.
\end{theorem}
\begin{proof}
The proof follows the ideas in \cite{Christiansen13} Corollary 4,
but with the added difficulties resolved by isolating the last word
that is likely to be guessed and leveraging the monotonicity it its
individual likelihood of being identified.

Noting the definition of $K_k(x, \epsilon)$ in the statement
of the theorem, consider for $x\in(0,\log(m))$
\begin{align*}
&\sup_{n \in K_k(x, \epsilon)}P( {G_{\text{opt}} } (U,V, {\vec{W}} _k)=n)\nonumber\\
=& \sup_{n \in K_k(x, \epsilon)}\sum_{(v_1, \ldots, v_V)}
	P( {G^{(v_1)}} (W_k^{(v_1)})=n)\\
	&\prod_{i=2}^{U}P( {G^{(v_i)}} (W_k^{(v_i)})\le n)
	\prod_{i=U+1}^{V}P( {G^{(v_i)}} (W_k^{(v_i)})\ge n)\\
\le& \sup_{n \in K_k(x, \epsilon)}
	\max_{(v_1, \ldots, v_V)}(V!)P( {G^{(v_1)}} (W_k^{(v_1)})=n)\\
	&\prod_{i=2}^{U}P( {G^{(v_i)}} (W_k^{(v_i)})\le n)
		\prod_{i=U+1}^{V}P( {G^{(v_i)}} (W_k^{(v_i)})\ge n)\\
\le& \sup_{n \in K_k(x, \epsilon)}
	\max_{(v_1, \ldots, v_V)}(V!)P( {G^{(v_1)}} (W_k^{(v_1)})=n)\\
	&\prod_{i=2}^{U}
	P\left(\frac 1k \log  {G^{(v_i)}} (W_k^{(v_i)})\le x-\epsilon\right)\\
&\prod_{i=
U+1
}^{V}P\left(\frac 1k \log  {G^{(v_i)}} (W_k^{(v_i)})\ge x+\epsilon\right)\nonumber\\
&\le \inf_{n \in K_k(x-2\epsilon, \epsilon)}\max_{(v_1, \ldots, v_V)}(V!)
P\left(\frac1k \log  {G^{(v_1)}} (W_k^{(v_1)})=n\right)\\
&\prod_{i=2}^{U}
P\left(\frac 1k \log  {G^{(v_i)}} (W_k^{(v_i)})\le x+\epsilon\right)\\
&\prod_{i=U+1}^{V}P\left(\frac 1k \log {G^{(v_i)}} (W_k^{(v_i)})\ge x-\epsilon\right).\nonumber
\end{align*}
The first equality holds by definition of $ {G_{\text{opt}} } (U,V,\cdot)$.  The
first inequality follows from the union bound over all possible
permutations of $\{1, \ldots, V\}$. The second inequality utilizes
$k^{-1}\log n \in (x-\epsilon, x+\epsilon)$ if $n\in K_k(x, \epsilon)$,
while the third inequality uses the monotonic decreasing probabilities
in guessing a single user's string.

Taking $\lim_{\epsilon \downarrow 0}\limsup_{k\rightarrow
\infty}k^{-1}\log$ on both sides of the inequality, interchanging
the order of the max and the supremum, using the continuity
of $ {\Lambda_G^{(v)}} (\cdot)$ for each $v\in\{1,\cdots,V\}$, and the
representation of the rate function $\IGopt(U,V,\cdot)$ in equation
\eqref{eq:Iopt}, gives the upper bound
\begin{align*}
&\lim_{\epsilon \downarrow 0}\limsup_{k\rightarrow \infty}\frac 1k \log \sup_{n \in K_k(x, \epsilon)}
	P( {G_{\text{opt}} } ( {\vec{W}} _k)=n) \\
&\leq-\IGopt(U, V, x)-x.
\end{align*}
Considering the least likely guesswork in the ball leads to a
matching lower bound. The other case, $x=0$, follows similar logic,
leading to the result.
\end{proof}

We next provide some illustrative examples of what these results
imply, returning to using $\log_2$ in figures.

\section{Mismatched Statistics Example}
\label{sec:mismatch}

The potential lack of convexity in the rate function of Theorem
\ref{thm:main}, equation \eqref{eq:Iopt}, only arises if users'
string statistics are asymptotically distinct. The significance of
this lack of convexity on the phenomenology of guesswork can be
understood in terms of the asymptotically optimal round-robin
strategy: if the rate function is not convex, there is no single
set of users whose strings are most vulnerable.
That is, if $U$ strings are recovered after a small number of
guesses, they will be from one set of users, but after a number of
guesses corresponding to a transition from the initial convexity
they will be from another set of users.
This is made explicit in the following corollary to Theorem
\ref{thm:main}.

\begin{corollary}
If $\IGopt(U,V,x)$ is not convex in $x$, then there is there is no
single set of users whose strings will be identified in the long
string length asymptotic.
\end{corollary}
\begin{proof}
We prove the result by establishing the contraposition: if a single set
of users is always most vulnerable, then $\IGopt(U,V,x)$ is convex.
Recall the expression for $\IGopt(U,V,x)$ given in equation
\eqref{eq:Iopt}
\begin{align*}
&\IGopt(U,V,x)=\\
&\max_{v_1,\ldots, v_V}
\left( {\Lambda_G^{(v_1)}} ^*(x)+\sum_{i=2}^U \delta^{(v_i)}(x)
+\sum_{i=U+1}^V  {\gamma^{(v_i)}} (x)\right),
\end{align*}
As explained after Theorem \ref{thm:main}, for given $x$ the set
of users $\{(v_1),\ldots,(v_U)\}$ corresponds to those users whose
strings, on the scale of large deviations, will be identified by
the inquisitor after approximately $\exp(kx)$ queries. If this set
is unchanging in
$x$, i.e. the same set of users is identified
irrespective of $x$, then both of the functions
\begin{align*}
\left( {\Lambda_G^{(v_1)}} ^*(x)+\sum_{i=2}^U \delta^{(v_i)}(x)\right)
\text{ and }
\sum_{i=U+1}^V  {\gamma^{(v_i)}} (x)
\end{align*}
are sums of functions that are convex in $x$, and so are convex
themselves. Thus the sum of them, $\IGopt(U,V,x)$, is convex.
\end{proof}

This is most readily
illustrated by an example that falls within the two-user setting
of \cite{Merhav99}, where one string is constructed from uniformly
from i.i.d. bits and the other string from non-uniformly selected
i.i.d. bytes.
\begin{figure}
\begin{center}
\includegraphics[scale=0.46]{nonconvex.pdf}
\end{center}
\caption{User 1 picks a uniform bit string. User 2 picks a non-uniform
i.i.d. byte string. The straight line starting at $(0,1)$ displays
${ {\Lambda_G} ^{(1)}}^*(x)$, the large deviations rate function for
guessing the uniform bit string. The convex function starting
below it is ${ {\Lambda_G} ^{(2)}}^*(x)$, the rate function for guessing
the non-uniform byte string. The highlighted line, which is the
minimum of the two rate functions until $x=1$ and then $+\infty$
afterwards, displays $I_{ {G_{\text{opt}} } }(1, 2, x)$, as determined by
\eqref{eq:Iopt}, the rate function for an inquisitor to guess one
of the two strings. Its non-convexity demonstrates that initially
it is the bytes that are most likely to be revealed by brute force
searching, but eventually it is the uniform bits that are more
likely to be identified. The Legendre-Fenchel transform of the
scaled cumulant generating function of the guesswork distributions
would form the convex hull of the highlighted line and so this
could not be deduced by analysis of the asymptotic moments.
}
\label{fig:nonconvex}
\end{figure}

Let $ {\mathbb{A} }=\{0,\ldots,7\}$, $U=1$ and $V=2$. Let one character source
correspond to the output of a cryptographically secure pseudo-random
number generator. That is, despite having a byte alphabet, the source
produces perfectly uniform i.i.d. bits,
\begin{align*}
P(W^{(1)}_1=i) &=
	\begin{cases}
	1/2 & \text{ if } i\in\{0,1\}\\
	0 & \text{ otherwise}.
	\end{cases}
\end{align*}
The other source can be thought of as i.i.d. bytes generated by a
non-uniform source,
\begin{align*}
P(W^{(2)}_1=i) &=
	\begin{cases}
	0.55 & \text{ if } i=0\\
	0.1 & \text{ if } i\in\{1,2\}\\
	0.05 & \text{ if } i\in\{3,\ldots,7\}.
	\end{cases}
\end{align*}
This models the situation of a piece of data, a string from the
second source, being encrypted with a shorter, perfectly uniform
key. The inquisitor can reveal the hidden string by guessing either
the key or the string. One might suspect that either the key or
the string is necessarily more susceptible to being guessed, but
the result is more subtle.

Figure \ref{fig:nonconvex} plots the rate functions for guessing
each of the user's strings individually as well as the rate function
for guessing one out of two, determined by equation \eqref{eq:Iopt},
which in this case is the minimum of the two rate function where
they are finite. The y-axis is the exponential decay-rate in string
length $k$ of the likelihood of identification given approximately
$\exp(k x)$ guesses, where $x$ is on the x-axis, have been made.
The rate function reveals that if the inquisitor identifies one of
the strings quickly, it will be the non-uniform byte string, but
after a certain number of guesses it is the key, the uniform bit
string, that is identified.

Attempting to obtain this result by taking the Legendre Fenchel
transform of the sCGF identified in \cite{Merhav99} results in the
convex hull of this non-convex function, which has no real meaning.
This explains the necessity for the distinct proof approach taken
here if one wishes to develop estimates on the guesswork distribution
rather than its moments.

\section{Identical Statistics Examples}
\label{sec:ident}

When the string statistics of users are asymptotically the same,
the resulting multi-user guesswork rate functions are convex by
Corollary \ref{cor:same}, and the r\^ole of specific Shannon entropy
in analyzing expected multi-user guesswork appears.  This is the
setting that leads to the results in Section \ref{sec:firstexample}
where it is assumed that character statistics are i.i.d., but not
necessarily uniform.

An alternate means of departure from string-selection uniformity
is that the appearance of characters within the string may be
correlated. The simplest model of this is where string symbols are
governed by a Markov chain with arbitrary starting distribution and
transition matrix
\begin{align*}
\left(
	\begin{array}{cc}
	1-a & a \\
	b & 1-b
	\end{array}
\right),
\end{align*}
where $a,b\in(0,1)$. The specific R\'enyi entropy of this character
source can be evaluated, e.g. \cite{Malone042}, for $\beta\neq1$ to be
\begin{align*}
R(\beta) =& \frac{1}{1-\beta}\log
	\left(
	(1-a)^\beta+(1-b)^\beta \right. \\
	& \left.+
	\sqrt{((1-a)^\beta-(1-b)^\beta)^2 + 4(ab)^\beta }
	\right)
	-\frac{1}{1-\beta}
\end{align*}
and $R(1)$ is the Shannon entropy
\begin{align*}
R(1) &=
\frac{b}{a+b}H(a)+\frac{a}{a+b}H(b),
\end{align*}
where $H(a) = -a\log(a)-(1-a)\log(1-a)$.

Figure \ref{fig:gap_mark} shows $R(1/2)-R(1)$ the difference between
the average guesswork growth rate for a single user system versus
one for an arbitrarily large number of users as $a$ and $b$ are
varied. Heavily correlated sources or those with unlikely characters
give the greatest discrepancy in security.

\begin{figure}
\begin{center}
\includegraphics[scale=0.46]{sec_gap_markov}
\end{center}
\caption{Markovian string source over a binary alphabet $ {\mathbb{A} }=\{0,1\}$
with $a$ being the probability of a 1 after a 0 and $b$ being the
probability of a 0 after a 1. The plots shows the difference in
average guesswork exponent for a single user system and a system
with an arbitrarily large number of users, a measure of computational
security reduction.
}
\label{fig:gap_mark}
\end{figure}
If $a=b$, then the stationary likelihood a symbol is a $0$ or $1$
is equal, but symbol occurrence is correlated. In that setting, the
string source's specific R\'enyi entropy gives for $\beta\neq1$
\begin{align*}
R(\beta) =& \frac{1}{1-\beta}\log
	\left(
	(1-a)^\beta + a^\beta
	\right),
\end{align*}
which is the same as a Bernoulli source with probability $a$ of one
character. Thus the results in Section \ref{sec:firstexample} can
be re-read with the Bernoulli string source with parameter $p=a$
substituted for a Markovian string source whose stationary distribution
gives equal weight to both alphabet letters, but for which character
appearance is correlated.

\section{Discussion}
\label{sec:conc}

Since Massey \cite{Massey94} posed the original guesswork problem
and Arikan \cite{Arikan96} introduced its long string asymptotic,
generalizations have been used to quantify the computational security
of several systems, including being related to questions of loss-less
compression. Here we have considered what appears to be one of the
most natural extensions of that theory, that of multi-user computational
security. As a consequence of the inherent non-convex nature of
the guesswork rate function unless string source statistics are
equal for all users, this development wasn't possible prior to the
Large Deviation Principle proved in \cite{Christiansen13}. The
results therein themselves relied on the earlier work that determined
the scaled cumulant generating function for the guesswork for a
broad class of process \cite{Arikan96,Malone042,Pfister04,Hanawal11}.

The fact that rate functions can be non-convex encapsulates that
distinct subsets of users are likely to be identified depending on
how many unsuccessful guesses have been made. As a result, a simple
ordering of string guessing difficulty is inappropriate in multi-user
systems and suggests that quantification of multi-user computational
security is inevitably nuanced.

The original analysis of the asymptotic behavior of single user
guesswork identified an operational meaning to specific R\'enyi
entropy. In particular, the average guesswork grows exponentially
in string length with an exponent that is the specific R\'enyi
entropy of the character source with parameter $1/2$. When users'
string statistics are the same, the generalization to multi-user
guesswork identifies a surprising operational r\^ole for specific
R\'enyi entropy with parameter $n/(n+1)$ for each $n\in {\mathbb{N} }$ when
$n$ is the excess number of strings that can be guessed. Moreover,
while the specific Shannon entropy of the string source was found
in the single user problem to have an unnatural meaning as the
growth rate of the expected logarithm of the guesswork, in the
multi-user system it arises as the universal lower bound on the
average guesswork growth rate.

For the asymptote at hand, the key message is that there is a law
of diminishing returns for an inquisitor as the number of users
increases. For a multi-user system
designer,
in contrast to the single character, single user system
introduced in \cite{Massey94},
Shannon entropy is the appropriate measure of
expected guesswork for systems with many users.

Future work might consider the case where the $V$ strings are not
selected independently, as was assumed here, but are instead linear
functions of $U$ independent strings. A potential application of
such a case, suggested by Erdal Arikan (Bilkent University) in a
personal communication, envisages the use of multi-user guesswork
to characterize the behavior of parallel concatenated decoders
operating on blocks of convolutionally encoded symbols passed though
a preliminary algebraic block Maximum Distance Separable (MDS) code,
e.g. \cite{shu2004}. The connection between guessing and convolutional
codes was first established by Arikan \cite{Arikan96}.

Decoding over a channel may, in general, be viewed as guessing a
codeword that has been chosen from a list of possible channel input
sequences, given the observation of an output sequence formed by
corrupting the input sequence according to some probability law
used to characterize the channel, e.g \cite{Christiansen13b}.
Considering sequential decoding of convolutional codes, first
proposed by Wozencraft \cite{Wozencraft57}, that guessing may
constitute an exploration along a decision tree of the possible
input sequences that could have led to the observed output sequence,
as modeled by Fano \cite{Fano63}.  If the transmitted rate, given
by the logarithm of the cardinality of possible codewords, falls
below the cut-off rate, then results in \cite{Arikan96} prove that
the guesswork remains in expectation less than exponential in the
length of the code. Beyond the cut-off rate, it becomes exponentially
large. One may view such a result as justifying the frequent use
of cut-off rate as as a practical, engineering characterization of
the limitations of block and convolutional codes.

Consider now the following construction of a type of concatenated
code \cite{shu2004}, which is a slight variant of that proposed by
Falconer \cite{Falconer67}. The original data, a stream of i.i.d.
symbols, is first encoded using an algebraic block MDS code. For a
block MDS code, such as a Reed-Solomon code \cite{shu2004}, over a
codeword constituted by a sequence of $V$ symbols, correct reception
at the output of any $U$ symbols from the $V$ allows for correct
decoding, where the feasibility of a pair of $V$ and $U$ depends
on the family of codes. For every $U$ input symbols in the data
stream, $V$ symbols are generated by the algebraic block MDS code.
Note that these symbols may be selected over a set of large
cardinality, for instance by taking each symbol to be a string of
bits. As successive input blocks of length $U$ are processed by the
block MDS code, these symbols form $V$ separate streams of symbols.
Each of these $V$ streams emanating from the algebraic block MDS
code is coded using a separate but identical convolutional encoder.

The $V$ convolutional codewords thus obtained are dependent, even
though any $U$ of them are mutually independent. This dependence
is imputed by the fact that the $V$ convolutional codewords are
created by $U$ original streams that form the input of the block
MDS encoder. The $V$ convolutional codewords constitute then the
inputs to $V$ mutually independent, Discrete Memoryless Channels
(DMCs), all governed by the same probability law. In Falconer's
construct, such parallel DMCs are embodied by time-sharing equally
a single DMC. While Falconer envisages independent DMCs governed
by a single probability law, as is suitable in the setting of
interleaving over a single DMC, we may readily extend the scheme
to the case where the parallel DMCs have different behaviors. Such
a model is natural in wireless settings where several channels are
used in parallel, say over different frequencies. While the behavior
of such channels is often well modeled as being mutually independent,
and the channels individually are well approximated as being DMCs,
the characteristics of the channels, which may vary slowly in time,
generally differ considerably from each other at any time.

Decoding
uses the outputs of the $V$ DMCs as follows. For each DMC,
the output is initially individually decoded using sequential
decoding so that, in the words of Falconer, "controlled by the Fano
algorithm, all $[V]$ sequential decoders simultaneously and
independently attempt to proceed along the correct path in their
own trees". The dependence among the streams produced by the original
application of the block MDS code entails that, when $U$ sequential
decoders each correctly guesses a symbol, the correct guesses
determine a block of $U$ original data symbols. The latter are
communicated to all remaining $V-U$ sequential decoders, eliminating
the need for them to continue producing guesses regarding that block
of $U$ original data symbols. The sequential decoders then proceed
to continue attempting to decode the next block of $U$ original
data symbols. This scheme allows the $U$ most fortunate guesses out
of $V$ to dominate the performance of the overall decoder. A
sequential decoder that was a laggard for one block of the original
$U$ symbols may prove to be a leader for another block of $U$
symbols.

\section*{Acknowledgments:}
The authors thank Erdal Arikan (Bilkent University) for informative
feedback and for pointing out the relationship between multi-user
guesswork and sequential decoding.
They also thank the anonymous reviewers for their feedback
on the paper.

redpajama_set_name: RedPajamaArXiv


The School of Labor and Employment Relations at The University of Illinois anticipates inviting applications for the position of Post-Doctoral Scholar with the Project for Middle Class Renewal. This is a 24-month position that begins on August 24, 2016. The Project for Middle Class Renewal was established in the fall of 2015 with the goal of promoting policy analysis, scholarly research and scholar-practitioner exchanges on employment related issues. The Project's focus is broadly on employment policy, including the labor market, precarious work, industry studies, labor unions, training, education, and collective bargaining. Candidates should possess a Ph.D. in a relevant discipline, or a J.D., earned in the last three years, as well as evidence of an emerging research program relevant to the Project's interests. Scholars will receive salary, benefits, and a research/travel fund to support their work.
Postdoctoral candidates will be expected to teach one course each semester in the Global Labor Studies Program. Review of applications will begin on March 15, 2016 and continue until the position is filled.
Policy Analyst/Director Job Qualifications: PhD with coursework in economics, political science, public policy, labor relations, sociology, or related field. Knowledge of labor unions, collective bargaining, labor market public policy and economic trends. Ability to analyze and project trends affecting workers, employment relations, the labor market, labor unions, employment related policy, and the collective bargaining process. Capacity to work with and analyze large observational datasets, such as the Current Population Survey (CPS) and conduct impact analysis using IMPlan or other similar tools. Ability to work independently and collaboratively to initiate and execute projects. Effective communications skills, both orally and in writing, so that complex technical information is translated into understandable formats. Excellent quantitative skills and advanced use of personal computers and database software needed. Some travel required.


. 🍀Features all letters and numbers in various fun colors.
🍀Helps children learn while still having fun.
🍀Extremely durable, water resistant, and easy to clean.
📦POSTAGE RM8 SM, RM23 SS .
🐇New Mini Kids Motor .
🍀Color : Red & Yellow .


text:
Eisenhower Presidential Museum Exhibits Open to Public
On July 29, the Eisenhower Presidential Museum opened to the public with all new exhibits after undergoing more than a year of renovation. Using newly digitized and never-before-seen footage from the National Archives and Records Administration, new mini-theaters offer visitors the opportunity to hear Ike's words firsthand on a variety of events and issues from D-Day to world peace.
"Our team is excited to share this updated story with our visitors. We are thrilled to feature the holdings of the collection, not only here in Abilene, but also from the National Archives in Washington, DC. These resources allowed us to create a custom exhibit script using Ike and Mamie's own words and really connect with the visitor on a personal level," stated Dawn Hammatt, Director, Eisenhower Presidential Library and Museum.
The Museum renovation was the result of a successful five-year $12,250,000 capital campaign conducted by the Eisenhower Foundation. Donors from all 50 states contributed to this grassroots effort. Lead donors to the campaign included the Hall Family Foundation, the Dane G. Hansen Foundation, the William T. Kemper Foundation, and The Sunderland Foundation. For a complete list of campaign contributors, please visit the "Support" section of our website.
"We are truly grateful for your contributions. Dwight D. Eisenhower: A Legacy of Leadership was the largest fundraising campaign in the Eisenhower Foundation's 74-year history, and the first comprehensive exhibit renovation in more than 45 years," added Meredith Sleichter, Executive Director, Eisenhower Foundation. "Because of your financial support, we are now welcoming guests to a new, engaging experience at the Eisenhower Presidential Museum in Abilene, Kansas — Ike's hometown."
When speaking about his hometown in London, England, after World War II, Ike said, "I come from the very heart of America." To echo this sentiment which Ike often shared with the world, the new Museum features entry and exit galleries that incorporate this quote in their titles. To borrow from President Nixon's moving eulogy for General Eisenhower, "Perhaps no one sentence could better sum up what Dwight Eisenhower meant to a whole generation of Americans…And with his own great qualities of heart he personified the best in America."
We are "IKE"cited to reintroduce this generation to the heart of Dwight D. Eisenhower and to host thousands of visitors to his hometown of Abilene, Kansas — "the very heart of America."

redpajama_set_name: RedPajamaCommonCrawl


text:
Thoroughly Modern Millie opens July 13
Thoroughly Modern Millie, a Tony award winning musical, is set to be the EVSC and Public Education Foundation's summer show.
Thoroughly Modern Millie opens July 13 Thoroughly Modern Millie, a Tony award winning musical, is set to be the EVSC and Public Education Foundation's summer show. Check out this story on courierpress.com: https://www.courierpress.com/story/entertainment/events/2017/07/09/thoroughly-modern-millie-opens-thursday/432852001/
sarah.loesch@courierpress.com Published 8:06 p.m. CT July 8, 2017
Gracie Schmidt, center, portrays Millie Dillmount in the Evansville Vanderbugh School Corporation and Public Education Foundation's production of "Thoroughly Modern Millie" and is overlooked by love interest Jared Hoover (Trevor Graydon), right, and best friend Catherine Wessel (Miss Dorothy) during rehearsal at the Old National Events Plaza..(Photo: DENNY SIMMONS / COURIER & PRESS)Buy Photo
Gracie Schmidt relates to the opening number of "Thoroughly Modern Millie" the most.
Schmidt, who plays lead Millie Dillmount, sings "Not For the Life of Me," opening the show with a number that briefly explains her character's desire to make a life of her own.
"Thoroughly Modern Millie," a Tony Award-winning musical, is the Evansville Vanderburgh School Corporation and Public Education Foundation's summer musical. The performances begin at 7 p.m. Thursday and run through July 16 at 2 p.m.
Rehearsal for the Evansville Vanderbugh School Corporation and Public Education Foundation's production of "Thoroughly Modern Millie" is underway at Old National Events Plaza Friday night. (Photo: DENNY SIMMONS / COURIER & PRESS)
Schmidt, 16, said there have been ups and downs to playing Millie, but when it comes down to it, she and the character are quite similar.
"Millie is literally me, except I haven't found my true love yet," she said. "That's the hardest part for me to play."
The musical follows Schmidt's character as she travels from Kansas to New York with the hopes of making something of herself and ultimately finding a rich man to marry. As other characters enter and friendships develop, Millie's attempt to marry for money becomes complicated.
Gracie Schmidt portrays Millie Dillmount who begins to fall for Colton Colbert (Jimmy Smith) during a rehearsal for "Thoroughly Modern Millie." (Photo: DENNY SIMMONS / COURIER & PRESS)
One of those characters is Millie's best friend, Miss Dorothy, portrayed by 15-year-old Catherine Wessel. She comes from a wealthy upbringing and travels to New York in hopes of living a middle-class life.
Wessel said she loves her character, and the portrayal is a fun one to act out on stage.
"It's so much fun getting to be over the top about everything and having to have this sweet accent," she said.
Wessel said the show itself is packed with big musical numbers, enormous moments and tons of laughs, but what can really bring people out is the knowledge that the whole cast is working incredibly hard.
Nicole Bittner, 14, rehearses some dance steps backstage during a rehearsal for the Evansville Vanderbugh School Corporation and Public Education Foundation's production of "Thoroughly Modern Millie." It opens Thursday. (Photo: DENNY SIMMONS / COURIER & PRESS)
"You can really see all of the effort that has been put in," she said. "We've really grown, and the show is huge."
That hard work and professionalism is part of what has kept Jared Hoover coming back for five summer musicals.
Hoover, who plays Trevor Graydon, Millie's boss in New York, said there is nowhere else in Evansville where actors and actresses can get this type of training or experience.
The 18-year-old started voice lessons when he was in fourth grade, and he's been singing and performing ever since. And now his experience over the years has led him to pursue acting in college and professionally.
"It's a unique process you aren't going to find anywhere else other than here," Hoover said.
This show, in particular, Hoover said allows the cast members to get deeper into acting and their characters since it is a Broadway show.
"I feel like this is as close to Broadway as you're going to get in the Midwest," he said. "I don't mean that lightheartedly at all."
Adult set crew members, from left, McKailah Hardin, Zach Krietemeyer and Jordan Kluesner create the lobby in the Evansville Vanderbugh School Corporation and Public Education Foundation's production of "Thoroughly Modern Millie." (Photo: DENNY SIMMONS / COURIER & PRESS)
He said the cast is made up of the best people from around the Tri-State, and it's one of the best shows he has been a part of.
Schmidt also said the cast has put in a lot of hard work, and the group decided to make it a goal to be close this year.
For Schmidt, who started acting in fifth grade, the stage is where she feels most comfortable. She said she is often introverted, but on stage she is able to entertain and connect with people possibly making their lives better.
"I'm sharing my passion, so it's just this home feeling," she said.
Schmidt said people should buy a ticket to the show because it has a powerful message about coming from anywhere and making something of yourself.
The orchestra rehearses in the basement of Old National Events Plaza for the Evansville Vanderbugh School Corporation and Public Education Foundation's production of "Thoroughly Modern Millie." (Photo: DENNY SIMMONS / COURIER & PRESS)
"You don't have to be wealthy, you don't have to be any of this and it turns out good," she said. "It's saying follow your dreams."
What: "Thoroughly Modern Millie"
When: 7 p.m. Thursday through Saturday, 2 p.m. Sunday
Where: Aiken Theatre at Old National Events Plaza
Cost: $6.50-$18.50, tickets can be ordered at the Old National Events Plaza box office or at 812-435-5770 ext. 211.
Read or Share this story: https://www.courierpress.com/story/entertainment/events/2017/07/09/thoroughly-modern-millie-opens-thursday/432852001/
Crossroads IGA: A new type of grocery store for Evansville
Taqueria Co. returns and brings new burger joint to mall
Stay Hungry: WingFest, PAAWS puppies and more
Latest food and restaurant inspections
Review: EPO' concert brings audience to its feet
Can you beat this burger challenge at Prime Time?


Show off your Virginia Cavaliers pride as you enjoy your beverage of choice with this trendy 27oz. Chaser tumbler!
ORCA_Navy_Virginia_Cavaliers_27oz._Silver_Logo_Chaser_Tumbler http://images.fanatics.com/lf http://dmimages.ff.p10/chains/2808925.txt false We are unable to customize this item with the text you have entered. Please try a different entry again. Your current entry cannot be processed due to guidelines for past and present player names. Please create a new entry.


I guess it all started with my mum, Jamaican born but moved to England at 11 oldest of 4 she had to be the toughest and most flexible adapting to a new country climate and attitude Mum had everything 2nd hand or hand me downs from neighbours or cousins whilst adjusting to life in England. So when I was born mum said to herself no child of mine will ever have 2nd hand clothes or want for anything and I never did even now. I thank my mum for that statement and believe that has set me up for who and what I am today.
I remember looking back through pictures and seeing how sharp I looked. Usually jumper, polo shirt, and trousers. Very preppy who said Kanye made College drop out style cool!! I was a mini Carlton Banks, (before Alfonso Ribero gave us his most classic performance), with a slick bow tie and penny loafers to this day I still prefer a bow tie to a traditional tie.
Fashion wasn't a real thing, it was just what we liked, we wore and had the confidence to wear it. I saw my mum as the icon always looking sharp rocking her own style. I guess coming from the Caribbean you had to work harder, look smarter than anyone else, to be taken seriously you already stand out from the crowd so why not really stand out bring the native vibe to English attire.
I was the first grandchild and nephew so was well looked after and dress to impress all the time, without thinking it's just what we did, it's not just Sunday best everyday counts. I recently watched the film on Jesse Owens life and I will never forget this quote "a man has to present an image to the world". And it really has stuck with me and made sense to my journey.
I was never the most talkative or confident in groups so my fashion talked for me, putting clothes together experimenting with colour, pattern and textures was the real me crying out. I didn't care what people thought, I was curious about fashion and confident I can carry it off. I won't single out specific looks but it goes back to not following a trend but wearing what I felt I wanted to wear, I always used fashion as my thing to start a conversation knowing I was confident in my look gave me confidence in myself to talk, express myself and ultimately forge a career.
The old saying is don't judge a book by its cover but we all ultimately do, whether it's someone with a beard and rucksack to a banker in a pinstripe suit. You are all judging and being judged, it's the first thing people see, before you've even opened your mouth so you better make it count. I did, I have and will continue to be curious about clothes, my heritage, my friendships, my family, my career and reinforce the values that have put me on this path. But without having the confidence in yourself people will see through it. Trends come and go brands evolve and shapeshift to fit within the world but style and confidence is what really matters. My mum brought that Jamaican swagger I edited the English gent and created a curious boy.
Follow are journey, engage with our style and inspire the future.


Ivana De Domenico is based in Salt Lake City, Utah. Ivana completed her Bachelors degree in Biological Science in 2002 at the University of Messina, Sicily. Her thesis described the purification and characterization of recombinant Caulobacter crescentus Cu/Zn superoxide dismutase (De Domenico I et al Biochim Biophys Acta, 2006). In the same year, Ivana De Domenico matriculated into the Cellular, Molecular Biology and Biotechnology graduate program at the University of Messina, Italy, completing her Ph.D. in the laboratory of Dr. Giovanni Musci in 2005.
As part of this program, Ivana De Domenico worked at the University of Utah, Salt Lake City. Her early work focused on iron metabolism with a particular interest in hepcidin, ferroportin (Fpn) and ferritin. Hepcidin is a peptide hormone transcriptionally regulated by iron, inflammation and hypoxia. Hepcidin was originally described as a defensin with potent antimicrobial properties but its main role is in iron transport. Hepcidin binds to its only known receptor, ferroportin (Fpn) an iron exporter protein, and causes its internalization and degradation. Ivana De Domenico experiments described the interaction of these two proteins how the phosphorylation of Fpn lead to the receptor's activation and degradation led to several important publications (De Domenico I, et al Mol Biol Cell, 2008; De Domenico et al PNAS, 2009; De Domenico et al JCI, 2010). This work led to the development of a validated assay for the detection of hepcidin in both mice and humans (De Domenico I et al, Cell Metabol, 2008).
Hepcidin secreted in high amounts leads to iron-limited-erythropoiesis, a condition commonly associated with the anemia of inflammation (aka. anemia of chronic disease). Hepcidin secretion is increased in subjects with chronic kidney diseases, rheumatic diseases, malignancies and bacterial infections. Subjects with these diseases commonly have anemia of inflammation. This interest led me to showed that Borrelia burgdorferi, the bacteria that causes Lyme disease, increases hepcidin secretion through activation of Toll-like receptor (TLR) 4 (Koening C et al. Blood, 2009). Further work with Mycoplasma arthritidis, a bacterium that causes arthritis in mice, showed hepcidin secretion could also be activated through other TLRs (Koening et al. J Inflammation, 2009). Serum hepcidin levels were inversely correlated with serum iron values and had an important role in the anemia that developed in infected mice.
Others showed that hepcidin had antimicrobial properties suggesting that the peptide had effects beyond iron transport. Ivana De Domenico confirmed these findings by showing iron-loaded macrophages change their transcriptional response when cultured with hepcidin. These experiments led to the unexpected finding that hepcidin also had anti-inflammatory effects. In a manuscript published in The Journal of Clinical Investigation in 2010, she showed that mice injected with hepcidin could survive lethal injections of LPS. Ivana De Domenico also showed that the protective effects of hepcidin were through down-regulation of proinflammatory cytokines. These findings have been corroborated by others and led to an NIH grant awarded to Dr. Ivana De Domenico to study transcriptional regulation of Fpn.
Growing up in a European family that enjoyed traveling enabled Ivana De Domenico to appreciate different cultures at a very early age. Whether she was learning to ski in Northern Italy at the age of 5, or walking the beaches of southern Spain just a few years later, Ms. De Domenico somehow knew that she would become accustomed to living as a globetrotter.
Ivana De Domenico currently lives in the United States of America; however, in her three and a half decades of life, she has been to nearly all the continents of the world (with the exception of Antarctica), though there are so many places she still hopes to visit.
Although traveling is one of Ivana De Domenico's many interests and hobbies, she also considers it a serious career. In reality, Ivana understands travel as a way to enrich her life and become a more global citizen. Ms. De Domenico fully immerses herself in her new environment whether she is staying for a short time, or for a prolonged sabbatical. Ivana researches her destinations in advance in an effort to learn the languages and ways of life with the hope of truly being lost in the crowd of her temporary home. Ivana De Domenico believes that the only way to truly appreciate the world and its beauty are to walk the streets with the people who live there.


text:
8. A secondary-trisomic like plant found in rice
Osamu IDETA, Atsushi YOSHIMURA and Nobuo IWATA
Faculty of Agriculture, Kyushu University, Fukuoka, 812 Japan
Studying chromosomal assignment of RFLP linkage groups (Ideta et al. 1990), we found a variant in the F1 plants derived from a cross between primary trisomics triplo 8 originated from a Japonica variety Nipponbare and an Indica variety IR24. The variant resembled the hybrid triplo 8 morphologically, but differed in some respects. The variant showed a low plant height, short panicles, slightly slender grains and a very low seed fertility. We examined chromosome configurations at metaphase I of the variant and compared with those in the hybrid triplo 8 (Table 1). A trivalent or a univalent was observed in each cell of the variant. The frequency of trivalent in the variant was lower than that in the hybrid triplo 8. These morphological and microscopic observations showed that the variant was a kind of trisomics related to triplo 8 with some chromosomal alternation in the extra chromosome.
Table 1. Chromosome configuration at metaphase I in the hybrid primary
trisomics and a related variant derived from the cross of Japonica primary
trisomics triplo 8/IR 24
Chromosome configuration at metaphase I       Number of cells
=========================================      observed
11 II +1 III       12 II + 1 I
Hybrid triplo 8          27                 25                     52
Variant                  13                 28                     41
Fig. 1A and B. RFLP gene dosage analysis of the variant by using 6 clones mapped on chromosome 8. A) Summary of the RFLP analysis. Boxes reveal the loci of the RFLP clones which showed more increased dosage effect. Map distance (cM) and RFLP loci mapped on chromosome 8 (Saito et al. 1991) are shown in the left and right, respectively. B) Autoradiograms derived from probing Npb 126 and 68. P1: triplo 8, P2: IR24, lane 1: hybrid disomics, lane 2: hybrid triplo 8, lane 3: variant.
In order to detect the rearrangement of the extra chromosome, we performed RFLP gene dosage analysis using 6 RFLP clones mapped on chromosome 8 following the methods given by McCouch et al. (1988) and Ideta et al. (1990). The RFLP clones were due to Saito et al. (1991). The result of the RFLP analysis is summarized in Fig.1A with two photos in Fig. 1B. When probed with RFLP clones which are located on the extra chromosome, the gene dosage effect in hybrid primary trisomics is expected as follows: The ratio of signal intensities of trisomic fragment (P1 band in Fig. 1B) to disomic fragment (P2 band in Fig. 1B) is 2:1 theoretically. For RFLP clones, Npb 56, 126 (upper photograph in Fig. 1B) and 398, this was observed in the hybrid triplo 8, but was not observed in the variant. While for Npb 41, 38 and 68 (lower photograph in Fig. 1B), the hybrid triplo 8 showed the expected gene dosage effect but the variant showed a more increased gene dosage effect. The ratio of signal intensities of the variant fragments appeared to be 3:1. These results suggested that the chromosomal region from XNpb 68-1 to 41 on RFLP linkage map of chromosome 8 was duplicated in the extra chromosome of the variant.
Secondary trisomics accidentally arise in the progenies of primary trisomics (Khush 1973). The phenomena observed in the variant agreed with those in secondary trisomics. Therefore, the variant appeared to be secondary trisomics. Since the position of the centromere on the RFLP linkage map is uncertain, we consider the variant as a secondary-trisomic-like-plant.
Ideta, O., S. Yoshimura, A. Yoshimura, A. Saito, M. Kawase, N. Kishimoto, M. Yano, M. Nakano, T. Ogawa, M. Nakagahra and N. Iwata, 1990. Assignment of rice RFLP clones to their respective chromosomes by using gene dosage effect in hybrid primary trisomics. Jpn. J. Breed. 40 (Suppl. 1): 466-467 (in Japanese).
Khush, G. S., 1973. Cytogenetics of Aneuploids. Academic Press, New York and London. 301 pp.
McCouch, S. R., G. Kochert, Z. H. Yu, Z. Y. Wang, G. S. Khush, W. R. Coffman and S. D. Tanksley, 1988. Molecular mapping of rice chromosomes. Theor. Appl. Genet. 76: 815- 829.
Saito, A., M. Yano, N. Kishimoto, M. Nakagahra, A. Yoshimura, K. Saito, S. Kuhara, Y. Ukai, M. Kawase, T. Nagamine, S. Yoshimura, O. Ideta, R. Ohsawa, Y. Hayano, N. Iwata and M. Sugiura, 1991. Linkage map of restriction fragment length polymorphism loci in rice. Jpn. J. Breed. 41: 665-670.


Last minute in St. Constantine & Elena, Bulgaria. St. Constantine & Elena last minute offers 2019.
Check out our last minute discounts and special offers in St. Constantine & Elena, Bulgaria. Whether it's a spur of the moment decision or you're just waiting for a bargain, last minute holidays are an easy and convenient way to get away. Keep visiting to catch the latest last minute holiday deals in St. Constantine & Elena as they become available. Leaving things until the last minute could be the best decision for your holiday in St. Constantine & Elena in Bulgaria.


There is no shortage of Korean restaurants that serve locally grown vegetables in the area. If you want something other than rice, though, your pickings are pretty slim. There are a handful of American-style fast-food restaurants in downtown Yeongju-si (the likes of Domino's Pizza and Lotteria hamburgers), but you'll find more Korean joints.
The places around Buseoksa, such as Pusoeksa Shikdang (tel. 054/633-3317) or Myeongseong Shikdang (tel. 054/633-3262), specialize in sanchae bibimbap.
The restaurants in the Sosu Seowon area specialize in traditional Korean food. A good one to try is the Cheongdari Old House (tel. 054/633-4288), where you can get a meal with vegetables usually prepared for traditional rituals.


text:
Security tight ahead of key Catalan parliamentary address
Catalan regional President Carles Puigdemont speaks on the phone just before taking lunch inside the Palau de la Generalitat in Barcelona, Spain, Tuesday Oct. 10, 2017, which is the seat of the Catalan government. Puigdemont plans to address the Catalan parliament on Tuesday evening in a session that some have portrayed as the staging of an independence declaration for the northeastern region of 7.5 million, although others have said the move would only be symbolic. (AP Photo/Emilio Morenatti)
Catalonia's regional leader is due to address parliament in a highly anticipated session that could spell the birth of a new republic, marking a critical point in the standoff between separatists and Spain's central authorities.
Security is tight in Barcelona and police cordoned off a park surrounding the legislative building where Catalan president Carles Puigdemont is expected to walk a fine line when he addresses regional legislators.
The speech will need to appease the most radical separatist-minded supporters of his ruling coalition, but Sr Puigdemont faces shutting down any possibility of negotiating with Spain if he adopts a hard line.
The Catalan leader has not revealed the precise message he will deliver in the address, but separatist legislators and activists have said they will not be satisfied with anything short of an independence declaration.
A full declaration of secession - or an outright proclamation of a new Catalan republic - would meet fierce opposition by central Spanish authorities, who could take the unprecedented step of suspending the self-government of Catalonia and taking over some or all powers in the region.
Sr Puigdemont himself could end up in prison.
Some 2.3 million Catalans - 43% of the electorate in the north-eastern region - voted in the October 1 independence referendum, which the Spanish government said was illegal.
Regional authorities say 90% who voted were in favour and declared the results of the vote valid.
The ballot was marred by violence as riot police tasked with stopping the voting clashed with voters, leaving hundreds injured.
The political deadlock has plunged the country into its deepest political crisis in more than four decades, since democratic rule was restored following the dictatorship of General Francisco Franco.
In the streets of Barcelona, expectations were divided between those who want to see the birth of a new nation and others opposed to the idea. Some feared a drastic backlash from the Spanish central authorities.
The Catalan parliament's governing board acknowledged on Tuesday morning it had received the results in last week's disputed independence referendum, but a parliamentary official said the board refrained from putting the results through normal parliamentary procedures to elude any legal problems, because the referendum and its legal framework have been suspended by the national Constitutional Court.
Hundreds of thousands have turned out for street protests in Barcelona and other towns in the past month to back Catalan independence and protest against police violence during the vote. Those committed to national unity have also staged separate, large-scale rallies.
The tension has impacted the economy, with dozens of companies already relocating their corporate address away from the troubled region to remain under Spanish and European laws if Catalonia manages to secede.
AP Photo/Emilio Morenatti
'Nothing is impossible', Barnier says of UK/EU treaty on Gibraltar


Pin Teddy Bear Medium Clutch crafted in saffiano with pin bear motif print, is the bearer of light moods and serious style. Featuring top tab zip closure, detachable wristlet, signature lining, internal zip pocket, and silver tone hardware. Signature dust bag included.