TITLE: Show that $d(z,z_1)$ is a metric.
QUESTION [0 upvotes]: I am relatively new to proofs so I am struggling to understand what really counts as "proved" and what doesn't.

Consider the vector space $\mathbb M $ of real numbers $\mathbb R$.
   Show that for $z,z_1 \in \mathbb R$, $d:\mathbb M \times \mathbb M
 \rightarrow\mathbb R^+$ defined as $$d(z,z_1)=f(\lvert z-z_1 \rvert),
 \space \space \space f:\mathbb R^+\rightarrow \mathbb R^+$$ is a
   metric provided that for $x,y \in \mathbb R^+$
$\text{(A)} \space \space f(0)=0 \\ \text{(B)} \space \space f(x)>0
 \space  \text{for} \space  x>0 \\ \text{(C)} \space \space f(y) \ge
 f(x) \space \text{for} \space y \ge x \space \text{i.e. $f$ is a monotonically growing function}\\ \text{(D)} \space
\space\frac{f(x)}{x}\ge \frac{f(y)}{y} \space \text{for} \space y \ge
x$

This is what I have tried so far:
In order for a space to be a metric space the following axioms have to be true:
$\text{(1)} \space \space d \space \text{is real valued, finite and nonnegative } \\ \text{(2)} \space \space d(x,y)=0 \iff x=y \\ \text{(3)} \space \space d(x,y)=d(y,x) \\ \text{(4)} \space \space d(x,y) \le d(x,z)+d(z,y)$
For (1): $\forall x,y \in \mathbb R^+, \lvert x-y\rvert \ge 0$. From (B) it follows that if $\lvert x-y \rvert > 0 \implies f(\lvert x-y \rvert) \ge 0 \implies d\ge 0 \checkmark$
For (2): $\lvert x-y \rvert=0 \iff x=y \implies f(\lvert x-y \rvert)=f(0)=0 \iff x=y \checkmark$
Does this count as proving? I am not sure how to show 3) and 4). Maybe someone can show me or give me a hint. Thanks.

REPLY [1 votes]: We need the following
Lemma. A function $f$ with the properties (A)–(D) is subadditive, i.e., one has
$$f(x+y)\leq f(x)+f(y)\qquad(x>0, \>y>0)\ .$$
Proof. From
$${f(x+y)\over x+y}\leq {f(x)\over x},\qquad {(x+y)\over x+y}\leq {f(y)\over y}$$
it follows that
$${f(x+y)\over x+y}\leq{x\over x+y}\>{f(x)\over x}+{y\over x+y}\>{f(y)\over y}\ .$$
Now multiply with $x+y$.$\qquad\square$
This allows to complete the proof that for any metric $d$ on a set $X$ the function $d':=f\circ d$ is again a metric if $f$ has the properties (A)–(D): Given any three points $x$, $y$, $z\in X$ one has
$$d'(x,z)=f\bigl(d(x,z)\bigr)\leq f\bigl(d(x,y)+d(y,z)\bigr)\leq f\bigl(d(x,y)\bigr)+f\bigl(d(y,z)\bigr)=d'(x,y)+d'(y,z)\ .$$


TITLE: Calculate how many holes in a line, when line length, hole and gap length are known.
QUESTION [0 upvotes]: I have a hand rail, that has regularly spaced holes in it. The rail length is given, the length of the holes is given, and the even gap between the holes is given. Also this run is positioned centrally in the handrail, in so much as the remaining gap is divided equally at the ends
I would like assistance with coming up with a formula that can calculate how many holes would fit in a given hand rail.
The purpose being that I were to tweak the variable lengths, the amount of holes is always calculated.
Here is a demonstration:
Rail length: 110  Hole Length: 10  Gap length: 5  End lengths 20 Amount of holes: 5

REPLY [0 votes]: It seems as if, in your example, you could have 6 holes, which makes for 60 units of hole-length, 25 units of gap, and 12.5 end length, or even 7 holes, making 70 units of hole-length, 30 of gap, and 5 at each end. If you give us rail length, hole length, and gap, all three answers are valid. No single formula could possibly give all three.
But if you're willing to give the end length as well, then you have this:
\begin{align}
L = nh + (n-1)g + 2e
\end{align}
where $L$ is the total length, $n$ the number of holes, $h$ the hole-width, $g$ the gap between holes, and $e$ then end-length. Solving for $n$, we get
\begin{align}
L &= nh + (n-1)g + 2e\\
L -2e&= nh + ng-g\\
L -2e + g &= n(h + g)\\
\frac{L - 2e + g}{h+g} &= n,
\end{align}
and that's your formula. Of course, if you make the end-lengths too long, you can get negative values for $n$, but think of a 10-foot rail with two 7-foot end-lengths. Not much room for holes, is there?


TITLE: Finding Moebius transformation
QUESTION [2 upvotes]: i'm triyin to solve this:
Find a moebius transformation that applies the exterior of the circle $\{z:|z-1|=1\}$ to the right half plane. $\{z: Re(z)>0\}$.
So i fixed $a=1$, then

$T(2) \to \infty$ $\implies \frac{2\cdot 1+b}{2c+d}=\infty$
$T(1-i) \to 1 \implies \frac{(1-i)+b}{c(1-i)+d}=1$
$T(0) \to 0 \implies \frac{0 \cdot 1 +b}{c\cdot 0 + d}=0$
with this I get the following equation system
$a=1$
$2c+d=0$
$1-i+b=c-ci+d$
$b=0$
and i get $a=1, b=0, c=i$ and $d=-2i$ so i get the next moebius transformation $T(z)=\frac{z}{iz-2i}$ wich verifies for $2,1-i$ and $0$ but if i consider $-1$ in the exterior of the circle then $T(-1)=\frac{-1}{-i-2i}=\frac{-1}{-3i}=\frac{-i}{3}$ and $\frac{-i}{3}$ is not into the right half plane. $\{z: Re(z)>0\}$.
I don't know where I went wrong

REPLY [0 votes]: Doing this by solving equations for the coefficients may not be the easiest way. There are "geometric" options. First, translate the circle $|z-1|=1$ to the circle $|z|=1$. Then invert: $z\to 1/z$. Now, true, this sends $0$ to the point at infinity, but this is inescapable: if the exterior of a circle is not taken to include the point at infinity, then it has the homotopy type of a circle, which is not the same as the homotopy type of a half-plane... Then map the unit disk to a half-plane by a "Cayley map"... (for example, sending $-1\to 0$, $0\to 1$, and $1\to\infty$).


text:
\section{Introduction}
Particle Swarm Optimization (PSO) is a nature-inspired meta-heuristic,
first introduced by Eberhart and Kennedy in the year 1995~\cite{ken_eb_1995}, which
mimics the behavior of bird flocks and fish swarms. It is designed for
so-called continuous black-box optimization problems, i.\,e.,
objective functions that are not explicitly provided in a
closed formula. The algorithm consists of a
set $\{1,\ldots,N\}$ of particles, the
individuals of the swarm, that move through the $D$-dimensional
continuous search space. Each particle has a position $x$ and a
velocity $v$ that are updated via Movement Equations~\eqref{eq:movementv}
and~\eqref{eq:movementx} (see below). Furthermore each
particle remembers its best position found so far, its local attractor
$l$, and can access the best position any particle has found, the
global attractor $g$. The swarm operates in discrete time steps, where
one iteration consists of one application of the movement equations
for each particle.

For each dimension $d\in \{1,\ldots,D\}$ particle $n\in\{1,\ldots,N\}$
performs its move in iteration $t+1$ based on the following movement
equations:
\begin{align}
  v_{t+1,n,d}&=\chi \cdot v_{t,n,d}+c_l\cdot r_{t+1,n,d}\cdot(l_{t,n,d}-x_{t,n,d})+c_g\cdot s_{t+1,n,d}\cdot (g_{t,n,d}-x_{t,n,d}) \label{eq:movementv}\\
  x_{t+1,n,d}&=x_{t,n,d}+v_{t+1,n,d}, \label{eq:movementx}
\end{align}
where $r_{t+1,n,d}$ and $s_{t+1,n,d}$ are random variables on $[0,1]$
independently and uniformly drawn in every iteration for every particle and dimension.
$\chi$, $c_l$ and $c_g$ are constant parameters chosen by the user.  After the particles
finish their moves the local and global attractors get possibly
updated if better positions were found.

Since its introduction in 1995 PSO has become popular not only among
computer scientists as it can be easily implemented and adapted to
different problems. Many different variants of PSO were introduced in the
literature and analyzed.

A special focus of the analysis of PSO is on the convergence and
stagnation, i.\,e., the premature convergence to non-optimal points,
of the swarm. PSO as a meta-heuristic should fulfill the two
principals of exploration, i.\,e., finding new good positions, and
exploitation, i.\,e., improving on already found points. The
parameters $\chi$, $c_l$ and $c_g$ have a major impact on the balance
between exploration and exploitation. Good choices for the parameters
should allow for extensive exploration, while the particles should
ultimately converge to the global attractor.

Various publications supply discussions on parameter settings and
bounds on them such that convergence can be guaranteed. Some of those which
analyze the quality and/or convergence guarantees of different
parameter settings theoretically are (among many others)
\cite{BE:02,Cleg15,Gazi12,Harrison2018,JLY:07a,JLY:07,Poli09,SW:15,T:03}.

In \cite{SW:15} Schmitt and Wanka
use drift theory to prove the convergence to local optima on
one-dimensional objective functions and introduce a slightly modified
PSO to extend this analysis to $D$-dimensional objective functions.

In \cite{BE:02} Van den Bergh and Engelbrecht introduce a modified PSO
algorithm that adds an adaptive noise term at each iteration. They
prove that this PSO has a guaranteed convergence.

In \cite{T:03}, Trelea could formulate bounds on
the parameters of PSO such that the expected value of the position of a particle
converges to the global attractor. The bounds on
the parameters presented in
\cite{T:03} are $\chi<1$, $c_l+c_g>0$ and $c_l+c_g<4\cdot(\chi+1)$ and these
bounds are visualized in Figure~\ref{fig:convergencebounds} if $c_l=c_g=c$ by
the triangle enclosed by the black straight line, the right bound of the graph
and the $\chi$-axis (i.\,e., the triangle described by the points $(-1,0)$, $(1,4)$, and $(1,0)$).
Please note that there are parameter configurations where the expected values of
the particles' positions converge but actually the particles' positions diverge
(area between red and black curve in Figure~\ref{fig:convergencebounds} where
the black curve is larger than the red curve). On the other hand, there are
also cases where the expected values of the particles' positions diverge but actually the particles'
positions converge (area between red and black curve in
  Figure~\ref{fig:convergencebounds} where the red curve is larger than the
black curve). Therefore convergence of the expected value is neither a necessary
condition nor a sufficient condition for convergence of the particles'
positions.
Trelea could identify several different
convergence behaviors that the swarm could exhibit based on the
parameter selection.

In \cite{JLY:07a,JLY:07}, Jiang et\,al.\,could prove parameter bounds
that lead to a
convergence of the variance and expected value of the particles'
positions given the attractors are constant. Especially if the attractors coincide then the variance converges to zero.
If $c_l=c_g=c$ then the area for parameters leading to a convergence of the
variance is bounded by the blue curve which represents the inequation
$c_l+c_g=2 c \leq 24(1-\chi^2)/(7-5\chi)$ and the $\chi$-axis in
Figure~\ref{fig:convergencebounds}. In addition to \cite{JLY:07a,JLY:07} this bound has been proposed in \cite{Poli09}.
Please note that this is a sufficient condition to guarantee convergence of the particles' positions but it is not a necessary condition.

In this paper we focus on the convergence of the swarm, i.\,e., convergence of the particles' positions, to the global
attractor. We
mathematically prove and experimentally confirm that there are parameter sets
where the expected value and the variance of the particles' positions
do not converge, however, the positions of the swarm converge with probability
one. Please note that this is not a contradiction, which we will explain
in Section~\ref{sec:convergence_analysis} after Definition~\ref{def:convindicator}
in Example~\ref{ex:logisbetter} below.
In \cite{Harrison2018} the quality of different parameter settings is discussed
and various parameter sets are experimentally compared. There, good results
are also obtained while using parameter sets beyond the bound presented in
\cite{JLY:07a,JLY:07,Poli09}, where the variance of the particles' positions
diverges. This indicates that the bound for converging variance is not
the actual bound for the convergence of the swarm.
If attractors coincide and $c_l=c_g=c$ then the area for parameters leading to
a convergence of the particles' positions is bounded by the red curve and the
$\chi$-axis in Figure~\ref{fig:convergencebounds}. Please note that the slope
of the red curve directly to the left of $\chi=0$ is nearly twice as much as
the slope directly to the right of $\chi=0$, which is not a numerical error.
Consequently, it is an interesting observation itself, which could be analyzed
more in detail in a future work.
We introduce a new measure for the
convergence of the particles' positions and provide the actual parameter bounds that
lead to the convergence of the particles' positions. These bounds can be
obtained with arbitrary precision by numerical approximations using spline interpolation. For $\chi=0$ this bound
can also be obtained by closed theoretical analysis.
Hence, we extend the range of parameter settings which provably lead to convergence of PSO as specified in the following theorem.
\begin{theorem}{\color{white}{-}}\label{thm:figureClassification}
  \begin{itemize}
    \item The particles' positions converge if the parameters are chosen strictly between the red curve in Figure~\ref{fig:convergencebounds} and the $\chi$-axis.
    \item The particles' positions diverge if the parameters are chosen strictly outside the region between the red curve in Figure~\ref{fig:convergencebounds} and the $\chi$-axis.
  \end{itemize}
\end{theorem}

In Section~\ref{sec:convergence_analysis} we introduce our new
convergence indicator and calculate the difference between two
consecutive convergence indicators which can be used to prove bounds on
the parameters of the PSO algorithm such that convergence takes place. In
Section~\ref{sec:numeric}
we explain how these bounds can be calculated numerically and compare the
results with experiments confirming the results.

\begin{figure}[htb]
  \begin{center}
	\include{convergencebounds}
  \end{center}
  \caption{Bounds for the convergence on the expected position to zero (see also \cite{T:03}), on variance of the position to zero (see also \cite{JLY:07a,JLY:07}) and on the expected logarithm of position and velocity to minus infinity \label{fig:convergencebounds}}
\end{figure}

config: arxiv


TITLE: Survey of transformations related to the use of SAT solvers
QUESTION [13 upvotes]: I am starting to investigate the possibility of relying on a SAT solver to tackle an optimisation problem I'm interested in, and am currently looking for a survey that would feature examples of "clever" transformations to variants of SAT (i.e., transformations that result in a problem of reasonable size, since I'm not interested in proving hardness results but in actually solving the problem), approximately in the spirit of what can be found in the survey on cubic graphs by Greenlaw and Petreschi, if any comparison can be made between the two.
Has such a survey eluded me because it does not exist, or because I just missed it?

REPLY [9 votes]: Chapter 2 of the Handbook of Satisfiability surveys the aspects to bear in mind when designing those transformations, as well as a list of references that answer my question. This helped me find a few examples that one can have a look at to familiarise oneself with these transformations:

Chromatic number: see Iyama and Miyazaki
Clique: see Iyama and Miyazaki
Hamiltonian circuit: see Iyama and Miyazaki
$n$-queens: see Nadel
Stable marriage: see Gent et al.


TITLE: Property of permutation matrices
QUESTION [1 upvotes]: I need the formal proof of this fact. I define the permutation matrix in this way
given $\pi$ a permutation of $n$ elements its permutation matrix is: $${P}_\pi=\begin{bmatrix} {e}_{\pi_{1}} \\ \vdots
 \\{e}_{\pi_{n}} \end{bmatrix},$$ where ${e}_i$ is the row vector with $1$ in the $i$-th position and $0$ in every other position. How can I prove that $${P}_{\sigma}^T{P}_{\pi}^T={{P}_{\sigma\circ\pi}}^T\quad?$$
thanks!

REPLY [1 votes]: Observe that, for every $j=1,\ldots,n$,
$$
P_\pi e_j=e_{\pi^{-1}(j)}.
$$
Hence
$$
P_\pi P_{\sigma}e_j=P_\pi e_{\sigma^{-1}(j)}=e_{\pi^{-1}(\sigma^{-1}(j))}=e_{(\sigma\circ\pi)^{-1}(j)}=P_{\sigma\circ \pi}e_j.
$$
Thus
$$
P_\pi P_{\sigma}=P_{\sigma\circ \pi}\quad\text{or}\quad
P_\sigma^TP_{\pi}^T=P_{\sigma\circ \pi}^T.
$$


TITLE: Let $k \subseteq F \subseteq K$ be fields, and let $z \in K$. Prove that if $k(z) \colon k$ is finite, then $[F(z):F] \leq [k(z):k]$.
QUESTION [2 upvotes]: Let $k \subseteq F \subseteq K$ be fields, and let $z \in K$. Prove that if $k(z) \colon k$ is finite, then $[F(z):F] \leq [k(z):k]$. In particular, $[F(z):F]$ is finite.
If $k(z) \colon k$ is finite, then $[k(z):k]=\dim_{k}k(z)=n$ for some $n \in \mathbb{N}$. I was trying to prove that $F(z) \colon F$ is a subspace of $k(z) \colon k$. But doubt this happens.
The Hint over Rotman´s Advanced Algebra book says I should obtain an irreducible $p(x) \in k[x]$, and this polynomial should factor in $K[x]$. i dont really understand this hint.
Also, no problem seeing $[F(z):F]$ is finite once it is proved that $[F(z):F] \leq [k(z):k]$.

REPLY [3 votes]: As $z$ is finite over $k$, then it has a minimum polynomial $p(X)$ over $k$.
This means that $p(X)$ is monic, its coefficients are in $k$, $p(z)=0$ and
$p(X)$ is a factor of all polynomials $f(X)$ with coefficients in $k$ such that
$f(z)=0$.
But $k\subseteq F$, so that $z$ satisfies a polynomial equation over $k$
(namely $p(X)=0$). Therefore $z$ is finite over $F$, and so has a minimum
polynomial $q(X)$ over $F$.
This means that $q(X)$ is monic, its coefficients are in $F$, $q(z)=0$ and
$q(X)$ is a factor of all polynomials $f(X)$ with coefficients in $F$ such that
$f(z)=0$. But one of these polynomials is $p(X)$. Therefore $q(X)$ is a factor of
$p(X)$. As a consequence, $\deg q(X)\le\deg p(X)$.
But the degree of the extension $|k(z):k|$ equals $\deg p(X)$. Likewise
$|F(z):F|=\deg q(z)$. Therefore $|F(z):F|\le|k(z):k|$.


text:
\section{Numerical experiments}\label{sec:numerics}
In this section, we assess the statistical and computational efficiency of the proposed estimators on synthetic problems\footnote{The code to reproduce these experiments is available at this webpage~\url{https://gitlab.com/proussillon/wasserstein-estimation-sinkhorn-divergence}.}. While this is what our theory controls, the error on the scalar $W_2^2(\mu,\nu)$ is not a suitable quantity to plot as it might vanish spuriously as we vary other parameters (such as $n$ or~$\lambda$), which hinders interpretation of the plots (see Appendix~\ref{app:additionalnumerics}). Instead, we propose to observe a more stringent and stable quantity, namely the $L_1$ error on the estimated dual potential $\varphi$, which is the Lagrange multiplier associated to the first marginal constraint in Eq.~\eqref{eq:entropycost}. This dual potential is the gradient of $W_2^2(\mu,\nu)$ with respect to $\mu$~\cite[Prop.~7.17]{santambrogio2015optimal}, a quantity of high interest when training machine learning models with $W_2^2$ as a loss function.

Specifically, given $v^{(k)} \in \RR^n$ obtained after $k$ Sinkhorn's iterations with discrete marginals $\mu_n,\nu_n$ as in Eq.~\eqref{eq:sinkhorniteration}, we define the  function $\hat u_{\mu,\nu}(x) = -\lambda \log (\sum_{j=1}^n e^{(v^{(k)}_j-\frac12 \Vert x-y_j \Vert_2^2)/\lambda}q_j)$. The quantity we plot is $\int \vert \hat \varphi_{\lambda,n}(x) - \varphi(x)\vert \dd\mu(x)$ estimated via Monte Carlo integration or on a fine grid, where $\hat \varphi_{\lambda,n}$ is defined as follows: (i) $\hat \varphi_{\lambda,n} = 2\hat u_{\mu,\nu}$ for the biased estimator $\hat T_{\lambda,n}$, (ii) $\hat \varphi_{\lambda,n} =2\hat u_{\mu,\nu} - (\hat u_{\mu,\mu'}+\hat v_{\mu,\mu'})$ for the debiased estimator $\hat S_{\lambda,n}$ and (iii) $2\hat \varphi_{\lambda,n} - \hat \varphi_{\sqrt{2}\lambda,n}$ for the extrapolated estimator $\hat R_{\lambda,n}$.

\paragraph{Random sampling.} Figure~\ref{fig:sampling} shows the approximation error for the estimators $T_\lambda$, $S_\lambda$ and $R_\lambda$ in the random sampling setting. Here, $\mu,\nu\in \Pp(\RR^d)$ with $d=5$ are smooth elliptically contoured distributions with compact support and are such that the optimal potential $\varphi$ is quadratic and admits a closed-form, as well as the transport cost (see Appendix~\ref{app:additionalnumerics}). These properties guarantee that the conclusions of Proposition~\ref{prop:samplesinkhorn} apply. As expected, for a given $\lambda$, $S_\lambda$ and $R_\lambda$ have a much smaller bias than $T_\lambda$ (left plot). Looking at the performance as a function of $\lambda$ (middle plot), we see that the error is minimal for some $\lambda^*$ that is much larger than what is needed for $T_\lambda$ to achieve a comparable accuracy. Also, choosing the best $\lambda^*$ for each $n$ (right panel), we see that $S_{\lambda^*}$ has the same rate as the plug-in estimator (estimated with $T_\lambda$ with a small $\lambda$), with a better constant. We remark that $R_\lambda$ does not converge faster, which does not contradict ours results since we have no guarantee on the specific quantity plotted here.

\begin{figure}
  \centering

  \begin{subfigure}[b]{0.31\textwidth}
    \begin{tikzpicture}[scale = 0.5]
\begin{loglogaxis}[xlabel = number of samples $n$, ylabel = $L^1$ error on the first potential, no markers, legend pos=south west, grid = minor]

     \addplot+[ line width = 1.5pt, color = blue, error bars/.cd, y dir=both, y explicit] table [x= Nsamples, y= error_on_potentials, col sep=space, y error = std_on_potentials] {figures/OT_lambda_1_dimension_5.csv};
  \addlegendentry{$T_\lambda$}
  \addplot+[line width = 1.5pt, color = red, error bars/.cd, y dir=both, y explicit] table [x= Nsamples, y= error_on_potentials, col sep=space, y error = std_on_potentials] {figures/S_lambda_1_dimension_5.csv};
  \addlegendentry{$S_\lambda$}
  \addplot+[line width = 1.5pt, color = brown, error bars/.cd, y dir=both, y explicit] table [x= Nsamples, y= error_on_potentials, col sep=space, y error = std_on_potentials] {figures/R1_lambda_1_dimension_5.csv};
  \addlegendentry{$R_\lambda$}
                \addplot[thick, black] table [x= Nsamples, y= error_on_potentials, col sep=space] {figures/OT_lambda_0.01_dimension_5.csv};
    \addlegendentry{plug-in}

\end{loglogaxis}
\end{tikzpicture}
\end{subfigure}
\hfill
\begin{subfigure}[b]{0.31\textwidth}
    \begin{tikzpicture}[scale = 0.5]
\begin{loglogaxis}[xlabel = $\lambda$, ylabel = $L^1$ error on the first potential, no markers, legend pos=north west, grid = both, ymin = 2/100]
  \addplot+[ line width = 1.5pt, color = blue, error bars/.cd, y dir=both, y explicit] table [x= blur, y= error_on_potentials,y error = std_on_potentials, col sep=space]  {figures/OT_Nsamples_1000_dimension_5.csv};
  \addlegendentry{$T_\lambda$}
  \addplot+[line width = 1.5pt, color = red, error bars/.cd, y dir=both, y explicit] table [x= blur, y= error_on_potentials,y error = std_on_potentials, col sep=space]{figures/SD_Nsamples_1000_dimension_5.csv};
  \addlegendentry{$S_\lambda$}
  \addplot+[line width = 1.5pt, color = brown, error bars/.cd, y dir=both, y explicit] table [x= blur, y= error_on_potentials,y error = std_on_potentials, col sep=space] {figures/R1_Nsamples_1000_dimension_5.csv};
  \addlegendentry{$R_\lambda$}
\end{loglogaxis}
\end{tikzpicture}

\end{subfigure}
\hfill
\begin{subfigure}[b]{0.31\textwidth}
     \begin{tikzpicture}[scale = 0.5]
  \begin{loglogaxis}[xlabel = number of samples $n$, ylabel = $L^1$ error on the first potential, no markers, legend pos=north east, grid = minor, ymin = 1/100]
    \addplot[line width = 1.5pt, color = blue] table [x= Nsamples, y= error_on_potentials, col sep=space] {figures/OT_lambda_opt_dimension_5.csv};
    \addlegendentry{$T_{\lambda^*}$}
        \addplot[line width = 1.5pt, color = red] table [x= Nsamples, y= error_on_potentials, col sep=space] {figures/S_lambda_opt_dimension_5.csv};
        \addlegendentry{$S_{\lambda^*}$}
            \addplot[line width = 1.5pt, color = brown] table [x= Nsamples, y= error_on_potentials, col sep=space] {figures/R1_lambda_opt_dimension_5.csv};
  \addlegendentry{$R_{\lambda^*}$}
                \addplot[thick, black] table [x= Nsamples, y= error_on_potentials, col sep=space] {figures/OT_lambda_0.01_dimension_5_xmax10000.csv};
                \addlegendentry{plug-in}

\end{loglogaxis}
\end{tikzpicture}
\end{subfigure}
\caption{$L^1$ estimation error on the first potential for $\mu,\nu$ smooth compactly supported distributions with $d=5$. Left: as function of $n$ for $\lambda=1$. Middle: as a function of $\lambda$, for $n=10000$. Right: as a function of $n$ for the optimal $\lambda^*(n)$. Error bars show the standard deviation on 30 realizations.}\label{fig:sampling}
\end{figure}

Overall, these estimators require less samples and a larger $\lambda$ to achieve a given accuracy compared to $T_\lambda$, which leads to substantial computational gains.
This is illustrated on Figure~\ref{fig:computational_complexity} where for a target $L^1$ error on the potential, we chose the largest $\lambda$ and smallest $n$ that achieve this error, with $\lambda \in [0.1, 1]$ and $n \in [10, 100 000]$. We report the computational time using the Sinkhorn's iterations of Eq.~\eqref{eq:sinkhorniteration} stopped when the $\ell_1$-error on the marginals is below $10^{-5}$. We observe that for small target accuracies, the estimators $S_\lambda$ and $R_\lambda$ compare favorably to $T_\lambda$. In practical settings, one does not know \emph{a priori} the best choice for $\lambda$, but many machine learning tasks involving $W_2^2$ come with a performance criterion, in which case cross-validation can be used to select this parameter.

\begin{figure}[h]
              \centering
 \begin{tikzpicture}[scale = 0.5]
  \begin{axis}[xlabel = $L^1$ error on the first potential, ylabel = best computational time (seconds), no markers, legend pos=north east, grid = major, xmin = 0.025, ymin = 1/100, ymax = 0.2]
    \addplot[line width = 1.5pt, color = blue] table [x= Error , y= T, col sep=space] {figures/xp_ultime.csv};
    \addlegendentry{$T$}
    \addplot[line width = 1.5pt, color = red] table [x= Error , y= S, col sep=space] {figures/xp_ultime.csv};
    \addlegendentry{$S$}
   \addplot[line width = 1.5pt, color = brown] table [x= Error , y= R, col sep=space] {figures/xp_ultime.csv};
    \addlegendentry{$R$}
\end{axis}
\end{tikzpicture}
\caption{Best computational time achieved by the estimators to reach a given accuracy (after optimizing over $n$ and $\lambda$), for $\mu,\nu$ smooth compactly supported distributions with $d=5$. }
\label{fig:computational_complexity}
\end{figure}

\paragraph{Discretization on grids.}

Figure~\ref{fig-deterministic} shows the evolution of the errors for densities $(\mu,\nu)$ on the 1-D torus, the setting of Proposition~\ref{prop:gridperf}. In this case, one can compute efficiently the dual potentials $\varphi$ using cumulative functions~\cite{rabin2011transportation}.

This figure shows that, as expected, for a fixed $(h,\lambda)$ the error of $S_\lambda$ and $R_\lambda$ is systematically lower than that of $T_\lambda$. Even when selecting the optimal regularization $\lambda^\star(h)$ for each $h$ and for each method (which is a fair comparison), the error of $S_\lambda$ and $R_\lambda$ is still lower.

Furthermore, the optimal parameter $\lambda^\star(h)$ is systematically larger for $S_\lambda$ and $R_\lambda$.

Additional figures showing visual comparisons of the potentials and their approximations are provided in the appendix.

\begin{figure}[h]
		\centering
		\includegraphics[width=\linewidth]{figures/deterministic-curves}
	\caption{
	    Left: $L^1$ error on the first potential $\varphi$ as a function of the grid size $h$, for several value of $\lambda$.

	    Middle: same error, displayed as a function of $\lambda$, for several grid sizes $h$.

	    Right: evolution of the optimal regularization parameter $\lambda^\star(h)$ as a function of the grid size $h$.
	    }\label{fig-deterministic}
\end{figure}


TITLE: How to solve $ \log_8[\log_4(2x+1)] = \log_{27} 3$ for $x$?
QUESTION [2 upvotes]: I'm stuck on this question.

$$\log_8[\log_4(2x+1)] = \log_{27} 3$$

What I did was to manipulate the inner $\log_4$ to get $\log_8[\frac{\log_2(2x+1)}{\log_2 4}] = \frac{1}{3}$
Then manipulating the outer $\log_8$ to become $\frac{\log_2 8}{\log_2 2}$, I will get $2x+1 = 2^{\frac{4}{9}}$, which is not what the answer key wanted. For reference, answer key gives $x = 7\frac{1}{2}$.
Greatly appreciate any hint. Thanks!

REPLY [6 votes]: \begin{align}
\log_8[\log_4(2x+1)] &= \log_{27} 3\\
\log_8[\log_4(2x+1)] &= \frac{1}{3}\\
\log_4(2x+1) &= 8^\frac{1}{3}=2\\
2x+1&=4^2\\
x&=\frac{15}{2}
\end{align}


TITLE: Does this proof of a voting related lemma work? if so, how?
QUESTION [1 upvotes]: I'm attempting to read this PDF on  Arrow's impossibility theorem and ultrafilters. I find myself unconvinced that the proof of their Lemma 13 demonstrates what they say it does. I'm hoping someone can help shed light on whether the proof works, and if it does, how it works.
First, I will introduce (what I hope is,) enough of the descriptions of the notation used for others to be able to follow along without needing to read the PDF.
The PDF defines a voting system as a tuple $(A, V, F)$ consisting of a set of candidates $A$, a set of voters $V$ and a function $F$ which given a collection of voter preferences $(C_v)_{v ∈ V}$ produces a
chain of candidates, representing the election results.
The following potential properties of voting systems are defined as follows in the PDF:

(Unanimity) For any $a, b ∈ A$, for any preference profile $(C_v)_{v∈V}$, if for all $v∈V$, $a <^{C_v} b$, then in the election result $C$ also $a <^C b$. In other words,if $b$ is preferred  to $a$ by  every  voter,  then  in  the  election  result $b$ is  also preferred to $a$.
(Independence  of  irrelevant  alternatives)  For  any $a, b∈A$, for any two preference profiles $(C_v)_{v∈V}$ and $(D_v)_{v∈V}$, if for all $v∈V$, $a <^{C_v} b$ if and only if $a <^{D_v} b$, then $a <^C b$ if and only if $a <^D b$, where $C$ and $D$ are the election results for $(C_v)_{v∈V}$ and $(D_v)_{v∈V}$. In other words, introduction of other candidates than $a$ or $b$ should not influence their order in an election.

Also relevant is this definition of a decisive voter ...

For a voting system $(A, V, F)$, a subset $X$ of $V$ is called decisive if for any chain $C$ with universe $A$ and any preference profile $(C_v)_{v∈V}$, if $C_v=C$ for all $v∈X$, then $F((C_v)_{v∈V}) = C$.  We say that $v∈V$ is decisive if $\{v\}$ is decisive.

... which is used in this definition of what it means for a voter to be decisive for a pair of candidates:

For $(A, V, F)$ a voting system and $a \neq b$ both in $A$, we say that a subset $X$ of $V$ is decisive for the pair $(a, b)$ if for any chain $C$ with universe $A$ and any preference profile $(C_v)_{v∈V}$, if $a <^{C_v} b$ for all $v∈X$, then $a <^{F((C_v)_{v∈V})} b$. We say that $v∈V$ is decisive for $(a, b)$ if $\{v\}$ is decisive for $(a, b)$.

Here's a quote from the PDF regarding some further notation:

...we  introduce  some  notation.   Fix  a  voting  system  $(A, V, F)$  and  distinct $v_1, v_2, v_3 ∈ V$.  We will write (for example)
$
\begin{array}{lr}
v_1: & a_1a_2a_3... a_n \\
v_2: & b_1b_2b_3... b_m \\
v_3: & c_1c_2c_3... c_k \\
\hline \text{Outcome}: & d_1d_2d_3... d_r
\end{array} \\
$
If for some preference profile $(C_v)_{v ∈ V}$, if $C_{v_1} \vDash a_1< a_2. . . < a_n$, $C_{v_2} \vDash b_1< b_2<. . . < b_m$, and $C_{v_3} \vDash c_1< . . . < c_k$, then $ F((C_v)_{v ∈ V}) \vDash d_1< d_2< . . . < d_r.$  Note that, by the independence of irrelevant alternatives, if this holds for some preference profiles, this holds for all preference profiles satisfying the given orderings.

With all that background, we can finally introduce Lemma 13.

Lemma 13. Assume $(A, V, F)$ is a voting system with $|V|= 2$ satisfying unanimity and the  independence  of  irrelevant  alternatives. Assume $v∈V$ and $a, b, c$ are distinct elements of $A$. If $v$ is decisive for $(a, b)$, then $v$ is decisive for $(a, c)$ and decisive for $(b, c)$.
Proof. Write $V=\{v, w\}$. Since $v$* is decisive for $(a, b)$, we have:
$
\begin{array}{lr}
v: & ab \\
w: & ba \\
\hline \text{Outcome}: & ab
\end{array}
$
By unanimity ($c$ is after $b$ in both rankings):
$
\begin{array}{lr}
v: & abc \\
w: & bca \\
\hline \text{Outcome}: & abc
\end{array}
$
By the independence of irrelevant alternatives:
$ \begin{array}{lr}
v: & ac \\
w: & ca \\
\hline \text{Outcome}: & ac
\end{array}
$
This shows that $v$ is decisive for $(a, c)$.  Now using unanimity (adding $b$ before $a$ in both ranking)
$ \begin{array}{lr}
v: & bac \\
w: & cba \\
\hline \text{Outcome}: & bac
\end{array}
$
Thus by the independence of irrelevant alternatives:
$ \begin{array}{lr}
v: & bac \\
w: & cba \\
\hline \text{Outcome}: & bac
\end{array}
$
This shows that $v$ is decisive for $(b, c)$.

The above proof has 5 instances of the introduced notation involving rows of pertaining to voters above an outcome row. I'll call these steps 1 to five based on the order they appear in the proof.
The part I take issue with is, given we used $b$ in step 2 here ...:
$
\begin{array}{lr}
v: & abc \\
w: & bca \\
\hline \text{Outcome}: & abc
\end{array}
$
... I question the legitimacy of the move from step 3 here...:
$ \begin{array}{lr}
v: & ac \\
w: & ca \\
\hline \text{Outcome}: & ac
\end{array}
$
... to step 4 here:
$ \begin{array}{lr}
v: & bac \\
w: & cba \\
\hline \text{Outcome}: & bac
\end{array}
$
using the independence of irrelevant alternatives criteria. I think this move would be fine if we were adding in a heretofore unused candidate, say $d$, giving us
$ \begin{array}{lr}
v: & dac \\
w: & cda \\
\hline \text{Outcome}: & dac
\end{array}
$
but I don't see why it's legitimate to identify $b$ and $d$ here, particularly since the order is changed when the $b$ preference rankings were put back. If the order is changed, that seems like a distinct set of votes to me, so I don't see how it is legitimate to make conclusions that seems to rely on two different chains of candidates, (with different orders) as being the same.
It seems to me that this is trying to prove that given $v$ is decisive for $(a, b)$, $v$ is always decisive for $(a, c)$ and $(b, c)$, but it only seems to prove that given $v$ is decisive for $(a, b)$, $v$ may be decisive for $(a, c)$, given one set of canditate chains and separately may be decisive for $(b, c)$, given a different set of candidate chains, which does not seem to allow conclusions to be drawn about properties of a set of voters given all possible sets of candidate chains with a given universe.
Can someone explain if I've misunderstood something here? And if so how/what? Alternately, if I have in fact found a problem with this proof, can the same conclusion be drawn given these definitions?
*: this was $X$ in the original but I think $v$ is correct here.

REPLY [2 votes]: It would be more clear if we separated out the claim into two parts:

If $v$ is decisive for $(a,b)$ and $c$ is any third candidate, then $v$ is decisive for $(a,c)$.
If $v$ is decisive for $(a,b)$ and $c$ is any third candidate, then $v$ is decisive for $(c,b)$.

The first part of this claim is what we prove in the first half of Lemma 13.
The second part of this claim is what we prove in the second half of Lemma 13, but I've changed the variable names slightly for clarity. So let me give the proof again.
If $v$ is decisive for $(a,b)$, that means if $v$ has any ranking compatible with $a<b$ and $w$ has any ranking compatible with $b<a$, the outcome will have $a<b$.
Now suppose $v$ has any ranking compatible with $c<a<b$ and $w$ has any ranking compatible with $b<c<a$. The outcome will have $a<b$ by the above; it will have $c<a$ because both voters vote $c<a$; therefore the outcome will have $c<a<b$.
This means that if $v$ has a ranking compatible with $c<b$ and $w$ has a ranking compatible with $b<c$, then for one way to insert $a$ into those rankings, the outcome will have $c<b$. By independence of irrelevant alternatives, the outcome must have $c<b$ for all ways to insert $a$ into those rankings. The conclusion is exactly what it means for $v$ to be decisive for $(c,b)$.

To go from $(a,b)$ to $(b,c)$ in this way; first, apply the first half of the claim to go from $(a,b)$ to $(a,c)$. Then, apply the second half with $(a,c)$ playing the role of $(a,b)$ and $b$ playing the role of the third candidate to go from $(a,c)$ to $(b,c)$.


TITLE: Getting Equation From a Table
QUESTION [1 upvotes]: I have a simple problem that i am struggling with. In short i am given a number of volts a battery is putting out and from this i need to figure out how full it is. I have a table of 100 values, one corresponding to each percentage and i need to create and equation that if i plug in an amount of volts will give me a percentage value from it. I tried creating a trend line using excel, but it was hundreds off. Any advice on how to do this and or what software could do this would be appreciated. I've included one of the tables below.
1470,   100%
1440,   99%
1409,   98%
1386,   97%
1365,   96%
1348,   95%
1332,   94%
1317,   93%
1305,   92%
1295,   91%
1284,   90%
1275,   89%
1266,   88%
1258,   87%
1252,   86%
1245,   85%
1239,   84%
1234,   83%
1227,   82%
1225,   81%
1217,   80%
1213,   79%
1208,   78%
1202,   77%
1197,   76%
1193,   75%
1187,   74%
1184,   73%
1178,   72%
1176,   71%
1170,   70%
1167,   69%
1161,   68%
1158,   67%
1154,   66%
1149,   65%
1146,   64%
1142,   63%
1138,   62%
1136,   61%
1132,   60%
1128,   59%
1125,   58%
1122,   57%
1118,   56%
1117,   55%
1112,   54%
1109,   53%
1107,   52%
1104,   51%
1099,   50%
1096,   49%
1093,   48%
1090,   47%
1088,   46%
1085,   45%
1081,   44%
1080,   43%
1076,   42%
1073,   41%
1069,   40%
1066,   39%
1062,   38%
1058,   37%
1056,   36%
1052,   35%
1049,   34%
1044,   33%
1041,   32%
1038,   31%
1034,   30%
1030,   29%
1026,   28%
1021,   27%
1019,   26%
1013,   25%
1010,   24%
1004,   23%
1000,   22%
995,    21%
989,    20%
984,    19%
980,    18%
973,    17%
969,    16%
962,    15%
956,    14%
950,    13%
943,    12%
935,    11%
929,    10%
920,    9%
913,    8%
904,    7%
895,    6%
883,    5%
871,    4%
858,    3%
842,    2%
823,    1%
806,    0%

REPLY [2 votes]: I find that it's easier to get to a fit of the output in millivolts as a function of the battery capacity percentage. A plot of the capacity as a function of the percentage shows the problem:

This looks like an S-curve, but we have a nonzero slope at the end, which is not going to yield a good fit. Also an S-curve fit requires using non-linear fit methods, which can be awkward to implement correctly. If we interchange the two variables then the graph of percentage as a function of the millivolts looks like this:

This looks superficially like a 3rd degree curve with a clear point of inflexion in the middle. So, we can try to make a 3rd degree fit using straightforward linear fit methods. What you then find is that the fit is not so good at the edges. Such problems are then easy to remedy by adding exponential functions that are small everywhere except at the edges. I've obtained a good fit using a trial function of the form:
$$f(x) = a + b x + c x^2 +d x^3 + u \exp\left[\left(\frac{25-x}{5}\right)\right] +  v \exp\left[\left(\frac{x-75}{5}\right)\right]$$
This yields the fit values $a = 872.36$, $b = 7.42058$, $c = -0.0862508$, $d = 0.000583907$, $u = -0.452178$, $v = 0.897504$. The graph with the fit function looks like this:

Using nonlinear fitting methods we can try to fit the original data of the battery power as a function of the voltage, it turns out that it's quite difficult to get a good fit. Using Mathematica, the built in function "NonlinearModelFit" does not work well, it fails to converge for my choice of fit function. So, I had to use this to get to a reasonable fit with an inferior fit function and then try a linear combination of the output and another function using the linear fit method. I found the following result:
$$
\begin{split}
f(x) =& \frac{100.044 \left[\exp\left(0.0119075x\right)-12035\right]}{\exp\left(0.0119075 x\right)+468872} +\\
& 0.00023108 x \exp\left(\frac{x-1420}{40}\right)
\end{split}
$$
The graph with this function looks like:


text:
\begin{document}

\title{O-segments on topological measure spaces}

\author{Mohammad Javaheri}

\address{Department of Mathematics, University of Oregon, Eugene, Oregon 97403}

\email{javaheri@uoregon.edu}

\subjclass[2000]{Primary 28A25; Secondary 46G10}

\date{}

\keywords{Nonatomic measure, open segments, weakly outer regular measure.}

\begin{abstract}
Let $X$ be a topological space and $\mu$ be a nonatomic finite measure on a $\sigma$-algebra $\Sigma$ containing the Borel $\sigma$-algebra of $X$. We say $\mu$ is weakly outer regular, if for every $A \in \Sigma$ and $\epsilon>0$, there exists an open set $O$ such that $\mu(A \backslash O)=0$ and $\mu(O \backslash A)<\epsilon$. The main result of this paper is to show that if $f,g \in L^1(X,\Sigma, \mu)$ with $\int_X f d\mu=\int_X g d\mu=1$, then there exists an increasing family of open sets $u(t)$, $t\in [0,1]$, such that $u(0)=\emptyset$, $u(1)=X$, and $\int_{u(t)} f d\mu=\int_{u(t)} g d\mu=t$ for all $t\in [0,1]$. We also study a similar problem for a finite collection of integrable functions on general finite and $\sigma$-finite nonatomic measure spaces.

\end{abstract}

\maketitle

\section*{Introduction}

A (nonnegative) measure space $(X,\Sigma, \mu)$ is called nonatomic, if for every $A\in \Sigma$ with $\mu(A) >0$, there exists $B\subset A$ such that $0<\mu(B) <\mu(A)$. Sierpi\'{n}ski \cite{sie} showed that if $(X,\Sigma,\mu)$ is nonatomic, then the range of $\mu$ is $[0,\mu(X)]$. A stronger result \cite[Theorem 15]{af} states that there exists a continuum of values for a nonatomic finite measure along increasing sequences of measurable sets. To make this statement precise, we need the following definition.

\begin{define} \label{def1}
Let $(X,\Sigma, \mu)$ be a finite (respectively $\sigma$-finite) measure space and $\eta$ be a $\sigma$-additive function on $\Sigma$. An increasing family $u(t)\in \Sigma$, $t\in [0,1]$ (respectively $t\in [0,\infty)$), is called a segment for $\eta$, if $u(0)=\emptyset$, $u(1)=X$ (respectively, $\lim u(t)=X$ as $t\rightarrow \infty$), $u(s)\subset u(t)$ if $s<t$, and
\begin{equation}
\eta(u(t))=t\eta(X)~,~\forall t\in [0,1]~,~(\mbox{respectively}~\eta(u(t))=t~,~\forall t\geq 0)~.
\end{equation}
\end{define}

In the sequel, the $\sigma$-additive function $\mu_f: \Sigma \rightarrow \mathbb{R}$ induced by $f\in L^1(X,\Sigma, \mu)$ is defined by $\mu_f(E)=\int_E f d\mu$, $E\in \Sigma$.

\begin{thm}\label{finite} \cite{af}
Let $S$ be a finite collection of integrable functions on a nonatomic finite measure space. Then there exists a common segment for all $\mu_f$, $f\in S$.
\end{thm}

We will give an elementary second proof of this theorem in \S2. The conclusion of Theorem \ref{finite} does not necessarily hold if the collection $S$ contains infinitely many functions (see \S3). Next, we will consider the problem of finding common segments on $\sigma$-finite nonatomic measure spaces. Here and throughout, by a $\sigma$-finite measure space, we mean a measure space $(X,\Sigma, \mu)$ such that $\mu(X)=\infty$ and $X=\cup_i X_i$ for a countable collection of finite-measure subsets $X_i \in \Sigma$. We prove the following theorem in \S4.

\begin{thm}\label{sigmafinite}
Let $(X,\Sigma, \mu)$ be a $\sigma$-finite nonatomic measure space. Let $S$ be a finite collection of functions such that $f-1 \in L^1(X,\Sigma, \mu)$ for all $f\in S$ and
\begin{equation} \label{intz}
\int_X (f-1) d\mu=0~,~\forall f \in S~.\end{equation} Then there exists a common segment for all $\mu_f$, $f\in S$.
\end{thm}

In \S5, we consider the problem of finding common O-segments on topological measure spaces. By an O-segment for a $\sigma$-additive function $\eta$, we mean a segment $u(t)$ for $\eta$ in the sense of Definition \ref{def1} such that, in addition, $u(t)$ is open for all $t$. To state the main results of \S5, we recall the following definitions.

\begin{define}\label{deftop}
Let $\mu$ be a finite measure on a topological space $X$ such that every open set is measurable. Let $A$ be a measurable set.
\begin{itemize}
\item[i)] We say $A$ is \emph{approximable} by open sets, if for every $\epsilon>0$ there exists an open set $O$ such that $\mu(A \oplus O) < \epsilon$.
\item[ii)] The measure $\mu$ is called \emph{weakly outer regular} at $A$, if for every $\epsilon>0$, there exists an open set $O$ such that $\mu(A \backslash O)=0$ and $\mu(O \backslash A)< \epsilon$.
\item[iii)] The measure $\mu$ is called \emph{outer regular} at $A$, if for every $\epsilon>0$, there exists an open set $O$ such that $A \subset O$ and $\mu(O \backslash A)<\epsilon$.
\end{itemize}
\end{define}

In Theorem \ref{oseg}, we show that every nonatomic measure $\mu$ in which all measurable sets are approximable by open sets admits an O-segment. More importantly, one has the following theorem.

\begin{thm} \label{osegm}
Let $(X, \Sigma, \mu)$ be a topological measure space such that $\mu$ is finite, nonatomic, and weakly outer regular. Let $f,g \in L^1(X,\Sigma, \mu)$. Then there exists a common O-segment for $\mu_f$ and $\mu_g$.
\end{thm}

\section{Common segments on finite measure spaces}

\begin{define} \label{def4} Let $(X,\Sigma,\mu)$ be a nonatomic finite measure space and $\eta$ be a $\sigma$-additive function on $\Sigma$. A \emph{partial segment} for $\eta$ is a pair $(u,\Lambda)$ such that $u: \Lambda \subseteq [0,1] \rightarrow \Sigma~$ has the following properties:

\begin{itemize}
  \item[ i)] $u(0)=\emptyset$ and $u(1)=X$,
  \item[ ii)]$u(s) \subset u(t)$ if $s<t$ and $s,t\in \Lambda$,
  \item[ iii)]$\eta(u(t))=t \eta(X)$ for all $t \in \Lambda$.
\end{itemize}
\end{define}
The set of all partial segments for $\mu$ is denoted by $\mathcal F$. The set $\mathcal F$ is nonempty; for example $(u,\{0,1\})\in {\mathcal F}$ where $u(0)=\emptyset$ and $u(1)=X$. We define a partial ordering $\preceq$ on $\mathcal F$ by setting $(u_1,\Lambda_1) \preceq (u_2, \Lambda_2)$ if and only if $\Lambda_1 \subseteq \Lambda_2$ and $u_1(t)=u_2(t)$ for all $t\in \Lambda_1$. We also let $\prec$ be the quazi-order associated with $\preceq$.

\begin{prop}\label{meas}
Let $(X,\Sigma, \mu)$ be a nonatomic finite measure space. Then for every partial segment $(u_0,\Lambda_0)$ of $\mathcal F$ there exists $(u,[0,1]) \in \mathcal F$ such that $(u_0,\Lambda_0) \preceq (u, [0,1])$. In particular, $u$ is a segment for $\mu$.
\end{prop}

\begin{proof}
Without loss of generality, we assume $\mu(X)=1$ (the case $\mu(X)=0$ has the trivial solution $u(t)=X$ for all $t\in [0,1]$). For a fixed $(u_0,\Lambda_0) \in {\mathcal F}$, we let
\begin{equation}{\mathcal U}=\{(u,\Lambda) \in {\mathcal F}| (u_0,\Lambda_0) \preceq (u,\Lambda) \}~.\end{equation}
We first show that every chain (i.e. totally ordered set) in $({\mathcal U}, \preceq)$ has an upper bound. Let ${\mathcal C}=\{(u_\alpha, \Lambda_\alpha)|\alpha \in J\}$ be a chain, where $J$ is some index set. We let $\Lambda=\cup_{\alpha \in J} \Lambda_\alpha$ and define $u: \Lambda \rightarrow \Sigma$ as follows. For $t\in \Lambda$, choose $\alpha \in S$ such that $t\in \Lambda_\alpha$ and set $u(t)=u_\alpha(t)$. Since $\mathcal C$ is a chain, $u$ is well-defined and $(u,\Lambda) \in {\mathcal U}$ is an upper bound for $\mathcal C$.

Now, by the Zorn's lemma, $\mathcal U$ contains a maximal element $(u, \Lambda)$. We prove that $\Lambda=[0,1]$.
\\

\emph{Step 1}. The set $\Lambda$ is a closed subset of $[0,1]$. Otherwise, there would exist a monotone sequence $t_i \in \Lambda$ such that $t^\prime=\lim t_i \notin \Lambda$. Define $(u^\prime,\Lambda^\prime) \in {\mathcal U}$ by setting $\Lambda^\prime=\Lambda \cup \{t^\prime\}$, $u^\prime(t)=u(t)$ for all $t\in \Lambda$, and
\begin{equation}u^\prime(t^\prime)=\lim_{i \rightarrow \infty} u(t_i)~,\end{equation}
where $\lim u(t_i)$ is the union (respectively intersection) of the $u(t_i)$'s if the sequence $t_i$ is increasing (respectively decreasing). It is straightforward to check that $(u,\Lambda) \prec (u^\prime,\Lambda^\prime)\in {\mathcal U}$. Since $(u,\Lambda)$ is maximal, this is a contradiction, and so $\Lambda$ is closed.
\\

\emph{Step 2.} The complement of $\Lambda$ in $[0,1]$ is empty. Otherwise, the complement of $\Lambda$ can be written as a union of disjoint open intervals \cite{c}. Let $(a,b)$ be one of such intervals. In particular, $a,b\in \Lambda$. Let $D=u(b) \backslash u(a)$. Since $\mu$ is nonatomic, there exists $E\in \Sigma$ with $E\subset D$ and $0<\mu(E)<\mu(D)=b-a$. We define $(u^\prime, \Lambda^\prime) \in {\mathcal U}$ by setting $\Lambda^\prime=\Lambda \cup \{a+\mu(E)\}$, $u^\prime(t)=u(t)$ for all $t\in \Lambda$, and $u^\prime(a+\mu(E))=u(a) \cup E$. Clearly $(u, \Lambda) \prec (u^\prime, \Lambda^\prime)$ which is in contradiction with $(u,\Lambda)$ being maximal.

It follows that $\Lambda=[0,1]$, and so $u$ is a segment that extends $u_0$.
\end{proof}

Proposition \ref{meas} implies that there exists at least one segment for any nonatomic finite measure space. The converse of this statement is also true.

\begin{prop}
Suppose $(X,\Sigma, \mu)$ is a finite measure space. Then $(X,\Sigma, \mu)$ is nonatomic if and only if it admits a segment.
\end{prop}

\begin{proof}
It is left to show that if $(X,\Sigma,\mu)$ has a segment, then it is nonatomic. Let $Y$ be any measurable subset of $X$ with $\mu(Y)>0$. We show that $(Y,\Sigma \cap Y, \mu)$ admits a segment, where the measure is induced by $(X,\Sigma, \mu)$.
Let $u:[0,1] \rightarrow \Sigma$ be a segment for $(X,\Sigma,\mu)$. Let $v(t)=Y \cap u(t)$ and $f(t)=\mu(v(t))$. We show that $f$ is a continuous and non-decreasing function from $[0,1]$ onto $[0,\mu(Y)]$. Clearly if $t<s$, we have $v(t) \subset v(s)$ and so $f(t) \leq f(s)$. Also if $t_i \rightarrow t$, then
\begin{equation}v(t_i)\oplus v(t)=Y\cap (u(t_i) \oplus u(t))\end{equation}
and so $|f(t)-f(t_i)| \leq \mu(v(t_i)\oplus v(t)) \leq \mu(u(t_i)\oplus u(t))=|t-t_i| \mu(X)\rightarrow 0$. Since $f$ is continuous and non-decreasing, $f$ is onto $[0,\mu(Y)]$. Finally, we define:
\begin{equation}w(t)=\bigcup_{f(s) \leq t \mu(Y)}v(s)~,~t\in [0,1]\end{equation}
Then $w$ is a segment for $Y$, and so $(X,\Sigma, \mu)$ is nonatomic.
\end{proof}

In the remaining of this section, we prove Theorem \ref{finite}. First, we need a lemma.

\begin{lem}\label{analysis}
Let $F$ be a real-valued continuous functions on $[0,1]$ such that $F(0)=0$ and $F(1)=1$. Then there exists $c,d \in [0,1]$ such that
\begin{equation}F(d)-F(c)=d-c={1 \over 2}~.\end{equation}
\end{lem}

\begin{proof}
Let $G(c)=F(c+1/2)-F(c)-1/2$, for $c\in [0,1/2]$. Then $G(0)+G(1/2)=0$ which implies that either $G(0)=G(1/2)=0$ or, by the mean-value theorem, there exists $c\in (0,1/2)$ such that $G(c)=0$. In either case, we have a solution of $G(c)=0$, and the lemma follows for $c$, $d=c+1/2$.
\end{proof}

\noindent \textbf{Proof of Theorem \ref{finite}.} Without loss of generality, we assume that $\mu(X)=1$, $1 \in S$, and that $\mu_{f}(X)=1$, $\forall f \in S$. If $\mu_{f}(X) \neq 0$, then one replaces $f$ by $f/(\mu_{f}(X))$, otherwise one replaces $f$ by $f+1$. Any common segment for the new family is a common segment for the original family of functions.

Proof is by induction on $n$. The case $n=1$ follows from Proposition \ref{meas} (recall that $1 \in S$). Suppose the assertion holds when $|S|\leq n$. Let $f_1,\ldots, f_{n+1}$ be a collection of $n+1$ integrable functions such that $f_1 \equiv 1$. Let $\mathcal G$ be the set of pairs $(u,\Lambda)$ that are partial segments for every $\mu_{f_i}$, $i\leq n+1$. The set $\mathcal G$ is nonempty; for example $(u,\{0,1\}) \in {\mathcal G}$, where $u(0)=\emptyset$ and $u(1)=X$. Next, as in the proof of Proposition \ref{meas}, one can show that every chain in $\mathcal G$ has an upper bound. Using the Zorn's lemma, we obtain a maximal element $(u,\Lambda)\in {\mathcal G}$. The set $\Lambda$ is closed (\emph{c.f.} step 1 of the proof of Proposition \ref{meas}). It is left to show that the complement of $\Lambda$ in $[0,1]$ is empty. If nonempty, $\Lambda^c$ can be written as a disjoint union of nonempty open intervals. Let $(a,b)$ be one of such intervals and set $X^\prime=u(b)\backslash u(a)$. By the inductive hypothesis, there exists a segment $v$ for $\mu_{f_i}$, $i\leq n$, on $X^\prime$. Let $F:[0,1] \rightarrow \mathbb{R}$ be the function
\begin{equation}F(t)={1 \over {b-a}}\int_{v(t)} f_{n+1} d\mu~,~t\in [0,1]~.\end{equation}
Then $F(0)=0$ and $F(1)=1$. By Lemma \ref{analysis}, there exists an interval $[c,d]\subset [0,1]$ such that
\begin{equation} \label{int2}
{1 \over {b-a}}\int_{v(d) \backslash v(c)} f_{n+1} d\mu =F(d)-F(c)=d-c={1 \over 2}~.
\end{equation}
We define $(u^\prime, \Lambda^\prime) \in {\mathcal G}$ by setting $\Lambda^\prime=\Lambda \cup \{(a+b)/2\}$, $u^\prime (t)=u(t)$ for $t\in \Lambda$, and $u^\prime((a+b)/2)=u(a) \cup v(d)\backslash v(c)$. Equation \eqref{int2} implies that $\mu_{f_{n+1}}(u^\prime((a+b)/2))=a+(b-a)/2=(a+b)/2$. On the other hand, for $i\leq n$, we have $\mu_{f_i}(u^\prime((a+b)/2))=a+ \mu_{f_i}(v(d)\backslash v(c))=a+\mu (v(d)\backslash v(c))=a+(b-a)/2=(a+b)/2$. It follows that $(u,\Lambda) \prec (u^\prime, \Lambda^\prime) \in {\mathcal G}$. This is a contradiction, and so $\Lambda=[0,1]$ and $u$ is a common segment for all of the $f_i$'s, $i\leq n+1$. This completes the proof of the inductive step and the theorem follows.
\hfill $\square$

\section{A counterexample}

In this section, we show that Theorem \ref{finite} may fail if $S$ is not finite. For positive integers $p,q$ with $p<q$, let
\begin{equation}
 I_{p,q}=\left [ {{2p-1} \over {2q}}, {{2p+1} \over {2q}} \right ]~.
\end{equation}
We define a function $f_{p,q}$ on $[0,1]$ by setting $f_{p,q}(t)=q$ for $t\in I_{p,q}$ and zero otherwise. We claim that there is no Lebesgue-measurable set $E$ with $\int_E f_{p,q} d\lambda =1/2$, where throughout this section, $\lambda$ refers to the Lebesgue measure on $[0,1]$. This will imply that the given family of integrable functions has no common segment. First, we need a lemma:

\begin{lem}\label{almost}
Let $E$ be a Lebesgue-measurable subset of $[0,1]$ such that $\lambda(E)>0$. Then for any $r\in (0,1)$ there exists a subinterval $J$ such that
\begin{equation}\lambda (E \cap J) \geq r \lambda (J)~.\end{equation}
\end{lem}

\begin{proof}
Choose $\epsilon>0$ such that $\epsilon<(1-r) \lambda (E)$. Let $U$ be an open set such that $E \subseteq U$ and $\lambda (U \backslash E)< \epsilon$. One can write $U$ as a disjoint union of open intervals $J_i$, $i\geq 1$. If $\lambda(E \cap J_i) \leq r \lambda(J_i)$ for all $i$, it would follow that $\lambda(E) \leq r \lambda(U)$. But then $\lambda(U \backslash E) \geq (1-r) \lambda(U) \geq (1-r) \lambda (E)>\epsilon$, which is a contradiction. It follows that for some $i$, we have $\lambda(E \cap J_i) \geq r \lambda(J_i)$, and the lemma follows.
\end{proof}

Now suppose there was a Lebesgue-measurable set $E$ such that $\int_{E} f_{p,q}d \lambda=1/2$ or equivalently, suppose for all $p,q$, we had
\begin{equation}\label{inter}
\lambda \left ( E \cap I_{p,q} \right )={1 \over {2q}}~.
\end{equation}
Then by lemma \ref{almost} there would exist an interval $(a,b) \subset [0,1]$ such that
\begin{equation} \label{there}
 \lambda(E \cap (a,b))>{3 \over 4}(b-a)~.
 \end{equation}
We choose $q$ such that $q>6/(b-a)$. Let $p=\lceil qa \rceil$, the smallest integer greater than or equal to $qa$, and $r=\lfloor qb \rfloor$, the largest integer less than or equal to $qb$. It follows from \eqref{inter} that
\begin{eqnarray}\label{contra} \nonumber
 \lambda (E \cap (a,b)) \leq {1 \over q}+\sum_{i=p}^r \lambda (E \cap I_{i,q}) & \leq &  {1 \over {q}}+{{r-p+1} \over {2q}}\\
 & \leq & {{b-a} \over 2} +{3 \over {2q}}<{3 \over 4}(b-a)~.
\end{eqnarray}
The inequalities \eqref{there} and \eqref{contra} contradict each other. This contradiction implies that there is no common segment for the family $f_{p,q}$.

\section{Common segments on sigma-finite measure spaces}

In this section, $(X,\Sigma, \mu)$ is a $\sigma$-finite nonatomic measure space. In particular, there exists a sequence $X_i \in \Sigma$, $i\geq 1$ such that  $X_0=\emptyset$, $X_i \subset X_{i+1}$, $\mu(X_i)<\mu(X_{i+1})$, and $\cup_i X_i=X$. Then, by Theorem \ref{meas}, one proceeds to find segments $u_i: [0, 1] \rightarrow \Sigma$ for $X_{i+1} \backslash X_i$ with the measure induced by $(X,\Sigma, \mu)$. By gluing these segments, one gets a segment for $\mu$. More precisely, we defines $u: [0,\infty) \rightarrow \Sigma$ by setting
\begin{equation}\label{glue}
u(t)= X_i \cup u_i \left ( {{t-\mu(X_i)} \over {\mu(X_{i+1})-\mu(X_i)}} \right )~,~t\in [\mu(X_i), \mu(X_{i+1})]~,~i\geq 0~.\end{equation}
Now, we are ready to present the proof of Theorem \ref{sigmafinite}.
\\
\\
\textbf{Proof of Theorem \ref{sigmafinite}.}
We may assume that $1\in S$. The proof is by induction on $|S|$. We have already shown the existence of a segment for $\mu$ and so the claim is true for $n=1$. Thus, suppose the claim is true for $n$ and let $f_i$, $i\leq n+1$ be functions on $X$ such that $f_1 \equiv 1$, $f_i-1 \in L^1(X,\Sigma, \mu)$, and $\int_X (f_i-1)d\mu=0$. By the inductive hypothesis, there exists a common segment $v(t)$ for $\mu_{f_i}$, $i\leq n$. We define
\begin{equation}F(t)=\int_{v(t)} (f_{n+1}-1) d\mu~,~t\in [0,\infty)~.\end{equation}
Then $F$ is a continuous function and $\lim F(t)=0$ as $t\rightarrow \infty$. In light of Theorem \ref{finite} and the gluing procedure presented by \eqref{glue}, it is sufficient to show that there is an increasing sequence $Y_k \in \Sigma$, $k\geq 1$, such that $X=\cup_i Y_i$ and $\mu_{f_i}(Y_k)=\mu(Y_k)<\infty$ for all $k\geq 1$ and $i\leq n+1$. We define the $Y_k$'s separately in each of the following two cases:
\\

\emph{Case i)} There is a sequence $t_k \rightarrow \infty$ such that $F(t_k)=0$ for all $k\geq 1$. Then let $Y_k=v(t_{k})$, $k\geq 1$. \\

\emph{Case ii)} $T=\max \{t: F(t)=0 \}<\infty$. Without loss of generality, suppose $F(t)>0$ for $t>T$ (the other case is quite similar). Since $F(0)=\lim_{t \rightarrow \infty} F(t)=0$, there should exist sequences $t_k,s_k$, $k\geq 1$ such that $t_k \uparrow \infty$, $s_k \downarrow T$, $s_1<t_1$, and $F(t_k)=F(s_k)$, $\forall k\geq 1$. Now, let $W=\cap_k v(s_k)$ and set
\begin{equation}Y_k=W \cup (v(t_k) \backslash v(s_k))~.\end{equation}
Then for $k\leq n$, we have
\begin{equation} \label{fin1}
\mu_{f_i}(Y_k)=\mu(Y_k)=T+ (t_k-s_k)<\infty~.
\end{equation}
Moreover,
\begin{equation} \label{fin2}
\mu_{f_{i+1}}(Y_k) =\mu(Y_k)+F(T)+F(t_k)-F(s_k)=\mu(Y_k)~.
\end{equation}
Note that in either case $X=\cup_k Y_k$. Finally, we let $X_j=\cup_{k\leq j} Y_k$, $j\geq 0$, and apply the formula \eqref{glue} to obtain a common segment for all $\mu_{f_i}$, $i\leq n+1$.
\hfill $\square$
\\

The conclusion of Theorem \ref{sigmafinite} does not hold if the collection $S$ is infinite. As a counterexample,  let $f_{p,q}$ be the family of functions defined in section 3 and set $\bar f_{p,q}(x)=f_{p,q} (x \mod 1)$ for all $x \in \mathbb{R}$. Then there is no set $E$ such that $\mu_{\bar f_{p,q}}(E)=1/2$ for all $p,q$. It follows that the collection $\bar f_{p,q}$ does not admit a common segment.

\section{O-segments on topological measure spaces}

Let $(X,\Sigma, \mu)$ be a topological measure space so that every open set is measurable. In this section, we prove the existence of O-segments for measure $\mu$ under the conditions that every $\mu$-measurable set is approximable by open sets and $\mu$ is nonatomic.

It is worth mentioning that even if the image of $\mu$ on the open sets is $[0,\mu(X)]$, it is not guaranteed that $\mu$ admits an O-segment. As a counterexample, let $X=\cup_n (2n,2n+1)$, $n\geq 1$, with the following topology and  measure. The open sets are only the intervals $(2n,2n+1)$ and their unions. The measure $\mu$ on $(2n,2n+1)$ is given by $\lambda/2^n$, where $\lambda$ is the usual Lebesgue measure. Then $\mu$ is nonatomic and the image of $\mu$ on open sets is $[0,\mu(X)]$ but $\mu$ does not admit an O-segment.

\begin{lem} \label{borel}
Let $(X,\Sigma,\mu)$ be a topological measure space such that $\mu$ is nonatomic and every $\mu$-measurable set is approximable by open sets. Then for any open set $A\in \Sigma$ and $a\in [\mu(A),\mu(X)]$ there exists an open set $O$ such that $A \subset O$ and $\mu(O)=a$.
\end{lem}
\begin{proof}
We define an increasing sequence $O_n$, $n\geq 1$, of open sets inductively such that $A \subset O_n$ for all $n\geq 0$ and
\begin{equation}\label{ineq1}
a+{{3^n}\over {4^n}} (\mu(A)-a) \leq \mu(O_n) \leq a+{1 \over {4^n}}(\mu(A)-a)~.
\end{equation}
We set $O_0=A$. Suppose we have defined $O_n$ such that \eqref{ineq1} holds, and we proceed to define $O_{n+1}$. Since $\mu$ is nonatomic, the set $X \backslash O_n$ contains a subset $A_{n+1} \in \Sigma$ such that
\begin{equation}\mu(A_{n+1})={1 \over 2} \left (a-\mu (O_n) \right )~.\end{equation}
Since $A_{n+1}$ is approximable by open sets, there exists an open set $U_{n+1}$ such that $A_{n+1} \subseteq U_{n+1}$ and
\begin{equation}\mu (U_{n+1} \oplus A_{n+1}) <  {1 \over 4} (a- \mu (O_n) )~,\end{equation}
We let $O_{n+1}=O_n \cup U_{n+1}$. Then, one has
\begin{eqnarray} \nonumber
\mu (O_{n+1}) &\leq&  \mu (O_n)+ \mu (U_{n+1} \cap A_{n+1})+ \mu ({U_{n+1} \backslash A_{n+1}}) \\  \nonumber
& \leq & \mu (O_n) + {3 \over 4} (a-\mu(O_n)) \leq  {3 \over 4} a +{1 \over 4}\mu (O_n) \\
& \leq & {3 \over 4} a +{1 \over 4} \left (a+ {{1} \over {4^n}}(\mu(A)-a) \right ) \leq a+ {{1} \over {4^{n+1}}}(\mu(A)-a)~.
\end{eqnarray}
Similarly, we have
\begin{eqnarray} \nonumber
\mu (O_{n+1}) &\geq&  \mu (O_n)+ \mu (A_{n+1} )- \mu (A_{n+1} \backslash U_{n+1}) \\  \nonumber
& \geq & \mu (O_n) + {1 \over 4} (a-\mu(O_n)) \geq  {1 \over 4} a +{3 \over 4}\mu (O_n) \\
& \geq & {1 \over 4} a +{3 \over 4} \left ( a+{{3^n}\over {4^n}} (\mu(A)-a) \right ) \geq a+ {{3^{n+1}} \over {4^{n+1}}} (\mu(A)-a)~.
\end{eqnarray}
Now, the set $O=\cup_n O_n$ is open, $A \subset O$, and $\mu(O)=a$.
\end{proof}

\begin{prop}\label{oseg}
Let $(X,\Sigma, \mu)$ be a topological measure space such that $\mu$ is finite and nonatomic, and suppose that every measurable set is approximable by open sets. Then for any open set $A$ with $\mu(A)<\infty$ there exists an O-segment $u(t)$ such that $u(\mu(A))=A$.
\end{prop}

\begin{proof}
Without loss of generality, assume that $\mu(X)=1$. We construct a sequence  of open sets $O_{m,n}$, $0\leq m\leq 2^n$, inductively on $n$ such that $O_{0,0}=A$, $O_{1,0}=X$, and
\begin{eqnarray} \label{orelations}
&&\mu (O_{m,n})=\mu(A)+ {m \over {2^n}}(1-\mu(A))~,\\ \label{orel2}
&&O_{m,n} \subseteq O_{k,l},~\mbox{if}~{m \over {2^n}} \leq {k \over {2^l}}~,\\ \label{orel3}
&&O_{m,n} = O_{k,l},~\mbox{if}~{m \over {2^n}} = {k \over {2^l}}~.
\end{eqnarray}
Suppose open sets $O_{m,n}$ are defined for $n$ and all $m\leq 2^n$ such that \eqref{orelations}-\eqref{orel3} hold. For a given pair $(m,n+1)$, choose $k$ such that $2k \leq m \leq 2k+1$. If $m=2k$, we simply set $O_{m,n+1}=O_{k,n}$. Otherwise, by Lemma \ref{borel} there exists an open set $O_{m,n+1}$ such that $O_{k,n} \subset O_{m,n+1} \subset O_{k+1,n}$ and $\mu(O_{m,n+1})=\mu(A)+m2^{-n-1}(1-\mu(A))$.

Next, for arbitrary $t\in [\mu(A),1]$, we define:
\begin{equation}u(t)=\bigcup_{m/2^n \leq t} O_{m,n}~.\end{equation}
To define $u$ on the interval $[0,\mu(A)]$, we repeat the above argument with $A=\emptyset$ and $X=A$.
\end{proof}

Clearly, in a weakly regular measure space, every measurable set is approximable by open sets. In the case of weakly outer regular measures, the statement of Proposition \ref{oseg} can be made stronger.

\begin{cor}\label{oseg2}
Let $(X,\Sigma, \mu)$ be a topological measure space such that $\mu$ is finite, nonatomic, and weakly outer regular. Then for any measurable set $A$, there exists a partial O-segment $(u,(\mu(A)/\mu(X),1])$ such that
\begin{equation}\label{condmu}
\mu(A \backslash u(t))=0~,~\forall t>\mu(A)/\mu(X)~.
\end{equation}
\end{cor}

\begin{proof}
Since $\mu$ is weakly outer regular, there exists a decreasing sequence of open sets $U_i$, $i\geq 1$, such that $U_1=X$, $\mu(A\backslash U_i)=0$ and $\mu(U_i \backslash A) \downarrow 0$ as $i\rightarrow \infty$. By Proposition \ref{oseg}, we can find O-segments stretching from $U_{i+1}$ to $U_{i}$. By gluing these O-segments, we obtain an O-segment satisfying \eqref{condmu}.
\end{proof}

If $\mu$ is $\sigma$-finite, nonatomic, and outer regular, then a similar proof shows that for any $A\in \Sigma$, there exists a partial O-segment $(u, (\mu(A), \infty))$ such that $A\subset u(t)$ for all $t>\mu(A)$. In the next theorem, we prove the existence of common O-segments for measures that are induced by two integrable functions. We first have the following lemma.

\begin{lem}\label{delta}
Let $(X,\Sigma, \mu)$ be a measure space and $S$ be a finite collection of integrable functions. Then for $\epsilon>0$ there exists $\delta=\delta(\epsilon)>0$ such that if $\mu(A)<\delta$, then $\int_A |f| d\mu<\epsilon$, for all $f \in S$.
\end{lem}

\begin{proof}
Choose $C>0$ such that $\int_X |f| d\mu < C$ for all $f\in S$. Also let $X(M,f)$ be the set of $x\in X$ such that $|f(x)| \leq M$. Then
\begin{equation}\lim_{M \rightarrow \infty} \int_{X(M,f)} |f|d \mu =\int_X |f| d\mu <C~.\end{equation}
It follows that for a given $\epsilon>0$ there exists $M$ such that
\begin{equation}\label{Mbound}
\int_{X\backslash X(M,f)} |f| d\mu < \epsilon/2~,~\forall f \in S~.
\end{equation}
We can then choose $M$ larger, if necessary, so that  \eqref{Mbound} holds and $C/M < \epsilon/2$. Now, choose $\delta<\epsilon/2M$ and note that for any $f\in S$ and $A\in \Sigma$ with $\mu(A) <\delta$, we have:
\begin{eqnarray}
\int_A |f| d\mu &=&\int_{A \cap X(M,f)} |f| d\mu + \int_{A \backslash X(M,f)} |f| d\mu\\
& \leq& \mu(A)M+\epsilon/2 \leq \delta M +\epsilon/2 < \epsilon~.
\end{eqnarray}
\end{proof}

Theorem \ref{osegm} directly follows from the next theorem.

\begin{thm} \label{comos}
Let $(X, \Sigma, \mu)$ be a topological measure space, where $\mu$ is finite, nonatomic, and weakly outer regular. Let $f,g \in L^1(X,\Sigma, \mu)$ so that $\mu_f(X)=\mu_g(X)$. Then for any $D\in \Sigma$ with $\mu_f(D)=\mu_g(D)$, there exists a common O-segment $u:(\mu(D)/\mu(X),1] \rightarrow \Sigma$ for $\mu_f$ and $\mu_g$ such that
\begin{equation}\mu(D \backslash u(t))=0~,~\forall t>\mu(D)~.\end{equation}
\end{thm}

\begin{proof}
Without loss of generality, we assume that $\mu(X)=\mu_f(X)=\mu_g(X)=1$. We first prove the assertion when $g \equiv 1$. In the steps 1 and 2 below, $g \equiv 1$.
\\

\emph{Step 1.} In this step, we show that if $B\in \Sigma$ such that $\mu_f(B)=\mu_g(B)$, then for any $a\in (\mu_g(B),1)$ and $\epsilon>0$, there exists an open set $U$ such that $\mu(B \backslash U)=0$ and $\mu_f(U)=\mu_g(U) \in (a,a+\epsilon)$.

Choose $A\in \Sigma$ such that $B\subseteq A$ and $\mu_f(A)=\mu_g(A)=a$. This choice of $A$ is made possible by Theorem \ref{finite}. By Corollary \ref{oseg2}, there exists an increasing family of open sets $v(t)$, $t\in (a,1)$ such that $\mu_g(A \backslash u(t))=0$, $u(1)=X$ and $\mu_g(v(t))=t$. Define
\begin{equation}F(t)=\int_{v(t)} f d\mu -t~,~t\in (a,1]~.\end{equation}
We have $\lim_{t \rightarrow a}F(t)=F(1)=0$. If there exists $t\in (a,a+\epsilon)$ with $F(t)=0$, we are done. Otherwise, let $t_0\geq a+\epsilon$ be the smallest $t$ such that $F(t)=0$. It follows that $F$ is either strictly positive or strictly negative on the interval $(a,t_0)$. We assume $F(t)<0$ for all $t\in (a,t_0)$ (the other case is quite similar). Define $t_1 \in (a,t_0)$ and $s>0$ by setting
\begin{equation}-s=\min_{a<t<t_0} F(t)=F(t_1)~,~t_1 \in (a,t_0)~.\end{equation}
Also choose $t_2, t_3 \in (a,t_0)$ such that $t_3<t_2$, $F(t_2)=F(t_3)/2$, and $t_3+t_0-t_2<\epsilon/2$. Let $C=v(t_0) \backslash v(t_2)$. In particular, we have:
\begin{equation}\label{muc}
\int_C( f-g)d\mu=-F(t_2)>0~.
\end{equation}

Since $\mu$ is weakly outer regular, there exists an open set $W$ such that $\mu(C \backslash W)=0$ and $\mu (W \backslash C)< \delta$, where we have chosen $\delta \in (0, \epsilon/2)$ so small that
\begin{equation}\label{mug}
  \int_{W \backslash C} |f-g| d\mu < -F(t_2)/2~.
\end{equation}
Such a choice of $\delta$ is made possible by Lemma \ref{delta}. Next, we define a function
\begin{equation}\label{defg}
G(t)=\int_{v(t) \cup W} (f-g) d\mu~,~t\in [a,t_3]~.
\end{equation}
It follows from the equation \eqref{muc} and inequality \eqref{mug} that
\begin{equation}G(a)=\int_W (f-g) d\mu \geq  \int_C (f-g) d\mu  - \int_{W \backslash C} |f-g| d\mu  > -F(t_2)/2>0~.\end{equation}
On the other hand, by our choice of $t_2,t_3$, one has
\begin{eqnarray} \nonumber
G(t_3)&=&\int_{v(t_3) \cup W}(f-g) d\mu  \\ \nonumber
&\leq& F(t_3)+ \int_C (f-g)d \mu  + \int_{W \backslash C} |f-g| d\mu  \\
&\leq & 2F(t_2)-F(t_2)-F(t_2)/2 \leq F(t_2)/2<0~.
\end{eqnarray}

Since $G$ is continuous, there should exist $t\in (a,t_3)$ such that $G(t)=0$. But then $U=v(t)\cup W$ satisfies $\mu_f(U) =\mu_g(U)$ and $\mu_g(U)\leq t+\mu(W) \leq t_3+ \mu(C)+\delta \leq t_3+t_0-t_2+\delta <\epsilon$. Moreover, $\mu(B \backslash  U)\leq \mu(B \backslash v(t))=0$ as desired.
\\

\emph{Step 2.} In this step, we inductively construct a sequence of open sets $O_{m,n}$ and a sequence of real numbers $r_{m,n}\in [0,1]$, $0 < m \leq 2^n$, such that $\mu(D \backslash O_{m,n})=0$ and
\begin{eqnarray} \label{orel}
&&\mu_f(O_{m,n})=\mu_g (O_{m,n})=r_{m,n}~,\\ \label{or2}
&& O_{m,n} \subseteq O_{k,l},~\mbox{if}~{m \over {2^n}} \leq {k \over {2^l}}~,\\ \label{or3}
&& O_{m,n}=O_{k,l}~\mbox{if}~{m \over {2^n}} = {k \over {2^l}}~.
\end{eqnarray}
Here $r_{m,n}$ will be a sequence of nonnegative real numbers that is dense in $[\mu(D),1]$.
We set $O_{1,0}=X$, $r_{1,0}=1$, and $r_{0,n}=\mu(D)$ for all $n$. Suppose $O_{m,n}$ has been defined for all $m\leq 2^n$ satisfying the conditions \eqref{orel}-\eqref{or3}. Next, we define $O_{m,n+1}$ for all $m\leq 2^{n+1}$. Choose $k$ such that $2k \leq m \leq 2k+1$. If $m=2k$, we simply set $O_{m,n+1}=O_{k,n}$. If $m=2k+1$ and $k\neq 0$, then we use Step 1 to find an open set $O_{m,n+1}$ such that $O_{k,n} \subset O_{m,n+1} \subset O_{k+1,n}$ and
\begin{equation} \label{oineq}
\mu_f(O_{m,n+1})=\mu_g(O_{m,n+1})\in \left [{{r_{k+1,n}+r_{k,n}} \over 2}, {{r_{k+1,n}+r_{k,n}} \over 2}+{{r_{k+1,n}-r_{k,n}} \over {2^{2n}+1}} \right )~.\end{equation}
If $m=1$, then again by step 1, there exists an open set $O_{1,n+1} \subset O_{1,n}$ such that $\mu(D \backslash O_{1,n+1})=0$ and \eqref{oineq} holds. By this construction, it is clear that the set $r_{m,n}$ is dense in $[\mu(D),1]$.
\\

\emph{Step 3} Now, we define the common O-segment of $f$ and $g$ by setting
\begin{equation}u(t)= \bigcup_{r_{m,n} \leq t} O_{m,n}~.\end{equation}
Then $u(t)$ is defined for $t\in (\mu(D), 1]$, $\mu(D \backslash u(t))=0$, $\mu(u(t))=t$, and $u(t)$ is an increasing sequence of open sets in $X$.
\\

\emph{Step 4}. The steps 1-3 could have been applied to a general $g$ if we had an O-segment for $\mu_g$ at hand. The above three steps provide such an O-segment. And so one can repeat the same three steps to obtain an increasing family of open sets $u(t)$ such that $\mu_f(u(t))=\mu_g(u(t))$. By the construction of $O_{m,n}$ in step 2 and \eqref{oineq} in particular, we conclude that the function $\beta(t)=\mu_f(u(t))=\mu_g(u(t))$ is increasing. Then $w=u\circ \beta^{-1}$ is a common O-segment for $\mu_f$ and $\mu_g$.
\end{proof}

\bibliographystyle{amsplain}


TITLE: Why the need of Sobolev spaces in this proof of isoperimetric inequality?
QUESTION [0 upvotes]: I was reading the chapter about isoperimetric inequalities in DaCorogna's book "Introduction to The Calculus of Variations". The isoperimetric inequality is proved to be equivalent to Wirtinger Inequality. At page 154, he introduces Wirtinger inequality in this way:
Let
$$X=\{u \in W^{1,2} : u(-1)=u(1) \ \ \text{and} \ \ \int_{-1}^1 u(x) \, dx = 0\}$$.
Then
$$\int_{-1}^{1} u^{'\, 2} \, dx \geq \pi^2 \int_{-1}^{1} u^2 \, dx, \  \forall \, u \in X.$$
I'm new to Sobolev spaces and my question is: why, exactly, the need to introduce Sobolev space as the $X$ of choice?

REPLY [1 votes]: You don't need to introduce Sobolev spaces, but the point here is that $W^{1,2}$ is the completion of $C^\infty$ with the norm $\|f\|_{W^{1,2}}:=\|f\|_{L^2}+\|f'\|_{L^2}$. So if you prove the above inequality for all smooth $f$ with appropriate conditions, then by continuity of the integral you automatically have the result for all $f\in W^{1,2}$.


TITLE: Hoeffding's inequality for Hilbert space valued random elements
QUESTION [3 upvotes]: Suppose that $\mathbb H$ is a separable Hilbert space and $X_1,\ldots,X_n$ are independent zero mean $\mathbb H$-valued random elements such that $\|X_i\|\le s$ for each $1\le i\le n$, where $\|\cdot\|$ is the norm of $\mathbb H$. Denote $S_n=X_1+\ldots+X_n$.

Is it true that
  $$
P(\|S_n\|\ge t)\le Ce^{-c\frac{t^2}{ns^2}}
$$
  for $t>0$, where $C$ and $c$ are positive constants?

This reduces to Hoeffding's inequality if $\mathbb H=\mathbb R$. So basically what I am asking is if there exists a generalization of Hoeffding's inequality to Hilbert spaces. Unfortunately, I could not find a result of this sort.
Any help is much appreciated.

REPLY [4 votes]: This is a special case of more general Theorem 3.5, which holds for martingales in $2$-smooth Banach spaces. Note that (i) any Hilbert space is $2$-smooth, with the $2$-smoothness constant $D=1$ and (ii) the consecutive sums of independent zero-mean random vectors constitute a martingale.
The inequality you need can also be easily deduced from the earlier result: Theorem 3 specifically for sums of independent zero-mean random vectors in a Hilbert space.


TITLE: What is "Expected number of ..."?
QUESTION [1 upvotes]: I have worked on probability problems for a long time but I cannot understand what people means by writing "Expected number of ...". So what exactly does it means and, in general, how can we calculate it?

REPLY [1 votes]: Expectation in the discrete case is defined as:
$$E(X)=\lim_\limits{N\to\infty} \frac{\sum_{i=1}^N x_i}{N}$$
That is, if we run the experiment $N$ times, the limit of the sum of outcomes over the number of trials tends to the expected value of $X$.
In the case where number of possible values for $x_i$ is finite, say $n$, we can define expectation as:
$$E(X)=\sum\limits_{i=1}^n x_iP(X=x_i)$$
So for example with $2d6$, we get:
$$E(X)=\frac{2+3\cdot2+4\cdot3+5\cdot4+6\cdot5+7\cdot6+8\cdot5+9\cdot4+10\cdot3+11\cdot2+12}{36}$$
$$=\frac{2+6+12+20+30+42+40+36+30+22+12}{36}$$
$$=\frac{252}{36}$$
$$=7$$
which means that if we sum the throws of $N$ $2d6$, and divide by $N$, we expect the result to be around $7$.
Another example if to ask how many throws of a die do we expect to throw a six.
The probability that it takes $k$ throws to throw a six is:
$$P(X=k)=\left(\frac56\right)^{k-1}\frac16$$
So the answer is:
$$E(X)=\frac16\sum_\limits{i=1}^\infty i\left(\frac56\right)^{i-1}$$
This is calculated via:
$$\sum kx^{k-1} = \sum\frac{d}{dx} x^k = \frac{d}{dx} \sum x^k = \frac{d}{dx}\left(\frac1{1-x}\right)$$
and
$$\frac{d}{dx}\left(\frac{1}{1-x}\right)=\frac{1}{(1-x)^2}$$
giving $36$, and so we expect to have to throw a die $6$ times in order to throw a six.