TITLE: Efficient approximation method
QUESTION [0 upvotes]: We have an equation of the form:
$P(x)=(1-xv)(1-xw)(1-x)^{n-2}-u$
$n≥2$ and $n$ belongs to the set of positive integers.
$0<u<1$.
$0<v≤1$.
$0<w≤1$.
$0<x≤1$.   ($x>1$, when $n=2$ and $v,w<<1)$ which is very rare.
For this equation it seems, a closed form expression for $x$ is not possible, so what would be the best, most efficient method of approximation, Newton's method requires a lot of iterations and often it doesn't converges, so we need a method that's more robust, requires fewer iterations and would most probably converge, it doesn't matter how rigourous the method is. PS: We can actually make a pretty good guess of value of $x$ but it'll always be smaller than the accurate value.

REPLY [1 votes]: I prefer to add another answer because I do not know yet what could be the limitations of such an approach.
Assume that we can write
$$(1-x\,v)(1-x\,w)(1-x)^{n-2}\sim (1-x)^m$$
Expanding as series around $x=0$
$$\Delta=(1-x\,v)(1-x\,w)(1-x)^{n-2}-(1-x)^m$$
$$\Delta=(2 + m - n - v - w)\, x+O(x^2)\quad \implies m=n+u+w-2$$
Using this $m$
$$\Delta=\frac 12 [v(1-v)+w(1-w)]\,x^2+O(x^3)$$
Applied to the examples used in the previous answers

for the first case :  $m=2.3$ which leads to $x_0=0.632534$ (the exact solution being $0.624959$)
for the second case  :  $m=7.3$ which leads to $x_0=0.090583$ (the exact solution being $0.090840$)

and this did not require the computation of any of the terms $x_R$, $f(x_R)$, $x_Q$, $f(x_Q)$, $x_P$.
Generating random numbers, some results (which look, at least to me, more than promizing)
$$\left(
\begin{array}{cccccc}
u & v & w & n & \text{first estimate} & \text{exact solution} \\
 0.48 & 0.84 & 0.46 & 43 & 0.0173482  &  0.0172032 \\
 0.19 & 0.44 & 0.96 & 25 & 0.0664561  &  0.0658234 \\
 0.87 & 0.33 & 0.53 & 54 & 0.0026045  &  0.0026311 \\
 0.23 & 0.84 & 0.41 & 74 & 0.0200290  &  0.0198649 \\
 0.06 & 0.90 & 0.71 & 79 & 0.0355295  &  0.0351589 \\
 0.88 & 0.46 & 0.57 & 18 & 0.0072989  &  0.0074791 \\
 0.94 & 0.62 & 0.60 & 31 & 0.0020240  &  0.0020454 \\
 0.17 & 0.49 & 0.59 & 58 & 0.0307361  &  0.0305705 \\
 0.48 & 0.43 & 0.81 & 32 & 0.0231840  &  0.0232241 \\
 0.57 & 0.68 & 0.06 & 37 & 0.0156528  &  0.0156059 \\
 0.03 & 0.71 & 0.55 & 89 & 0.0392474  &  0.0389549 \\
 0.10 & 0.99 & 0.82 & 41 & 0.0560480  &  0.0548658 \\
 0.88 & 0.71 & 0.17 & 12 & 0.0115020  &  0.0116828 \\
 0.64 & 0.33 & 0.30 & 92 & 0.0048955  &  0.0049122 \\
 0.84 & 0.57 & 0.36 & 51 & 0.0034672  &  0.0034859 \\
 0.91 & 0.56 & 0.53 & 38 & 0.0025158  &  0.0025396 \\
 0.01 & 0.93 & 0.59 & 45 & 0.1002360  &  0.0983040 \\
 0.32 & 0.97 & 0.41 & 41  & 0.0282721  &  0.0278260 \\
 0.28 & 0.12 & 0.14 & 100 & 0.0128510  &  0.0128717 \\
 0.51 & 0.17 & 0.41 & 82  & 0.0082866  &  0.0083216
\end{array}
\right)$$
Edit
In view of these results, we can even do better.
Compute
$$\Phi(m)=\int_0^1\Big[(1-x\,v)(1-x\,w)(1-x)^{n-2}-(1-x)^m\Big]^2 \,dx$$ which does not make any problem. $\Phi'(m)=0$ implies the nasty equation in $m$
$$\frac{2 v w \left(3 (m+n)^2-1\right)-v (m+n+1)^2 (2 m+2 n-1)}{(m+n)^2 (m+n+1)^2}+$$ $$\frac{w
   (-2 m-2 n+1)}{(m+n)^2}+\frac{(m-n+2) (3 m+n)}{(2 m+1)^2}=0$$
Making $m=n+u+w-2+\epsilon$ and expanding as a series around $\epsilon=0$ to first order gives a longish but fully explicit expression
$$\epsilon(v,w,n)=\frac A {2B}$$ where
$$A=\frac{1-v}{2 n+v+w-3}+\frac{2 v-1}{2 n+v+w-2}-\frac{v}{2 n+v+w-1}+\frac{(v-1) (2
   n+v-2)}{(2 n+v+w-3)^2}-$$ $$\frac{2 \left(n (2 v-1)+(v-1)^2\right)}{(2 n+v+w-2)^2}+\frac{v
   (2 n+v-1)}{(2 n+v+w-1)^2}+\frac{1}{(2 n+2 v+2 w-3)^2}$$
and
$$B=\frac{1-v}{(2 n+v+w-3)^2}+\frac{2 v-1}{(2 n+v+w-2)^2}-\frac{v}{(2
   n+v+w-1)^2}+\frac{(v-1) (2 n+v-2)}{(2 n+v+w-3)^3}-\frac{2 \left(n (2
   v-1)+(v-1)^2\right)}{(2 n+v+w-2)^3}+\frac{v (2 n+v-1)}{(2 n+v+w-1)^3}+\frac{2}{(2 n+2 v+2 w-3)^3}$$
For the first terms of the above table, the first estimate is now
$$\{0.017205,0.065821,0.002631,0.019865,0.035158,0.007488,0.002046\}$$ which is much better.
Update
Working on a logarithmic scale, there is an explicit expression of $m$.
Minimizing
$$\Psi(m)=\int_0^1 \Big[\log(1-x\,v)+\log(1-x\,w)+(n-2-m)\log(1-x) \Big]^2\,dx$$ leads to
$$2(m-n)=\frac{1-v}v  \left(\text{Li}_2\left(\frac{v}{v-1}\right)+\log (1-v)\right)+$$
$$\frac{1-w} w  \left(\text{Li}_2\left(\frac{w}{w-1}\right)+\log (1-w)\right)$$
The function
$$g(t)=\frac{1-t} t  \left(\text{Li}_2\left(\frac{t}{t-1}\right)+\log (1-t)\right)$$ is very well approximated by its $[2,2]$ Padé approximant built around $t=\frac 12$.
If we make the very crude approximation
$$g(t)=-\left(\frac{\pi ^2}{12}+\log (2)\right)+\left(\frac{\pi ^2}{3}-2\right)
   \left(t-\frac{1}{2}\right)+O\left(\left(t-\frac{1}{2}\right)^2\right)$$
$$m=n +\left(\frac{\pi ^2}{6}-1\right) (v+w)+\left(1-\frac{\pi ^2}{4}-\log (2)\right)$$


TITLE: How to find the key matrix of a 2x2 Hill Cipher?
QUESTION [2 upvotes]: In the english language, the most common digraph is TH which is then followed by HE. In this particular example let's say the digraphs with the most frequencies are RH and NI. How would I find the a, b, c, and d values for the key matrix:
  \begin{pmatrix}a&b\\c&d\end{pmatrix}

We can split TH and HE into pairs \begin{pmatrix}R\\H\end {pmatrix} \begin{pmatrix}N\\I\end{pmatrix}
Which, when converted to their integer values, are equivalent to:
\begin{pmatrix}19\\07\end {pmatrix} \begin{pmatrix}07\\04\end{pmatrix}
If i'm not wrong here, I can use these values to solve for the values of a, b, c, and d. Unfortunately my use of matrix notation is limited and I fear that I would clog up the screen with my poor attempt so I'll just put the result of my work. I basically combined the key matrix of a, b, c, and d with the pairs TH and HE to get:
TH: $(19a+7b)$mod$26$ and $(19c + 7d)$mod$26$
HE: $(7a+4b)$mod$26$ and $(7c+4d)$mod$26$
Assuming this work is correct, I believe that I can just set these values equal to the values of RH and NI and solve for a, b, c, or d.
$19a + 7b = 17$ would be used to find the value of R. However, I'm not entirely sure if this is correct. I am also not entirely sure how I would proceed after creating this equation. Wouldn't I have to find the inverse instead of solving the equation?

REPLY [2 votes]: You assume that $TH \to RH$ and $HE \to NI$ under the Hill cipher.
Or in matrix notation:
$$\begin{bmatrix} a & b\\ c & d\end{bmatrix}\begin{bmatrix}19\\7 \end{bmatrix}= \begin{bmatrix}17\\7 \end{bmatrix}$$
and
$$\begin{bmatrix} a & b\\ c & d\end{bmatrix}\begin{bmatrix}7\\4 \end{bmatrix}= \begin{bmatrix}13\\8 \end{bmatrix}$$
or in one matrix notation:
$$\begin{bmatrix} a & b\\ c & d\end{bmatrix} \begin{bmatrix} 19 & 7\\ 7 & 4\end{bmatrix} = \begin{bmatrix} 17 & 13\\ 7 & 8\end{bmatrix}$$
which allows us to find the encryption matrix by
$$\begin{bmatrix} a & b\\ c & d\end{bmatrix} = \begin{bmatrix} 17 & 13\\ 7 & 8\end{bmatrix} {\begin{bmatrix} 19 & 7\\ 7 & 4\end{bmatrix}}^{-1}$$
The determinant of $\begin{bmatrix} 19 & 7\\ 7 & 4\end{bmatrix}$ is $19\cdot 4 - 7\cdot 7 = 1 \pmod{26}$, so the inverse exists and equals (using $-7 = 19 \pmod{26}$)
$$\begin{bmatrix} 4 & 19\\ 19 & 19\end{bmatrix}$$
This allows us to compute the encryption matrix, and then the decryption matrix.
Alternatively, as  $\begin{bmatrix} 17 & 13\\ 7 & 8\end{bmatrix}$ is also invertible (determinant $19$) we can find the decryption matrix also from (using  $A = BC \to A^{-1} = C^{-1}B^{-1}$ etc.)
$${\begin{bmatrix} a & b\\ c & d\end{bmatrix}}^{-1} = \begin{bmatrix} 19 & 7\\ 7 & 4\end{bmatrix} {\begin{bmatrix} 17 & 13\\ 7 & 8\end{bmatrix}}^{-1}$$ as well


text:
\begin{document}

\maketitle

\begin{abstract}
Choice functions constitute a simple, direct and very general mathematical framework for modelling choice under uncertainty.
In particular, they are able to represent the set-valued choices that typically arise from applying decision rules to imprecise-probabilistic uncertainty models.
We provide them with a clear interpretation in terms of attitudes towards gambling, borrowing ideas from the theory of sets of desirable gambles, and we use this interpretation to derive a set of basic axioms.
We show that these axioms lead to a full-fledged theory of coherent choice functions, which includes a representation in terms of sets of desirable gambles, and a conservative inference method.
\end{abstract}

\section{Introduction}

When uncertainty is described by probabilities, decision making is usually done by maximising expected utility.
Except in degenerate cases, this leads to a unique optimal decision.
If, however, the probability measure is only partially specified---for example by lower and upper bounds on the probabilities of specific events---this method no longer works.
Essentially, the problem is that two different probability measures that are both compatible with the given bounds may lead to different optimal decisions.
In this context, several generalisations of maximising expected utility have been proposed; see~\cite{troffaes2007} for an nice overview.

A common feature of many such generalisations is that they yield \emph{set-valued choices}: when presented with a set of options, they generally return a subset of them.
If this turns out to be a singleton, then we have a unique optimal decision, as before.
If, however, it contains multiple options, this means that they are incomparable and that our uncertainty model does not allow us to choose between them.
Obtaining a single decision then requires a more informative uncertainty model, or perhaps a secondary decision criterion, as the information present in the uncertainty model does not allow us to single out an optimal option.
Set-valued choice is also a typical feature of decision criteria based on other uncertainty models that generalise the probabilistic ones to allow for imprecision and indecision, such as lower previsions and sets of desirable gambles.

\emph{Choice functions} provide an elegant unifying mathematical framework for studying such set-valued choice.
They map option sets to option sets: for any given set of options, they return the corresponding set-valued choice.
Hence, when working with choice functions, it is immaterial whether there is some underlying decision criterion.
The primitive objects of this framework are simply the set-valued choices themselves, and the choice function that represents all these choices, serves as an uncertainty model in and by itself.

A major advantage of working with choice functions is that they allow us to impose axioms on choices, aimed at characterising what it means for choices to be rational and internally consistent; see for example the seminal work by Seidenfeld et al.~\cite{seidenfeld2010}.
Here, we undertake a similar mission, yet approach it from a different angle.
Rather than think of choice in an intuitive manner, we provide it with a concrete interpretation in terms of attitudes towards gambling, borrowing ideas from the theory of sets of desirable gambles \cite{couso2011:desirable,walley2000,cooman2010,cooman2011b}.
From this interpretation alone, and nothing more, we develop a theory of coherent choice that includes a full set of axioms, a representation in terms of sets of desirable gambles, and a natural extension theorem.

\iftoggle{arxiv}{In order to facilitate the reading, proofs and intermediate results have been relegated to the Appendix.}
{Due to length constraints, proofs have been relegated to the appendix of an extended arXiv version of this contribution~\cite{extended}.}

\section{Choice Functions}

A choice function $\choicefun$ is a set-valued operator on sets of options.
In particular, for any set of options $\optset$, the corresponding value of $\choicefun$ is a subset $\choicefun(\optset)$ of $\optset$.
The options themselves are typically actions amongst which a subject wishes to choose.
As is customary in decision theory, every action has a corresponding reward that depends on the state of a variable~$X$, about which the subject is typically uncertain.
Hence, the reward is uncertain too.
The purpose of a choice function is to represent our subject's choices between such uncertain rewards.

Let us make this more concrete.
First of all, the variable~$X$ takes values~$x$ in some set of states~$\states$.
The reward that corresponds to a given option is then a function $\opt$ on $\states$.
We will assume that this reward can be expressed in terms of a real-valued linear utility scale, allowing us to identify every option with a real-valued function on $\states$.\footnote{A more general approach, which takes options to be elements of an arbitrary vector space, encompasses the horse lottery approach, and was explored by Van Camp \cite{2017vancamp:phdthesis}. Our results here can be easily extended to this more general framework.}
We take these functions to be bounded and call them \emph{gambles}.
We use $\opts$ to denote the set of all such gambles and also let
\begin{equation*}
\posopts\coloneqq\cset{\opt\in\opts}{\opt\geq0\text{ and }\opt\neq0}
\text{ and }
\nonposopts\coloneqq\cset{\opt\in\opts}{\opt\leq0}.
\end{equation*}

 Option sets can now be identified with subsets of $\opts$, which we call \emph{gamble sets}.
 We restrict our attention here to \emph{finite} gamble sets and will use $\optsets$ to denote the set of all such finite subsets of $\opts$, including the empty set.

\begin{definition}[Choice function]\label{def:choicefunction}
A \emph{choice function} $\choicefun$ is a map from $\optsets$ to $\optsets$ such that $\choicefun(\optset)\subseteq\optset$ for every $\optset\in\optsets$.
\end{definition}

Gambles in $\optset$ that do not belong to $\choicefun(\optset)$ are said to be \emph{rejected}.
This leads to an alternative representation in terms of so-called rejection functions.

\begin{definition}[Rejection function]\label{def:rejectionfunction}
The \emph{rejection function} $\rejectfun[\choicefun]$ corresponding to a choice function $\choicefun$ is a map from $\optsets$ to $\optsets$, defined by $\rejectfun[\choicefun](\optset)\coloneqq\optset\setminus\choicefun(\optset)$ for all $\optset\in\optsets$.
\end{definition}
\noindent
Since a choice function is completely determined by its rejection function, any interpretation for rejection functions automatically implies an interpretation for choice functions.
This allows us to focus on the former.

Our interpretation for rejection functions now goes as follows.
Consider a subject whose uncertainty about $X$ is represented by a rejection function $\rejectfun[\choicefun]$, or equivalently, by a choice function $\choicefun$.
Then for a given gamble set $\optset\in\optsets$, the statement that a gamble $\opt\in\optset$ is rejected from $\optset$---that is, that $\opt\in\rejectfun[\choicefun](\optset)$---is taken to mean that \emph{there is at least one gamble $\altopt$ in $\optset$ that our subject strictly prefers over $\opt$}.

This interpretation is of course still meaningless, because we have not yet explained the meaning of strict preference.
Fortunately, that problem has already been solved elsewhere: strict preference between elements of $\opts$ has an elegant interpretation in terms of desirability~\cite{walley2000,quaeghebeur2015:statement}, and it is this interpretation that we intend to borrow here.
To allow us to do so, we first provide a brief introduction to the theory of sets of desirable gambles.

\section{Sets of Desirable Gambles}\label{sec:SDGs}

A gamble $\opt\in\opts$ is said to be \emph{desirable} if our subject strictly prefers it over the zero gamble, meaning that rather than not gamble at all, she strictly prefers to commit to the gamble where, after the true value $x$ of the uncertain variable $X$ has been determined, she will receive the (possibly negative) reward $\opt(x)$.

A \emph{set of desirable gambles} $\desirset$ is then a subset of $\opts$, whose interpretation will be that it consists of gambles $\opt\in\opts$ that our subject considers desirable.
The set of all sets of desirable gambles is denoted by $\desirsets$.
In order for a set of desirable gambles to represent a rational subject's beliefs, it should satisfy a number of rationality, or \emph{coherence}, criteria.

\begin{definition}
A set of desirable gambles $\desirset\in\desirsets$ is called \emph{coherent} if it satisfies the following axioms \emph{\cite{couso2011:desirable,cooman2010,cooman2011b,quaeghebeur2015:statement}}:
\begin{enumerate}[label=\textup{D}$_{\arabic*}$.,ref=\textup{D}$_{\arabic*}$,topsep=2pt,leftmargin=*]
\item $0\notin\desirset$;\label{ax:desirs:nozero}

\item\label{ax:desirs:pos} $\posopts\subseteq\desirset$;

\item\label{ax:desirs:cone} if $\opt,\altopt\in\desirset$, $\lambda,\mu\geq0$ and $\lambda+\mu>0$, then $\lambda\opt+\mu\altopt\in\desirset$.
\end{enumerate}
We denote the set of all coherent sets of desirable gambles by $\cohdesirsets$.
\end{definition}
\noindent
Axioms~\ref{ax:desirs:nozero} and~\ref{ax:desirs:pos} follow immediately from the meaning of desirability: zero cannot be strictly preferred to itself, and any gamble that is never negative but sometimes positive should be strictly preferred to the zero gamble.
Axiom~\ref{ax:desirs:cone} is implied by the assumed linearity of our utility scale.

Every coherent set of desirable gambles $\desirset\in\cohdesirsets$ induces a binary preference order $\succ_{\desirset}$---a strict vector ordering---on $\opts$, defined by $ \opt\succ_{\desirset}\altopt\ifandonlyif\opt-\altopt\in\desirset$, for all $\opt,\altopt\in\opts$.
The intuition behind this definition is that a subject strictly prefers the uncertain reward $\opt$ over $\altopt$ if she strictly prefers trading $\altopt$ for $\opt$ over not trading at all, or equivalently, if she strictly prefers the net uncertain reward $\opt-\altopt$ over the zero gamble.
The preference order $\succ_{\desirset}$ fully characterises $\desirset$: one can easily see that $\opt\in\desirset$ if and only if $\opt\succ_{\desirset}0$.
Hence, sets of desirable gambles are completely determined by binary strict preferences between gambles.

\section{Sets of Desirable Gamble Sets}

Let us now go back to our interpretation for choice functions, which is that a gamble $\opt$ in $\optset$ is rejected from $\optset$ if and only if there is some gamble $\altopt$ in $\optset$ that our subject strictly prefers over $\opt$.
We will from now on interpret this preference in terms of desirability: we take it to mean that $v-u$ is desirable.

In this way, we arrive at the following interpretation for a choice function $\choicefun$.
Consider any $\optset\in\optsets$ and $\opt\in\optset$, then
\begin{equation}\label{eq:choiceintermsofdesir}
\opt\notin\choicefun(\optset)
\ifandonlyif\opt\in\rejectfun[\choicefun](\optset)
\ifandonlyif(\exists\altopt\in\optset)\,\altopt-\opt
\text{~is desirable.}
\end{equation}
In other words, if we let $\optset-\set{\opt}\coloneqq\cset{\altopt-\opt}{\altopt\in\optset}$, then according to our interpretation, the statement that $\opt$ is rejected from $\optset$ is taken to mean that $\optset-\set{\opt}$ contains at least one desirable gamble.

A crucial observation here is that this interpretation does not require our subject to specify a set of desirable gambles.
Instead, all that is needed is for her to specify those gamble sets $\optset\in\optsets$ that to her contain at least one desirable gamble.
We call such gamble sets \emph{desirable gamble sets} and collect them in a \emph{set of desirable gamble sets} $\rejectset\subseteq\optsets$.
As can be seen from Equation~\eqref{eq:choiceintermsofdesir}, such a set of desirable gamble sets $\rejectset$ completely determines a choice function $\choicefun$ and its rejection function $\rejectfun[\choicefun]$:
\begin{equation*}\label{eq:choiceintermsofK}
\opt\notin\choicefun(\optset)
\ifandonlyif\opt\in\rejectfun[\choicefun](\optset)
\ifandonlyif\optset-\set{\opt}\in\rejectset,
\text{ for all $\optset\in\optsets$ and $\opt\in\optset$}.
\end{equation*}
The study of choice functions can therefore be reduced to the study of sets of desirable gamble sets.
We will from now on work directly with the latter.
We will use the collective term \emph{choice models} for choice functions, rejection functions, and sets of desirable gamble sets.

Let $\rejectsets$ denote the set of all sets of desirable gamble sets $\rejectset\subseteq\optsets$, and consider any such~$\rejectset$.
The first question to address is when to call $\rejectset$ \emph{coherent}: which properties should we impose on a set of desirable gamble sets in order for it to reflect a rational subject's beliefs? We propose the following axiomatisation, using $(\lambda,\mu)>0$ as a shorthand notation for `$\lambda\geq0$, $\mu\geq0$ and $\lambda+\mu>0$'.
\begin{definition}[Coherence]
A set of desirable gamble sets $\rejectset\subseteq\optsets$ is called \emph{coherent} if it satisfies the following axioms:
\begin{enumerate}[label=\textup{K}$_{\arabic*}$.,ref=\textup{K}$_{\arabic*}$,leftmargin=*,topsep=2pt,start=0]
\item\label{ax:rejects:nonempty}
$\emptyset\notin\rejectset$;

\item\label{ax:rejects:removezero}
$\optset\in\rejectset\then\optset\setminus\set{0}\in\rejectset$, for all $\optset\in\optsets$;
\item\label{ax:rejects:pos} $\set{\opt}\in\rejectset$, for all $\opt\in\posopts$;
\item\label{ax:rejects:cone} if $\optset[1],\optset[2]\in\rejectset$ and if, for all $\opt\in\optset[1]$ and $\altopt\in\optset[2]$, $(\lambda_{\opt,\altopt},\mu_{\opt,\altopt})>0$, then
\begin{equation*}
\cset{\lambda_{\opt,\altopt}\opt+\mu_{\opt,\altopt}\altopt}{\opt\in\optset[1],\altopt\in\optset[2]}
\in\rejectset;
\end{equation*}
\item\label{ax:rejects:mono}$\optset[1]\in\rejectset$ and $\optset[1]\subseteq\optset[2]\then\optset[2]\in\rejectset$, for all $\optset[1],\optset[2]\in\optsets$.

\end{enumerate}
We denote the set of all coherent sets of desirable gamble sets by $\cohrejectsets$.
\end{definition}

Since a desirable gamble set is by definition a set of gambles that contains at least one desirable gamble, Axioms~\ref{ax:rejects:nonempty} and~\ref{ax:rejects:mono} are immediate.
The other three axioms follow from the principles of desirability that also lie at the basis of Axioms~\ref{ax:desirs:nozero}--\ref{ax:desirs:cone}: the zero gamble is not desirable, the elements of $\posopts$ are all desirable, and any finite positive linear combination of desirable gambles is again desirable.
Axioms~\ref{ax:rejects:removezero} and~\ref{ax:rejects:pos} follow naturally from the first two of these principles.
The argument for Axiom~\ref{ax:rejects:cone} is more subtle; it goes as follows.
Since $\optset[1]$ and $\optset[2]$ are two desirable gamble sets, there must be at least one desirable gamble $\opt\in\optset[1]$ and one desirable gamble $\altopt\in\optset[2]$.
Since for these two gambles, the positive linear combination $\lambda_{\opt,\altopt}\opt+\mu_{\opt,\altopt}\altopt$ is again desirable, we know that at least one of the elements of $\cset{\lambda_{\opt,\altopt}\opt+\mu_{\opt,\altopt}\altopt}{\opt\in\optset[1],\altopt\in\optset[2]}$ is a desirable gamble.
Hence, it must be a desirable gamble set.

\section{The Binary Case}\label{sec:binary}

Because we interpret them in terms of desirability, one might be inclined to think that sets of desirable gamble sets are simply an alternative representation for sets of desirable gambles.
However, this is not the case: we will see that sets of desirable gamble sets constitute a much more general uncertainty framework than sets of desirable gambles.
What lies behind this added generality is that it need not be known which gambles are actually desirable.
For example, within the framework of sets of desirable gamble sets, it is possible to express the belief that at least one of the gambles $\opt$ or $\altopt$ is desirable while remaining undecided about which of them actually is; in order to express this belief, it suffices to state that $\set{\opt,\altopt}\in\rejectset$.
This is impossible within the framework of sets of desirable gambles.

Any set of desirable gamble sets $\rejectset\in\rejectsets$ determines a unique set of desirable gambles based on its binary choices only, given by
\begin{equation*}
\desirset[\rejectset]\coloneqq\cset{\opt\in\opts}{\set{\opt}\in\rejectset}.
\end{equation*}
That choice models typically represent more than just binary choice is reflected in the fact that different $\rejectset$ can have the same $\desirset[\rejectset]$.
Nevertheless, there are sets of desirable gamble sets $\rejectset\in\rejectsets$ that \emph{are} completely characterised by a set of desirable gambles, in the sense that there is a (necessarily unique) set of desirable gambles $\desirset\in\desirsets$ such that $\rejectset=\rejectset[\desirset]$, with
\begin{equation\iftoggle{arxiv}{}{*}}\label{eq:choicefromdesir}
\rejectset[\desirset]
\coloneqq\cset{\optset\in\optsets}{\optset\cap\desirset\neq\emptyset}.
\end{equation\iftoggle{arxiv}{}{*}}
It follows from the discussion at the end of Section~\ref{sec:SDGs} that such sets of desirable gamble sets are completely determined by binary preferences between gambles.
We therefore call them, and their corresponding choice functions, \emph{binary}.
For any such binary set of desirable gamble sets $\rejectset$, the unique set of desirable gambles $\desirset\in\desirsets$ such that $\rejectset=\rejectset[\desirset]$ is given by $\desirset[\rejectset]$.

\begin{proposition}\label{prop:binaryiff}
Consider any set of desirable gamble sets $\rejectset\in\rejectsets$.
Then $\rejectset$ is binary if and only if $\rejectset[{\desirset[\rejectset]}]=\rejectset$.
\end{proposition}

The coherence of a binary set of desirable gamble sets is completely determined by the coherence of its corresponding set of desirable gambles.

\begin{proposition}\label{prop:coherence:for:binary}
Consider any binary set of desirable gamble sets $\rejectset\in\rejectsets$ and let $\desirset[\rejectset]\in\desirsets$ be its corresponding set of desirable gambles. Then $\rejectset$ is coherent if and only if $\desirset[\rejectset]$~is.

\end{proposition}

\section{Representation in Terms of Sets of Desirable Gambles}\label{sec:representation}

That there are sets of desirable gamble sets that are completely determined by a set of desirable gambles is nice, but such binary choice models are typically \emph{not} what we are interested in here, because then we could just as well use sets of desirable gambles to represent choice.
It is the non-binary coherent choice models that we have in our sights here.
But it turns out that our axioms lead to a representation result that allows us to still use sets of desirable gambles, or rather, sets of them, to completely characterise \emph{any} coherent choice model.

\begin{theorem}[Representation]\label{theo:rejectsets:representation}
Every coherent set of desirable gamble sets $\rejectset\in\cohrejectsets$ is dominated by at least one binary set of desirable gamble sets: $\cohdesirsets\group{\rejectset}\coloneqq\cset{\desirset\in\cohdesirsets}{\rejectset\subseteq\rejectset[\desirset]}\neq\emptyset$.
Moreover, $\rejectset=\bigcap\cset{\rejectset[\desirset]}{\desirset\in\cohdesirsets\group{\rejectset}}$.
\end{theorem}
\noindent
This powerful representation result allows us to incorporate a number of other axiomatisations~\cite{2017vancamp:phdthesis} as special cases in a straightforward manner, because the binary models satisfy the required axioms, and these axioms are preserved under taking arbitrary non-empty intersections.

\section{Natural Extension}\label{sec:natex}

In many practical situations, a subject will typically not specify a full-fledged coherent set of desirable gamble sets, but will only provide some partial \emph{assessment} $\assessment\subseteq\optsets$, consisting of a number of gamble sets for which she is comfortable about assessing that they contain at least one desirable gamble.
We now want to extend this assessment~$\assessment$ to a coherent set of desirable gamble sets in a manner that is as conservative---or uninformative---as possible.
This is the essence of \emph{conservative inference}.

We say that a set of desirable gamble sets $\rejectset[1]$ is less informative than (or rather, at most as informative as) a set of desirable gamble sets $\rejectset[2]$, when \mbox{$\rejectset[1]\subseteq\rejectset[2]$}: a subject whose beliefs are represented by $\rejectset[2]$ has more (or rather, at least as many) desirable gamble sets---sets of gambles that definitely contain a desirable gamble---than a subject with beliefs represented by $\rejectset[1]$.
The resulting partially ordered set $(\rejectsets,\subseteq)$ is a complete lattice with intersection as infimum and union as supremum.
The following theorem, whose proof is trivial, identifies an interesting substructure.

\begin{theorem}\label{theo:conservative:inference}
Let $\set{\rejectset[i]}_{i\in I}$ be an arbitrary non-empty family of sets of desirable gamble sets, with intersection $\rejectset\coloneqq\bigcap_{i\in I}\rejectset[i]$.
If $\rejectset[i]$ is coherent for all $i\in I$, then so is $\rejectset$.
This implies that $(\cohrejectsets,\subseteq)$ is a complete meet-semilattice.
\end{theorem}
\noindent
This result is important, as it allows us to a extend a partially specified set of desirable gamble sets to the most conservative coherent one that includes it.
This leads to the conservative inference procedure we will call natural extension.

\begin{definition}[Consistency and natural extension]
For any assessment $\assessment\subseteq\optsets$, let $\cohrejectsets(\assessment)\coloneqq\cset{\rejectset\in\cohrejectsets}{\assessment\subseteq\rejectset}$.
We call the assessment~$\assessment$ \emph{consistent} if\/ $\cohrejectsets(\assessment)\neq\emptyset$, and we then call\/ $\natexrejectset(\assessment)\coloneqq\bigcap\cohrejectsets(\assessment)$ the \emph{natural extension} of $\assessment$.
\end{definition}
\noindent
In other words: an assessment $\assessment$ is consistent if it can be extended to some coherent rejection function, and then its natural extension $\natexrejectset(\assessment)$ is the least informative such coherent rejection function.

Our final result provides a more `constructive' expression for this natural extension and a simpler criterion for consistency.
In order to state it, we need to introduce the set $\singposopts\coloneqq\cset{\set{\opt}}{\opt\in\posopts}$ and two operators on---transformations of---$\rejectsets$.
The first is denoted by $\RS$, and defined by
\begin{equation*}
\RS\group{\rejectset}\coloneqq\cset{\optset\in\optsets}{(\exists\altoptset\in\rejectset)\altoptset\setminus\nonposopts\subseteq\optset}
\text{ for all $\rejectset\in\rejectsets$},
\end{equation*}
so $\RS\group{\rejectset}$ contains all gamble sets $\optset$ in $\rejectset$, all versions of $\optset$ with some of their non-positive options removed, and all supersets of such sets.
The second is denoted by $\setposi$, and defined for all $\rejectset\in\rejectsets$ by
\begin{align*}
\setposi\group{\rejectset}\coloneqq\bigg\{
\bigg\{
\sum_{k=1}^n\lambda_{k}^{\opt[1:n]}\opt[k]
\colon
\opt[1:n]\in\times_{k=1}^n\optset[k]
\bigg\}
\colon
&n\in\naturals,(\optset[1],\dots,\optset[n])\in\rejectset^n,\\[-11pt]
&\big(\forall\opt[1:n]\in\times_{k=1}^n\optset[k]\big)\,\lambda_{1:n}^{\opt[1:n]}>0
\bigg\},
\end{align*}
where we used the notations $\opt[1:n]$ and $\lambda_{1:n}^{\opt[1:n]}$ for $n$-tuples of options $\opt[k]$ and real numbers $\lambda_{k}^{\opt[1:n]}$, $k\in\set{1,\dots,n}$, so $\opt[1:n]\in\opts^{n}$ and $\lambda_{1:n}^{\opt[1:n]}\in\reals^{n}$.
We also used $\lambda_{1:n}^{\opt[1:n]}>0$ as a shorthand for `$\lambda_k^{\opt[1:n]}\geq0$ for all $k\in\set{1,\dots,n}$ and $\sum_{k=1}^n\lambda_k^{\opt[1:n]}>0$'.

\begin{theorem}[Natural extension]\label{theo:rejectsets:consistency:and:natex}
Consider any assessment $\assessment\subseteq\optsets$.
Then $\assessment$ is consistent if and only if\/ $\emptyset\notin\assessment$ and\/ $\set{0}\notin\setposi\group{\singposopts\cup\assessment}$.
Moreover, if $\assessment$ is consistent, then $\natexrejectset(\assessment)=\RS\group{\setposi\group{\singposopts\cup\assessment}}$.
\end{theorem}

\section{Conclusion}

Our representation result shows that binary choice \emph{is} capable of representing general coherent choice functions, provided we extend its language with a `disjunction' of desirability statements---as is implicit in our interpretation---, next to the `conjunction' and `negation' that are already implicit in the language of sets of desirable gambles---see~\cite{quaeghebeur2015:statement} for a clear exposition of the latter claim.

In addition, we have found recently that by adding a convexity axiom, and working with more general vector spaces of options to allow for the incorporation of horse lotteries, our interpretation and corresponding axiomatisation allows for a representation in terms of lexicographic sets of desirable gambles \cite{2017vancamp:phdthesis}, and therefore encompasses the one by Seidenfeld et al.~\cite{seidenfeld2010} (without archimedeanity).
We will report on these findings in more detail elsewhere.

Future work will address (i) dealing with the consequences of merging our accept-reject statement framework \cite{quaeghebeur2015:statement} with the choice function approach to decision making; (ii) discussing the implications of our axiomatisation and representation for conditioning, independence, and indifference (exchangeability); and (iii) expanding our natural extension results to deal with the computational and algorithmic aspects of conservative inference with coherent choice functions.

\section*{Acknowledgements}

This work owes a large intellectual debt to Teddy Seidenfeld, who introduced us to the topic of choice functions.
His insistence that we ought to pay more attention to non-binary choice if we wanted to take imprecise probabilities seriously, is what eventually led to this work.

The discussion in Arthur Van Camp's PhD~thesis \cite{2017vancamp:phdthesis} was the direct inspiration for our work here, and we would like to thank Arthur for providing a pair of strong shoulders to stand on.

As with most of our joint work, there is no telling, after a while, which of us two had what idea, or did what, exactly.
We have both contributed equally to this paper.
But since a paper must have a first author, we decided it should be the one who took the first significant steps: Jasper, in this case.

config: arxiv


TITLE: Fluids - vector identity confusion
QUESTION [1 upvotes]: Trying to prove Kelvin's Circulation Theorem, but struggling to see why the following equality holds:

$$\textbf{u} \cdot (d\textbf{l}\cdot \nabla)\textbf{u} = d\textbf{l} \cdot \nabla \left(\frac{1}{2} u^2 \right)$$

I don't really have much idea where to start. I can take that gradient on the RHS, but that is of a scalar function and I'm not sure how I'll be able to get the vector $\textbf{u}$ out in the way that looks anything like how it should on the LHS...
Any hints would be appreciated (don't mind a solution either)
Edit: added picture of $d\mathbf{l}$ representation from notes.

REPLY [2 votes]: \begin{align}
d\textbf{l} \cdot \nabla \left(\frac{1}{2} u^2 \right)
&\;=\; \sum_{\mu\, \nu} dl_{\mu} \, \frac{\partial}{\partial x_{\mu}} \, \frac{1}{2} u_{\nu}u_{\nu}\\
&\;=\; \sum_{\mu\, \nu} dl_{\mu} \, u_{\nu}\, \frac{\partial}{\partial x_{\mu}} u_{\nu}\\
&\;=\; \sum_{\mu\, \nu} u_{\nu} \, dl_{\mu} \, \frac{\partial}{\partial x_{\mu}} u_{\nu}\\
&\;=\; \mathbf{u} \cdot \bigl[
\left(d\mathbf{l}\cdot \mathbf{\nabla}\right) \mathbf{u}
\bigr]
\end{align}


TITLE: Wigner function derivation of a multicomponent signal
QUESTION [0 upvotes]: A multicomponent signal can be expressed in exponentials can be expressed as follow,
$$x(t)=\sum_{k}c_k e^{2\pi f_0 t}$$
The Fourier transform of $x(t)$ is easy
$$\mathcal{F}_x(f)=\sum_k c_k \delta(f-kf_0)$$
while the Wigner Function is
$$ W_x(t,f) = \frac{1}{2\pi}\int x\Big(t+\frac{\tau}{2}\Big)x^*\Big(t-\frac{\tau}{2}\Big) e^{-j2\pi f\tau}\;d\tau $$
$$=\sum_k |c_k|^2 \delta(f-kf_0)+\sum_k \sum_{m \neq k} c_k c_m^* \delta(f-\frac{k+m}{2})e^{j2\pi(k-m)f_0t}.$$
However reference for this Wigner function did not provide the derivation and I'm struggling how to properly derive it.
I have already derived the Wigner function of a signal with trigonometric function $x(t)=cos(2\pi t +\theta)$ in this question but I don't know where to start with this multicomponent signal. Any hint will be appreciated.

REPLY [1 votes]: Hint 1: You seem to have several typos in your provided formulas above.  Please read them carefully from the source and fix the transcriptions.
Hint 2: Realize that the term out front, in the expression for the specific Wigner function, is just a special case for when $k=m$, that has been pulled out of the double summation:
$$\begin{align} &\sum_k |c_k|^2 \delta\left(f-kf_0\right)+\sum_k \sum_{m \neq k} c_k c_m^* \delta\left(f-\frac{k+m}{2}f_0\right)e^{j2\pi(k-m)f_0t} \\
\\
&=  \sum_k \sum_{m} c_k c_m^* \delta\left(f-\frac{k+m}{2}f_0\right)e^{j2\pi(k-m)f_0t}\\
\end{align}$$
Hint 3: Realize that the product of two summations is going to result in a double summation:
$$\begin{align} x\left(t+\dfrac{\tau}{2}\right)x^*\left(t-\dfrac{\tau}{2}\right) &= \left(\sum_{k=L}^N c_k e^{j2\pi kf_0\left(t+\frac{\tau}{2}\right)}\right)\left(\sum_{m=L}^N c^*_m e^{-j2\pi mf_0\left(t-\frac{\tau}{2}\right)}\right)\\
\\
&=\left(\sum_{k=L}^N c_ke^{j2\pi kf_0t} e^{j2\pi \frac{k}{2}f_0\tau}\right)\left(\sum_{m=L}^N c^*_m e^{-j2\pi mf_0t}e^{j2\pi \frac{m}{2}f_0\tau}\right) \\
\\
&= c_Lc^*_Le^{j2\pi (L-L)f_0t} e^{j2\pi \frac{L+L}{2}f_0\tau }\\
&+ c_Lc^*_{L+1}e^{j2\pi (L-[L+1])f_0t} e^{j2\pi \frac{L+L+1}{2}f_0\tau }\\
&\dots \\
&+ c_Nc^*_{N-1}e^{j2\pi (N-[N-1])f_0t} e^{j2\pi \frac{N+[N-1]}{2}f_0\tau }\\
&+ c_Nc^*_{N}e^{j2\pi (N-N)f_0t} e^{j2\pi \frac{N+N}{2}f_0\tau }\\
\\
&= \sum_k \sum_m c_kc^*_me^{j2\pi (k-m)f_0t}e^{j2\pi \frac{k+m}{2}f_0\tau} \\
\end{align}$$
Getting from that double summation to the specific Wigner function you desire should be very straight forward.


TITLE: Axiomatisable Groups
QUESTION [0 upvotes]: Let A be a set of sentences (“proper axioms”) in a first-order language L with equality. Let us write Mod(A) for the class of all models of A which respect equality. We say that a class of L-structures is axiomatisable if it is Mod(A) for some such A. It is finitely axiomatisable if A is finite. (For example, the usual set of axioms G for group theory shows that the class of all groups is finitely axiomatisable.)
Prove:
(i) The class of all finite groups is not axiomatisable.
(ii) The class of all infinite groups is axiomatisable.
(iii) The class of all infinite groups is not finitely axiomatisable.
How can I prove the above results?

REPLY [2 votes]: Hint for the first question: Let $\mathcal L$ be a language and let $T$ be any $\mathcal L$-theory with arbitrarily large finite models. Consider the language $\mathcal L'=\mathcal L\cup\{c_n\mid n\in\Bbb N\}$, where every $c_n$ is a constant symbol and the $\mathcal L'$ sentences $$\varphi_n=\bigwedge\limits_{\substack{1\leq i,j\leq n \\ i\neq j}}\neg(c_i=c_j)$$
so that intuitively $\varphi_n$ is saying "there are at least $n$ different elements. Is $T\cup\{\varphi_n\mid n\in\Bbb N\}$ finitely satisfiable? What does the compactness theorem tell you now?
Hint for the second question: Look again at the $\varphi_n$ from my first hint.
Hint for the third question: Suppose that $T$ is a finitely axiomatizable theory and that $\Gamma$ is an axiomatization of $T$. Can you show that there must be a $\Delta\subset\Gamma$, with $\Delta$ finite, such that $\Delta$ is an axiomatization of $\Gamma$? Now think again about your axiomatization from the second question.


TITLE: How to solve equation
QUESTION [0 upvotes]: I have a problem to solve that equation
$\log_{4}\left(x\right) = -2x + 9$
i know that answer is 4
but what is step by step solution.

REPLY [1 votes]: I don't think there is a systematic approach, but you can proceed as follows:
Let $x > 0$ be such that $\log_4 x = -2x +9$. Then $x= 4^{-2x}4^9 = \frac{2^{18}}{e^{2\ln4\cdot x}}$, so that ${x}{e^{2\ln4 x}} = 2^{18}$, and
$$
{2\ln4\cdot x}{e^{2\ln4\cdot x}} = 2^{19}\ln 4 \tag{1}
$$
It is not too hard to show that the function $f\colon y > 0 \mapsto {y}{e^y}$ is increasing on $(0,\infty)$; since $f(0)=0$ and $2^{19}\ln 4 > 0$, this implies that the only possible solution is for some $y\stackrel{\rm{}def}{=}2\ln4\cdot x$ being in $(0,\infty)$. In particular, there is at most one solution, so if you happen to find one, you'd be done.
Now, by magic, once you have found that the "easy" solution $x=4$ works (in (1) and in the original equation), you proved that it was the only one.


TITLE: Let $f$ be entire and suppose that $Re f(z) \le M$ for all $z$. Prove that $f$ must be a constant function.
QUESTION [0 upvotes]: Let $f$ be entire and suppose that $\Re f(z)  \le M$ for all $z$.  Prove that $f$ must be a constant function.

How would you do this proof?  I was thinking about applying Liouville's theorrem to the function $e^f$ but I'm not sure..

REPLY [2 votes]: With $g(z)=e^{f(z)}$, then $|g(z)|=e^{\text{Re}f(z)}\leq e^{M}$, so Liouville's Theorem says that $g=c$, the result follows.


TITLE: update of centroids in $k$ means clustering
QUESTION [1 upvotes]: I have been reading the lecture notes of Andrew Ng about Clustering techniques available in:
http://cs229.stanford.edu/notes/cs229-notes7a.pdf
but I have a problem in the second for of step $2$ which is the following:

For what I know, the previous step or for each section what it does is to set a value of $c$ considering the minimum value of each x minus the value of the centroid ($\mu$). According to what I read the second for each should update the values of the centroid by computing the new mean of the $x$ values assigned to this centroid, but how does this part do that? any numerical example would be great.
Why there is a value of $1\{\}$ before each set of brackets? and for what I see the value of the numerator by being multiplied with $x^{(i)}$ their summation would be greater than the sum of the value of the denominator. Should not be the other way around?
Thanks

REPLY [1 votes]: The formula means if the $i$-th data point is considered to be group $j$, we should consider that data point in updating our mean.
For example, if we think $x_1, x_2, x_3$ belongs to cluster $1$.
Then $\mu_1 = \frac{x_1+x_2+x_3}{3}.$
The notation $1\{c^{(i)}=j\}$ is an indicator function.
$\sum_{i=1}^m1\{c^{(i)}=j\}$ count the number of data point in cluster $j$.
$\sum_{i=1}^m1\{c^{(i)}=j\}x_i$ sums up the data points in cluster $j$.
The formula is the average of data points in the $j$-th cluster.


TITLE: Relaxed continuous mapping theorem
QUESTION [0 upvotes]: Let $X_{n}$ and $Y_{n}$ be sequences of random elements taking values in some normed space $S$ and defined on the same probability space. Next, assume that
$$
X_{n} = O_{p}(1),
$$
i.e. $X_{n}$ is stochastically bounded and
$$
Y_{n} \overset{a.s.}{\to} a,
$$
where $a$ is a constant element from $S$.
Next, let $f:S\times S \to \mathbb{R}$ be a continuous function. The question is the following hold
$$
f(X_{n}, Y_{n}) = O_{p}(1).
$$
Remark. By $O_{p}(1)$ I mean that for any $\varepsilon > 0$ there exists a finite $M$ and $N$ such that
$$
P(|X_{n}|>M)<\varepsilon, \, \forall \, n>N.
$$

REPLY [1 votes]: This is true if the normed space in question is finite dimensional and complete.  Otherwise, it may not be.
To start with, assume $S$ is finite dimensional and complete.  In particular, bounded subsets of $S$ are compact.
Since $Y_{n} \to a$ almost surely, it converges to $a$ in probability.  In particular, there is an $N_{1} \in \mathbb{N}$ such that
\begin{equation*}
P(\|Y_{n} - a\| > 1) \leq \frac{\epsilon}{3} \quad \text{if} \, \, n \geq N_{1}.
\end{equation*}
Choose $M > 0$ and $N_{2} \in \mathbb{N}$ such that
\begin{equation*}
P(\|X_{n}\| > M) \leq \frac{\epsilon}{3} \quad \text{if} \, \, n \geq N_{2}.
\end{equation*}
$f$ is continuous so there is a $K > 0$ such that $|f(x,y)| \leq K$ in the compact set $\bar{B}(0,M) \times [a - 1, a + 1]$, where $\bar{B}(0,M) = \{x \in S \, \mid \, \|x\| \leq M\}$. Therefore,
\begin{equation*}
P(|f(X_{n},Y_{n})| > K) \leq P(\|Y_{n} - a\| > 1) + P(\|X_{n}\| > M) \leq \frac{2 \epsilon}{3} \quad \text{if} \, \, n \geq \max\{N_{1},N_{2}\}.
\end{equation*}
If $S$ is not complete or not finite dimensional, the argument above fails because the result is no longer true.
In the non-complete case, we could use $S = \mathbb{Q}$ and let $(x_{n})_{n \in \mathbb{N}} \subseteq \mathbb{Q}$ with $x_{n} \to \pi$.  Define $f : \mathbb{Q} \times \mathbb{Q} \to \mathbb{R}$ by $f(x,y) = \frac{1}{x - \pi}$.  If we take the deterministic random variables $Y_{n} \equiv a$ for all $n \in \mathbb{N}$ and $X_{n} \equiv x_{n}$ for all $n \in \mathbb{N}$, then $f(X_{n},Y_{n}) = \frac{1}{x_{n} - \pi}$ surely and this is not stochastically bounded.
If $S$ is not finite dimensional, then closed balls are no longer compact in the norm topology.  Consequently, we can find an unbounded continuous function $g : \bar{B}(0,1) \to \mathbb{R}$.  Choose $(x_{n})_{n \in \mathbb{N}} \subseteq \bar{B}(0,1)$ such that $|g(x_{n})| \to \infty$ as $n \to \infty$.  As before, use deterministic sequences $Y_{n} \equiv a$ and $X_{n} \equiv x_{n}$ with $f(x,y) = g(x)$ to get that $f(X_{n},Y_{n})$ is not bounded.


TITLE: Equi-continuous sequence of functions from a continuous function having vanishing limit at infinity
QUESTION [1 upvotes]: Let $f:[1, \infty) \rightarrow \mathbb{R}$ be a continuous function such that
$$
\lim _{x \rightarrow \infty}|f(x)|=0
$$
For $n \geq 1$, let $g_{n}:[1, \infty) \rightarrow \mathbb{R}$ be given by
$$
g_{n}(x)=f(n x)
$$
Show that $\{g_n\}_{n \geq 1}$ is equicontinuous on $[1, \infty)$.
How to make $|f(nx)-f(ny)|<\epsilon$ for all $n \geq 1$ while from the limit, we can have $|f(nx)-f(ny)|\leq|f(nx)|+|f(ny)|<\epsilon$ whenever $n \geq M$ for some $M>0$.

REPLY [1 votes]: For any $\epsilon >0~~~\exists~M>0$ such that $|f(x)|<\frac{\epsilon}{4}$ for all $x\geq M$. Without loss of generality we can let $M>1$.
$f$ is uniformly continuous on $[1,M]$ (since it is continuous there). For the above $\epsilon$ there exists $\delta >0$ such that  $x_1, x_2 \in [1,M]$ and $|x_1-x_2|<\delta$ implies $|f(x_1)-f(x_2)|<\frac{\epsilon}{2}$.
If $x_1, x_2 \geq M$ then $|f(x_1)-f(x_2)|\leq |f(x_1)|+|f(x_2)|<\frac{\epsilon}{2}<\epsilon$.  (No role of  $\delta$  here).
If  $|x_1-x_2|<\delta$ and  $x_1 <M$,  $x_2>M$  then  $|f(x_1)-f(x_2)|\leq |f(x_1)-f(M)|+|f(M)-f(x_2)| \leq \frac{\epsilon}{2}+\frac{\epsilon}{4}+\frac{\epsilon}{4}=\epsilon$   (because $|x_1-M|<\delta$).
Combining we get $f$ is uniformly continuous on $[1, \infty)$ and $|x_1-x_2|< \delta$ implies  $|f(x_1)-f(x_2)| \leq \epsilon$.
Now for $x_1, x_2 \in [1, \infty)$ and $n \in \mathbb{N}$, $nx_1, nx_2$ are just two points in $[1, \infty)$. So $|nx_1-nx_2|< \delta$ implies  $|f(nx_1)-f(nx_2)|\leq  \epsilon$, i.e. $|g_n(x_1)-g_n(x_2)|\leq \epsilon$ for all $n$.


TITLE: Minimizing the cost of production by choosing between two options with different resource demands
QUESTION [0 upvotes]: Suppose that the ﬁrm has two possible activities to produce output. Activity $A$ uses $a_1$ units of good $1$ and $a_2$ units of good $2$ to produce $1$ unit of output. Activity $B$ uses $b_1$ units of good $1$ and $b_2$ units of good $2$ to produce $1$ unit of output. Factors can only be used in these ﬁxed proportions. If the factor prices are $(w_1,w_2)$, what are the demands for the two factors?
Please help me with this question as I don't know what to do when there are two simultaneous activities involved.thank you

REPLY [0 votes]: The cost function for one unit of output is $c(a,b)=w_1\cdot x_1+w_2\cdot x_2$
You can sketch the points $A(a_1/a_2)$,$B(b_1/b_2)$ in a diagram.  The line, which goes through the points A and B have to have a negative slope. Otherwise activity A or B is not efficient. Calcutlate the slope.
Then set $c(a,b)$ equal to 0 and solve $c(a,b)$ for $x_2$. Draw the line through the point $C(0/0)$ with the slope $-\frac{w_1}{w_2}$ Then push the line parallel upward till the line touches first point A or point B. The Point, which is touched first by the line, is the activity, which you have to apply, if you minimize the costs.
You can insert some values for $w_1,w_2,a_1,a_2,b_1$and $b_2$. You will recognize the following rules for minimizing the costs:

Use activity A, if $\left|\frac{a_2-b_2}{a_1-b_1}  \right| < \left| \frac{w_1}{w_2}\right| $
Use activity A or B, if $\left|\frac{a_2-b_2}{a_1-b_1}  \right| = \left| \frac{w_1}{w_2}\right|$
Use activity B, if $\left|\frac{a_2-b_2}{a_1-b_1}  \right| > \left| \frac{w_1}{w_2}\right|$


text:
\section{\textsf{COMRADE} Can Resist Byzantine Workers} \label{sec:byz}
In this section, we analyze \textsf{COMRADE} with Byzantine workers. We assume that $\alpha (< 1/2)$  fraction of worker machines are Byzantine. We define the set of Byzantine worker machines by $\cB$ and the set of the good (non-Byzantine)  machines by $\cM$. \textsf{COMRADE} employs a `norm based thresholding' scheme on the local Hessian inverse and gradient product to tackle the Byzantine workers.

In the $t$-th iteration, the center machine outputs a set  $\cU_t$ with  $\left| \cU_t \right|= (1-\beta)m$, consisting the indices of the worker machines with smallest norm. Hence, we `trim' the worker machines that may try to diverge the learning algorithm.  We denote the set of trimmed machines as $\cT_t$. Moreover, we take $\beta > \alpha$ to ensure at least one good machine falls in $\cT_t$. This condition helps us to control the Byzantine worker machines. Finally, the update is given by $\hat{\p}_t= \frac{1}{|\cU_t|}\sum_{i\in \cU_t}\hat{\p}_{i,t} $.
We define:
\small
\begin{align}
  & \epsilon_{byz}^2 = [3 (\frac{1-\alpha}{1-\beta})^2 +4\kappa_t (\frac{\alpha}{1-\beta})^2 ]\epsilon^2, \label{gbyz}\\

   & \zeta^2_{byz}  =2 (\frac{1-\alpha}{1-\beta} )^2(\frac{\nu}{1-\eta})^2 + \nu^2 (\frac{1-\alpha}{1-\beta})^2 (\frac{\eta}{\sqrt{(1-\alpha)m}}+ \frac{\eta^2}{1-\eta} )^2 + 4\kappa_t (\frac{\alpha}{1-\beta})^2 [2+(\frac{\nu}{1-\eta})^2 ]. \label{alpbyz}

\end{align}
\normalsize

 $\epsilon$ is defined in \eqref{eps}, $\nu= \frac{\sigma_{max}(\bA^T\bA)}{\sigma_{max}(\bA^T\bA)+n\lambda}$ and $\kappa_t$ is the condition number of the exact Hessian $\bH_t$.

\begin{theorem}\label{thm:byzsmooth}
Let $\mu \in \left[ 1, \frac{n}{d}\right]$ be the coherence of $\bA_t$ . Suppose $\gamma =1$ and $s \geq  \frac{3\mu d}{\eta^2}\log \frac{md}{\delta}$ for some $\eta,\delta \in (0,1)$. For $0\leq\alpha < \beta <1/2$  , under Assumption ~\ref{asm:hess} , with probability exceeding $1-\delta$, Algorithm~\ref{alg:main_algo} yields

\begin{align*}
  \| \mathbf{\Delta}_{t+1}\| \leq \max \{ \sqrt{\kappa_t(\frac{\zeta_{byz}^2}{1-\zeta_{byz}^2} )}\| \mathbf{\Delta}_{t}\|, \frac{L}{\sigma_{min}(\bH_t) }\| \mathbf{\Delta}_{t}\|^2  \}+ \frac{ 2\epsilon_{byz} }{\sqrt{\sigma_{min}(\bH_t)}},
\end{align*}
where $\zeta_{byz}$ and $\epsilon_{byz}$ are defined in equations~\eqref{gbyz} and \eqref{alpbyz} respectively.
 \end{theorem}
The remarks of Section~\ref{sec:one} is also applicable here. On top of that, we have the following remarks:
\begin{remark}
Compared to the convergence rate of Theorem~\ref{thm:smooth}, the rate here remains order-wise same even with Byzantine robustness. The coefficient of the quadratic term remains unchanged but the linear rate and the error floor suffers a little bit (by a small constant factor).
\end{remark}
\begin{remark}
Note that for Theorem~\ref{thm:byzsmooth} to hold, we require $\alpha \sim 1/\sqrt{\kappa_t}$  for all $t$. In cases where $\kappa_t$ is large, this can impose a stricter condition on $\alpha$. However, we conjecture that this dependence can be improved via applying a more intricate (and perhaps computation heavy) Byzantine resilience algorithm. In this work, we kept the Byzantine resilience scheme simple at the expense of this condition on $\alpha$.
\end{remark}


TITLE: Find $x$ so that $\left|\begin{array}{r}1&x&1\\x&1&0\\0&1&x\end{array}\right|=1$
QUESTION [0 upvotes]: I want to find a certain $x$ that belongs to $\mathbb R$ so that
$$\left|\begin{array}{r}1&x&1\\x&1&0\\0&1&x\end{array}\right|=1$$
This should be easy enough. I apply the Laplace extension on the third row so  I get
$$0-\left|\begin{array}{a}1 & 1\\x&0\end{array}\right|+x\left|\begin{array}{r}1&x\\x &1\end{array}\right|=1$$
So we have
$$-(0-x)+x(1-x^2)=1\implies x+x-x^3=1\implies x^3-2x+1=0$$
I'm kind of stuck because I'm not entirely familiar with solving cubic functions. I don't think there's a way to refactor this. Perhaps I should have found another way to solve this. $x=1$ is definitely a solution, but there's another one that I'm missing. Any hints?

REPLY [1 votes]: Polynomial long division:
$\small{(x^3-2x+1)÷(x-1)= x^2 +x-1}$;
$\small{ -(x^3-x^2)}$
$-----$
$\small{x^2-2x +1}$
$\small{ -(x^2-x)}$
$------$
$\small{-x +1}$
$\small{ -(-x+1)}$
$------$
$\small{0}$