text:
\begin{document}
\title{Incremental inference of collective graphical models}

\author{Rahul Singh, Isabel Haasler, Qinsheng Zhang, Johan Karlsson, and Yongxin Chen
\thanks{This work was supported by the Swedish Research Council (VR), grant 2014-5870, SJTU-KTH cooperation grant and the NSF under grant 1901599 and 1942523.
}
\thanks{R. Singh, Q. Zhang and Y. Chen are with the School of Aerospace Engineering,
Georgia Institute of Technology, Atlanta, GA, USA. {\tt\small \{qzhang419,rasingh,yongchen\}@gatech.edu}}
\thanks{I.~Haasler and J.~Karlsson are with the Division of Optimization and Systems Theory, Department of Mathematics, KTH Royal Institute of Technology, Stockholm, Sweden. {\tt\small haasler@kth.se, johan.karlsson@math.kth.se}}}

\maketitle
\thispagestyle{empty}
\begin{abstract}
We consider incremental inference problems from aggregate data for collective dynamics. In particular, we address the problem of estimating the aggregate marginals of a Markov chain from noisy aggregate observations in an incremental (online) fashion. We propose a sliding window Sinkhorn belief propagation (SW-SBP) algorithm that utilizes a sliding window filter of the most recent noisy aggregate observations along with encoded information from discarded observations. Our algorithm is built upon the recently proposed multi-marginal optimal transport based SBP algorithm that leverages standard belief propagation and Sinkhorn algorithm to solve inference problems from aggregate data. We demonstrate the performance of our algorithm on applications such as inferring population flow from aggregate observations.
\end{abstract}
\begin{IEEEkeywords}
Markov processes, filtering, stochastic systems
\end{IEEEkeywords}

\section{Introduction}\label{sec:intro}
\IEEEPARstart{T}{he} problem of inference from aggregate data is widely studied in fields including machine learning, ecology, and social sciences~\cite{SheDie11, SunSheKum15}.
Similar problems also occur in the area of estimation and control, for instance in ensemble filtering \cite{Eve03, LorNae11,CheKar18,HasRinChe19}.
In these applications, one aims to infer information about a group of agents in the case where only aggregate observations in the form of counts or contingency tables are provided~\cite{SheDie11}. Information about individuals may not be available due to, e.g., economical or privacy reasons \cite{SheDie11}.
For example, in bird migration analysis, individual trajectories are not readily accessible, but the number of birds in different areas can typically be counted from pictures. Another very present application is the spread of infectious diseases, where infections are usually under-reported, but inference of the true transmission dynamics is of utmost importance \cite{YanLipSha15}.

In control applications, individual dynamics are often estimated using for instance the Kalman filter \cite{Kal60}. In statistics, many methods are based on probabilistic graphical models (PGMs), e.g., the belief propagation algorithm \cite{Pea88}. However, neither approach is tractable when it comes to estimating the behavior of a large group of individuals simultaneously, let alone the fact that quite often only aggregate information is available. A number of methods have been developed to address this problem, for instance, the PGM framework has been extended to collective graphical models (CGMs), which is a formalism for inference and learning with aggregate data~\cite{SheDie11}. A CGM is a graphical model that describes the relationship between the aggregated counts of individuals. Several algorithms for aggregate marginal inference within the CGM framework have been proposed including Sinkhorn belief propagation (SBP)~\cite{SinHaaZha20}, approximate MAP inference~\cite{SheSunKumDie13} and non-linear belief propagation~\cite{SunSheKum15}. Whereas the latter two suffer from instability and lack convergence guarantees, the SBP algorithm is guaranteed to converge in case the underlying graphical model is acyclic.

The SBP algorithm is based on multi-marginal optimal transport theory, which studies the problem of finding the most efficient transport plan between several distributions~\cite{Pas15,BenCarCut15}. It has been shown that the aggregate inference problem is equivalent to the entropic regularized formulation of a multi-marginal optimal transport problem \cite{SinHaaZha20}. With this equivalence, the celebrated Sinkhorn algorithm~\cite{Cut13,BenCarCut15} has been utilized to solve the aggregate inference problem.

Most estimation tasks in the control community involve dynamic systems and thus evolution over time. This dynamic nature adds a temporal component to CGM. As time evolves, the number of aggregate noisy observations and the size of the underlying graphical model increase constantly. Clearly, naive CGM inference algorithms such as SBP are not suitable for real-time operations as the computational complexity increases linearly with the length of the graph.
Thus, to achieve real-time performance, we consider the problem of estimating the aggregate marginals of a Markov chain from noisy, aggregate observations in an incremental (online) fashion. In this problem, $M$ individuals behave independently according to the same underlying Markov chain for multiple time steps, and, at each time step, a noisy aggregate observation is made. As a new aggregate observation comes in at time step $t$, the goal is to estimate the aggregate marginal at time $t$. In case of an individual's model ($M=1$), this coincides with the traditional PGM, and naive incremental inference~\citet{Mur02} can be used by incorporating a sliding window filter to consider only a fixed number of most recent observations.

For collective dynamics, following the naive incremental approach, we build on the SBP algorithm and propose the sliding window Sinkhorn belief propagation (SW-SBP) algorithm for the incremental (online) aggregate inference problem. The SW-SBP algorithm employs a sliding window filter of length $K$, i.e., at each time step the $K$ most recent observations are used in order to estimate the current hidden aggregate distribution. In order to capture previous information, we propose to add one node at the beginning of the window, for which we consider two different settings. In one setting, the marginal distribution of this node is specified. In the other one, the node introduces some prior potential. We evaluate the performance of our algorithm on a variety of scenarios, including population flow analysis, validating the working of our algorithm.

The contribution of this work is twofold. On one hand, this is the first study of incremental inference in the CGM framework. Our method makes it possible to estimate the group behavior of a large collection of agents using aggregate observations in an online manner. On the other hand, this extends many incremental inference methods~\cite{Mur02,StaWhiBru17, WhiVu13} to the CGM setting. Indeed, when specialized to individual dynamics, our method reduces to a standard incremental inference algorithm.

\section{Background}\label{sec:background}

\subsection{Probabilistic Graphical Models and Belief Propagation}
\label{subsec:pgm}
Consider a distribution of $J$ random variables with the same finite image space $\mathcal{X}$, where $|\mathcal{X}| = d$, and with some dependencies between them. A probabilistic graphical model (PGM) is a compact and intuitive representation of such a distribution, which describes the dependencies by a graph \cite{WaiJor08}. More precisely, for a graph $G=(V,\,E)$, the random variables are represented by the set of vertices $V$, and the dependencies by the set of edges $E$.
The joint probability of the distribution of random variables can then be represented as
\begin{equation}\label{eq:individual}
p(\bx):= p(x_1,x_2,\ldots,x_J) = \frac{1}{Z} \prod_{(i,j) \in E} \psi_{ij}(x_i,x_j),
\end{equation}
where $\bx=\{x_1,\dots,x_J\}\in \mathcal{X}^J$, $\psi_{ij}\in\mathbb{R}$ are edge potentials, and $Z\in\mathbb{R}$ is a normalization constant. The edge potential $\psi_{ij}$ characterizes the strength of the dependency between the random variables at nodes $i$ and $j$. Sometimes one also defines node potentials $\phi_i(x_i)$, for $i\in V$. However, these can be absorbed in the edge potentials $\psi_{ij}$, and in this work we choose the compact notation \eqref{eq:individual}.

Often, one is interested in finding the distribution of one of the random variables, which is called the Bayesian marginal inference problem. An efficient method for this problem is the belief propagation algorithm, which updates the marginal distribution on the vertices, by sending messages (also called beliefs) between them \cite{Pea88}.
Let $N(i)$ denote the set of neighboring nodes of $i$. Then the message from variable node $i$ to variable node $j$ is
\begin{equation}\label{eq:BP}
m_{i \rightarrow j} (x_j) \propto \sum_{x_i} \psi_{ij}(x_i,x_j)
\prod_{k\in N(i)\backslash j} m_{k \rightarrow i}(x_i).
\end{equation}
This message can be understood as the belief of node $i$ about node $j$.
The messages in \eqref{eq:BP} are updated iteratively over the graph. When the algorithm converges, the node and edge marginals are given by
\begin{subequations}\label{eq:belief}
	\begin{eqnarray}
	b_i(x_i) &\propto&  \prod_{k \in N(i)} m_{k \rightarrow i} (x_i)
	\\
	\!\! \!\! \!\! \!\! \!\! \!\! \!\! b_{ij} (x_i,x_j)\!\!\!\!\! &\propto&\!\!\!\!\! \psi_{ij}(x_i,x_j)\!\!\!\!\!\! \prod_{k\in N(i) \backslash j}\!\!\!\!\!\! m_{k\rightarrow i} (x_i) \!\!\!\!\!\!\! \prod_{\ell\in N(j) \backslash i} \!\!\!\!\!\! m_{\ell \rightarrow j} (x_j\!).
	\end{eqnarray}
\end{subequations}

For an acyclic graph the belief propagation algorithm converges globally \cite{YedFreWei01} and the estimated marginal distributions in \eqref{eq:belief} recover the true marginals exactly. Although convergence is not guaranteed for general graphs with cycles, in practice the belief propagation algorithm often performs well~\cite{MurWeiJor99}.

\subsection{Collective Graphical Models} \label{subsec:cgm}
Collective graphical models (CGMs) describe the distribution of the aggregate data from several populations, which are each sampled independently from a discrete graphical model \cite{SheDie11}.
Consider a PGM as in Section~\ref{subsec:pgm} with underlying graph $G=(V,E)$.
Let $\bx^{(1)},...,\bx^{(M)}$ be $M$ samples of the PGM according to its joint probability distribution \eqref{eq:individual}. In particular, each sample is a tuple $\bx^{(m)}=(x_1^{(m)},\dots,x_J^{(m)})$, where $x_i^{(m)} \in \mathcal{X}$, for each $i=1,\dots,J$.

Let $X^{(m)}_i$ be the state of the $m^{th}$ individual at node $i$, and let $\mathbb{I}[.]$ denote the indicator function. Then the aggregate node distribution $\bn_i \in \mathbb{R}^d$ and aggregate edge distribution $\bn_{ij}\in \mathbb{R}^{d \times d}$ are element-wise given by
\begin{subequations}
\begin{align}
 n_i(x_i)=& \sum_{m=1}^M \mathbb{I}[X^{(m)}_i= x_i], \text{ for } i\in V,\\
    n_{ij}(x_i,x_j) =&  \sum_{m=1}^M \mathbb{I}[X_i^{(m)}= x_i, X_j^{(m)}= x_j], \text{ for } (i,j) \in E.
\end{align}
\end{subequations}
The collection of all the aggregate node and edge distributions is denoted as $\bn$, i.e., $\bn=\{\bn_i,\bn_{ij}| i\in V, (i,j)\in E\}$.
By construction all entries of $\bn$ are integers and they satisfy
\begin{equation}\label{eq:nconstraints}
\begin{aligned}
    \sum_{x_i}n_i(x_i) &= M,\qquad\qquad\quad ~\text{ for } i \in V, \\
    n_i(x_i) &= \sum_{x_j} n_{ij} (x_i,x_j), \ \ \text{for } (i,j)\in E.
    \end{aligned}
\end{equation}

From the underlying PGM $p(\bx)$, one can calculate the probability distribution of $\bn$, and this is known as the CGM. Similar to PGM, an important problem in CGM is to infer the marginal distributions given some measurements.
Multiple algorithms for aggregate marginal inference within the CGM framework have been proposed including the recent Sinkhorn belief propagation (SBP)~\cite{SinHaaZha20}, approximate MAP inference~\cite{SheSunKumDie13} and non-linear belief propagation (NLBP)~\cite{SunSheKum15}.
The approximate MAP inference and NLBP often suffer from instability and lack of convergence, while SBP exhibits convergence guarantees for acyclic graphs.

\subsection{Sinkhorn Belief Propagation} \label{subsec:sinkhorn_bp}

The Sinkhorn belief propagation algorithm~\cite{SinHaaZha20} is based on belief propagation and utilizes the celebrated Sinkhorn algorithm for multi-marginal optimal transport~\cite{Nen16,Pas12,BenCarCut15}, in order to solve the aggregate inference problem efficiently.

Let $G=(V,E)$ be a CGM, as in Section~\ref{subsec:cgm}, with joint aggregate distribution $\bn$. Moreover, let $\Gamma\subset\{1,\dots,J\}$ be a set of indices that represents all the nodes that are observed. That is, it holds $\bn_i= \by_i$ for a given set of observations $\by_i$, for $i\in\Gamma$ (see \cite{SinHaaZha20} for more discussion on this observation model).
In its variational form, the marginal inference problem for CGM with this observation model reads
\begin{equation}\label{eq:agg_form}
\begin{aligned}
     \underset{\bn}{\text{min}} && {\rm KL}(\bn~ ||~ \prod_{(i,j)\in E} \psi_{ij}(x_i,x_j))\\
     \text{s. t.}  && \bn_i = \by_i, \quad \forall i \in \Gamma.
\end{aligned}
\end{equation}

When the underlying graph is a tree, the objective function of problem~\eqref{eq:agg_form} is the same as the Bethe free energy~\cite{YedFreWei05}
\begin{equation}\label{eq:Bethe_energy_MOT}
\begin{aligned}
    F_{\rm Bethe}(\bn) =  \sum_{i,j} \sum_{x_i,x_j} n_{ij}(x_i,x_j) \ln \frac{n_{ij}(x_i,x_j)}{\psi_{ij}(x_i,x_j)} \\
    - \sum_{i=1} (d_i - 1) \sum_{x_i} n_i(x_i) \ln n_i(x_i),
    \end{aligned}
    \end{equation}
together with the consistency constraints \eqref{eq:nconstraints}. Here, $d_i$ denotes the degree of node $i\in V$.
Then the aggregate inference problem, with aggregate observations $\by_i$ for $i \in \Gamma$, reads
\begin{subequations}\label{eq:MOT_bethe}
\begin{eqnarray}
    \min_{\bn_{ij},\bn_i} &&F_{\rm Bethe}(\bn) \label{eq:MOT_bethe_a}
    \\
   \text{s.t.} && n_i(x_i) = y_i(x_i),~ \forall i \in \Gamma \label{eq:MOT_bethe_b} \\
   && \sum_{x_j} n_{ij}(x_i,x_j) = n_i(x_i), \forall (i,j) \in E \label{eq:MOT_bethe_c}  \\
   && \sum_{x_i} n_i(x_i)= 1, ~ \forall i \in V.\label{eq:MOT_bethe_d}
\end{eqnarray}
\end{subequations}
Note that here \eqref{eq:MOT_bethe_b} corresponds to the aggregate observation constraints and \eqref{eq:MOT_bethe_c}-\eqref{eq:MOT_bethe_d} to the  normalized consistency constraints \eqref{eq:nconstraints}. The solution to this problem is characterized by the following result.

\begin{thm}[{\cite[Theorem 1]{SinHaaZha20}} ] \label{thm:is_bp}
The solution to the aggregate inference problem~\eqref{eq:MOT_bethe} is characterized by
\begin{equation}
    {n}_i (x_i)  \propto  \prod_{k \in N(i)}  m_{k \rightarrow i}(x_i), ~\forall i\notin \Gamma
\end{equation}
where $m_{i \rightarrow j}(x_j)$ are fixed points of
\begin{subequations}\label{eq:is_bp_MOT}
\begin{eqnarray}
    m_{i\rightarrow j} (x_j)  &\propto&  \sum_{x_i} \psi_{ij}(x_i,x_j) \prod_{k\in N(i)\backslash j}  m_{k\rightarrow i}(x_i); \nonumber \\
    &&\forall i \notin \Gamma,~  \forall j \in N(i), \label{eq:is_bp_MOT1}  \\
    m_{i\rightarrow j} (x_j) &\propto&  \sum_{x_i} \psi_{ij}(x_i,x_j) \frac{y_i(x_i)}{m_{j \rightarrow i} (x_i)}; \nonumber \\
    && \forall i \in \Gamma,~  \forall j \in N(i).  \label{eq:is_bp_MOT2}
\end{eqnarray}
\end{subequations}
\end{thm}

Note that the inference problem \eqref{eq:agg_form} can be viewed as an entropy regularized multi-marginal optimal transport problem \cite{BenCarCut15,Nen16,SinHaaZha20}.
As a result, one can utilize the efficient Sinkhorn algorithm to solve the inference problem \eqref{eq:agg_form}. This can be accelerated further by merging it with belief propagation.
To summarize, by combining Sinkhorn for multi-marginal optimal transport problem and Theorem~\ref{thm:is_bp}, we establish Algorithm~\ref{alg:sbp}. We refer the reader to \cite{SinHaaZha20} for details of the derivation.
\begin{algorithm}[tb]
   \caption{Sinkhorn Belief Propagation (SBP)}
   \label{alg:sbp}
\begin{algorithmic}
   \STATE Initialize the messages $m_{i\rightarrow j} (x_j)$
   \STATE Update $m_{i\rightarrow j} (x_j)$ using \eqref{eq:is_bp_MOT}
   \WHILE{not converged}
   \FOR{$i \in \Gamma$}
        \STATE i) Update  $m_{i\rightarrow j} (x_j)$ using \eqref{eq:is_bp_MOT2}
        \STATE ii) Update all the messages on the path from $i$ to $i_{\rm next}$
        according to \eqref{eq:is_bp_MOT1}~(fix an order in $\Gamma$, $i_{\rm next}$ is the next element to $i$ in this order)
    \ENDFOR
    \ENDWHILE
\end{algorithmic}
\end{algorithm}

Note that in contrast to other algorithms for the aggregate inference problem, which rely on an explicit observation model~\cite{SunSheKum15}, SBP is guaranteed to converge when the underlying graph is a tree due to its foundations: Sinkhorn and belief propagation both converge \cite{YedFreWei01,KarRin17,BenCarCut15,ElvHaaJakKar20}.

The expressions in~\eqref{eq:is_bp_MOT} can be interpreted as messages between nodes, in analogy to the standard belief propagation method presented in Section~\ref{subsec:pgm}. In fact, the messages in \eqref{eq:is_bp_MOT} resemble the ones in \eqref{eq:BP}. The messages \eqref{eq:is_bp_MOT1} can be understood as a scaling step, which guarantees that the constraints \eqref{eq:MOT_bethe_b} remain satisfied.

\section{Main Results}\label{sec:main_result}
We consider \textit{incremental} marginal inference problems from aggregate data within the CGM framework. In particular, we address the problem of estimating the aggregate marginals of a hidden Markov chain from noisy aggregate observations in an incremental (online) fashion. We follow the model described in Section~\ref{subsec:sinkhorn_bp} as the generative model of aggregate data. A hidden Markov model (HMM) is a Markov chain where the state is not directly observable.
The joint distribution of an HMM factorizes as
\begin{equation} \label{eq:HMM_distribution}
    p(\bx, \bo) = p(x_1) \prod_{t=1} p(x_{t+1} \mid x_{t}) p(o_t \mid x_t),
\end{equation}
 where $\bx, \bo$ denotes state variable and observation respectively, $p(x_1)$ is the initial distribution of the starting state, $p(x_{t+1} \mid x_{t})$ are the transition probabilities between hidden (unobserved) variables, and $p(o_{t} \mid x_{t})$ are the observation probabilities for time steps $t=1,2,\ldots$. Note that the model given by \eqref{eq:HMM_distribution} is a directed graphical model but it can be equivalently converted to the undirected graphical model \eqref{eq:individual} by viewing the transition and observation probabilities as edge potentials $\psi_{ij}$ in \eqref{eq:individual}.

In this problem, $M$ individuals behave independently according to the same underlying hidden Markov chain for multiple time steps, and, at each time step, a noisy aggregate observation $\by_t$ is made in terms of the number of individuals in each observation node $o_t$. As a new observation is made at time step $t$, our goal is to estimate the corresponding aggregate marginal at time $t$. The number of aggregate noisy observations and the size of the underlying graphical model increases with time. To perform inference from this full data is not suitable for real-time operations as the computational complexity of inference increases greatly with the size of the graph. Therefore, incremental inference is of great importance in that it can efficiently estimate the required aggregate marginals from new observations without needing access to the previous observations.

Building on the SBP algorithm, we propose a sliding window Sinkhorn belief propagation (SW-SBP) algorithm for the incremental (online) aggregate inference problem. Borrowing the idea from traditional incremental HMM inference \cite{Mur02}, the SW-SBP algorithm employs a sliding window filter of length $K$ so that at time step $t$ ($t>K$), only the $K$ most recent observations are used in order to estimate the conditional probabilities. In addition to using only $K$ previous observations, we propose to add a node
\footnote{In case no extra node is added, the resulting algorithm is called naive SW-SBP.} to capture most of the information lost by discarding the previous observations. Denote this subgraph of the HMM model by $G_t = (V_t, E_t)$ as shown in Figure~\ref{fig:dynamic_markov}. Here, the incremental time starts at $t=K+1$. With this setting, we always have $2K + 1$ nodes (in $G_t$) at any time step $t$ from which the aggregate marginal is estimated.

\begin{figure}[t]
    \centering
    \includegraphics[scale = 0.5]{figures/Gt_new.pdf}
    \caption{Incremental HMM in SW-SBP.}
    \label{fig:dynamic_markov}
\end{figure}

The Bethe free energy \eqref{eq:Bethe_energy_MOT} for the subgraph/sliding window $G_t$ with the underlying HMM model \eqref{eq:HMM_distribution} is
{\small
\begin{equation}\label{eq:Bethe_energy_HMM}
\begin{aligned}
     &\sum_{i=t-K+1}^{t} \bigg( \sum_{x_{i-1},x_{i}} n_{i-1,i}(x_{i-1},x_{i}) \ln \frac{n_{i-1,i}(x_{i-1},x_{i})}{p(x_{i}| x_{i-1})} + \\
     & \sum_{x_i, o_i} n_{i,i}(o_i,x_i) \ln  \frac{n_{i,i}(o_{i},x_{i})}{p(o_{i}| x_{i})}  - 2 \sum_{x_i} n_i(x_i) \ln n_i(x_i) \bigg) + \\
     & \sum_{x_t} n_t(x_t) \ln n_t(x_t)
    \end{aligned}
\end{equation}}

We propose two methods for encoding information from the previous discarded observations in the node $\bn_{t-K}$. In the first method (SW-SBP-I) the node is constrained to be equal to the estimate of this node from the previous time step.
In the second method (SW-SBP-II) previous information is imposed by updating the potential $\phi_{t-K}$ on this node to the message $m_{t-K\to t-K+1}$ obtained at the previous time step.

\begin{figure}[t]
    \centering
    \begin{subfigure}[b]{0.19\textwidth}
        \centering
        \includegraphics[scale = 0.6]{figures/Gt_c_new.pdf}
        \caption{SW-SBP-I}
        \label{fig:Gt_constrained_potentialI}
    \end{subfigure} \hspace{0.1cm}
    \begin{subfigure}[b]{0.19\textwidth}
        \centering
        \includegraphics[scale = 0.6]{figures/Gt_p_new.pdf}
        \caption{SW-SBP-II}
        \label{fig:Gt_constrained_potentialII}
    \end{subfigure}
    \caption{Incremental HMM graph for the two methods.}
     \label{fig:Gt_constrained_potential}
\end{figure}

 Figure~\ref{fig:Gt_constrained_potential} shows the incremental HMM graphs corresponding to the two proposed schemes. The graph corresponding to SW-SBP-I at time step $t$ is $G_t^c = (V_t^c,E_t^c)$ as shown in Figure~\ref{fig:Gt_constrained_potentialI}. Here, the node $\bn_{t-K}$ is a fixed marginal node, which equals the estimated marginal on $G_{t-1}^c$. The index set of constraints $\Gamma_t^c$ is described by the set of shaded nodes in Figure~\ref{fig:Gt_constrained_potentialI}. At time step $t$, SW-SBP-I solves the inference problem \eqref{eq:MOT_bethe} with $\Gamma= \Gamma_t^c$ and Bethe free energy given as in \eqref{eq:Bethe_energy_HMM}. The steps of SW-SBP-I are listed in Algorithm~\ref{alg:isbp_marginal}, where $G^{\text{init}}$ is the initial graph with the first $K$ number of observations ($2K$ nodes) as in Figure~\ref{fig:dynamic_markov}.

\begin{algorithm}[h]
   \caption{SW-SBP-I (constrained marginal)}
   \label{alg:isbp_marginal}
\begin{algorithmic}
   \STATE Run SBP on initial graph $G^{\text{init}}$
   \FOR{$t = K+1,K+2,\ldots,$}
        \STATE Constrain marginal $\bn_{t-K}$ to be equal to its estimate obtained from $G_{t-1}^c$
        \STATE Run SBP on $G_t^c$
    \ENDFOR
\end{algorithmic}
\end{algorithm}

For the SW-SBP-II case, the incremental graph at time $t$ is represented by $G_t^p = (V_t^p, E_t^p)$ as in Figure~\ref{fig:Gt_constrained_potentialII}.
Here, the index set of constraints $\Gamma_t^p$ does not contain $t-K$. Instead, the potential $\phi_{t-K}$ (which will be absorbed into $p(x_{t-K+1}\mid x_{t-K})$ and is thus not explicit in \eqref{eq:Bethe_energy_HMM}) is updated to be
the message from $\bn_{t-K}$ to $\bn_{t-K+1}$ on the graph $G_{t-1}^p$.
Algorithm~\ref{alg:isbp_potential} lists the steps of SW-SBP-II.

\begin{algorithm}[h]
   \caption{SW-SBP-II (potential update)}
   \label{alg:isbp_potential}
\begin{algorithmic}
   \STATE Run SBP on initial graph $G^{\text{init}}$
   \FOR{$t = K+1,K+2,\ldots,$}
        \STATE Update node potential $\phi_{t-K}$ by message $m_{t-K \rightarrow t-K+1}$ obtained from $G_{t-1}^p$
        \STATE Run SBP on $G_t^p$
    \ENDFOR
\end{algorithmic}
\end{algorithm}

\begin{rem} \label{rem:KF}
The idea to replace the previous observations with a single node potential as in SW-SBP-II has been widely adopted in standard filtering settings. For instance, a Kalman filter \cite{Kal60} utilizes this idea to efficiently estimate the current state for linear dynamic systems.
\end{rem}

\begin{rem}
When applied to a single HMM trajectory, that is, when all the measurements $\by_i$ are Dirac distributions, the SBP algorithm reduces \cite{SinHaaZha20} to the standard inference algorithm: Forward-backward algorithm \cite{WaiJor08} in HMM literature. This is due to the fact that when $\by_i$ is Dirac, the belief $m_{i\rightarrow j}$ it outputs is independent of what it receives by \eqref{eq:is_bp_MOT2}. Consequently, SW-SBP-II reduces to a standard incremental inference algorithm in HMM which also employs a potential node to capture discarded information when all the observations $\by_i$ are Diracs.
\end{rem}

\section{Evaluation}\label{sec:eval}
We evaluate the performance of SW-SBP on multiple experiments including a toy example and a mobility pattern estimation problem.
We compare the performance of different SW-SBP algorithms in terms of the estimation error with the baseline algorithm, which is SBP (Algorithm \ref{alg:sbp}) on the whole graph without discarding previous measurements.

\begin{figure}[t]
    \centering
    \begin{subfigure}[b]{0.47\textwidth}
        \centering
            \includegraphics[width=1.0\textwidth]{figures/cdc_figure3_window_3.png}
            \caption{$K=3$.}
    \end{subfigure}
    \begin{subfigure}[b]{0.47\textwidth}
        \centering
            \includegraphics[width=1.0\textwidth]{figures/cdc_figure3_window_5.png}
            \caption{$K=5$.}
    \end{subfigure}
    \begin{subfigure}[b]{0.47\textwidth}
        \centering
            \includegraphics[width=1.0\textwidth]{figures/cdc_figure3_window_10.png}
            \caption{$K=10$.}
    \end{subfigure}
    \caption{Performance with $d =50$ for different window lengths $K$. The right column shows the $\ell_1$-norm error with respect to the baseline marginals and the left column shows the time consumption for the algorithms to converge. The solid lines denote the average over 10 trials and the shaded area represents the corresponding standard deviation.}
    \label{fig:comparison}
\end{figure}

\begin{figure}[t]
    \centering
    \begin{subfigure}[b]{0.21\textwidth}
        \centering
        \includegraphics[width=1.0\textwidth]{figures/cdc_figure4_d20.png}
        \caption{$d = 20$}
    \end{subfigure}
    \begin{subfigure}[b]{0.21\textwidth}
        \centering
        \includegraphics[width=1.0\textwidth]{figures/cdc_figure4_d50.png}
        \caption{$d = 50$}
    \end{subfigure}
    \caption{Performance for different values of $d$ with fixed window length of $K=5$.}
    \label{fig:change_d}
\end{figure}

\subsection{Performance Comparison}
\label{subsec:toy}

To evaluate the performance of the proposed algorithms, we simulate a time-varying HMM with randomly chosen observations and evaluate the performance for different filter lengths $K$ and different values of state dimension $d$. The observation is of the same dimension as the state. The transition and observation matrices are both generated randomly using $500\mathcal{I} + 10\exp({E})$ where $\mathcal{I}$ denotes the identity matrix and $E$ is a random matrix generated from a standard Gaussian distribution.
Figure~\ref{fig:comparison} compares the performance of proposed methods for varying sliding window length. The results are averaged over 10 different trials. It is evident that the time consumption of the baseline method increases rapidly with the size of the graph. Moreover, the convergence behaviors of Naive-SW-SBP, SW-SBP-I, and SW-SBP-II are similar. In terms of estimation errors, SW-SBP-I and SW-SBP-II outperform Naive-SW-SBP by a significant margin. Moreover, SW-SBP-II shows better error performance as compared to SW-SBP-I and as the length of the filter increases, the errors decrease.
Figure~\ref{fig:change_d} depicts the error performance for different values of $d$ with fixed window length of $K=5$. It is observed from the figure that SW-SBP-I and SW-SBP-II perform similar for small values of $d$, outperforming Naive-SW-SBP algorithm, and SW-SBP-II performs better for large values of $d$.
Note that the idea to update the potential in SW-SBP-II is inspired by the Kalman filter (see Remark~\ref{rem:KF}). In standard inference of HMMs, which is a special case of our framework where $\by_i$ is a Dirac distribution for all $i$, the strategy in SW-SBP-II gives precise solutions, that is, SW-SBP-II is a precise incremental implementation of SBP. However, in cases where the measurements $\by_i$ are general distributions, SW-SBP-II only approximates SBP. Currently there is no rigorous justification why SW-SBP-II outperforms SW-SBP-I in our general setting.

\begin{figure}[t]
    \centering
    \includegraphics[trim={0 9 0 8},clip,scale = 0.32]{figures/sensor.png}
    \caption{Location of $16$ sensors in a $15 \times 15$ grid.}
    \label{fig:sensor_locations}
\end{figure}

\begin{figure*}[t]
    \centering

     \begin{minipage}[c]{0.67\textwidth}
    \includegraphics[trim={50 0 60 5}, clip, width=\textwidth]{figures/6col_new.pdf}
     \end{minipage}
     \begin{minipage}[c]{0.32\textwidth}
    \caption{Simulation of movement of $M = 10000$ agents over $15 \times 15$ grid with $K = 3$. The first column depicts the real movement of agents at different time steps, second column represents the aggregate sensor observations, third column depicts estimated aggregated positions using the baseline full graph. Fourth, fifth, and sixth columns represent the estimated positions obtained by different variants of SW-SBP. The size of the circles is proportional to the number of agents.}
    \label{fig:human_mobility}
    \end{minipage} \vspace{-10pt}
\end{figure*}

\begin{figure}[t]
    \centering
    \begin{subfigure}[b]{0.42\textwidth}
        \centering
        \includegraphics[width=1.0\textwidth]{figures/wifi_length5_d10.png}

    \end{subfigure}
    \caption{Error comparison for bird migration experiment. The left and right figure show the error with respect to the ground truth and with respect to the baseline estimate, respectively.}
    \label{fig:human_mobility_error}
\end{figure}

\subsection{Bird Migration}
\label{subsec:human_mobility}
Next, we consider the problem of estimating a mobility pattern of birds in a geographical area from noisy aggregate counts. Following the environment considered in \citet{SunSheKum15}, we simulate $M$ individuals moving in an $L \times L$ grid, aiming to reach the top-right of the grid following a Markov chain. The transition probabilities of this Markov chain follow a log-linear distribution that accounts for four factors:  the distance between two positions, the angle between movement direction and the top-right direction, the angle between wind direction and the direction to goal (top-right in the grid), and preference to stay in the original cell. The weight for those four factors in the log-linear model is $(5,3,1.6,1)$. The observations are made as the counts of individuals connected to the randomly distributed sensors in the grid (see Figure~\ref{fig:sensor_locations}). These sensors constitute a distributed sensor network in which each sensor can only detect the present of birds nearby while is not able to output their locations.
We assume that each individual is connected to exactly one of the sensors and the probability of the connection decreases exponentially as the distance between agent and the sensor increases.

At time $t=0$, the population is concentrated at the two clusters: one at the left-bottom and one at the center-bottom.

We simulate the Markov chain for $M=10000$ individuals independently and perform incremental inference using SW-SBP algorithms. We compare the performance of the algorithms in terms of the $\ell_1$-norm of the difference between the estimated marginals and the baseline marginals. Figure~\ref{fig:human_mobility_error} shows the errors for the algorithm for $30$ time steps on a $15 \times 15$ grid with $16$ randomly distributed sensors. It can be observed from the figure that SW-SBP-II performs significantly better than SW-SBP-I and Naive-SW-SBP. Moreover, the errors for all the three methods decrease as the length of the sliding window filter increases. Figure~\ref{fig:human_mobility} shows the true and estimated movements of the the population using different methods. As can be seen, SW-SBP-II infers the population movements closest to the baseline.

\section{Conclusion}
\label{sec:conclusion}

In this paper, we proposed an algorithm for incremental inference from aggregate data in a Markov chain by employing a sliding window filter. The performance of proposed methods were demonstrated on multiple scenarios including estimation of bird mobility patterns. The present work focus on discrete setting and its extension to continuous state system is a future direction.

\bibliography{icml_mot}
\bibliographystyle{IEEEtran}

\end{document}


TITLE: Limit in two variables of $\frac{\sin(\sqrt[3]x y)}{xy}$
QUESTION [1 upvotes]: I have to evaluate this limit
$$\lim_{|(x,y)| \to \infty} \frac{\sin(\sqrt[3]x y)}{xy}$$
I think it's useful to consider the module and the inequality $|\sin t| \leq |t|$ for all $t\in\mathbb{R}$ to prove that the limit is $0$, my approach is
$$0\leq \lim_{|(x,y)| \to \infty} \left|\frac{\sin(\sqrt[3]x y)}{xy}\right|\leq \lim_{|(x,y)| \to \infty} \left|\frac{\sqrt[3]x y}{xy}\right|= \lim_{x \to +\infty} \left|\frac{1}{x^{\frac{2}{3}}}\right|=0$$
So the limit is $0$. Is this correct?
If it is correct, I have some more doubts:
(1) In this step: $$\lim_{|(x,y)| \to \infty} \left|\frac{\sqrt[3]x y}{xy}\right|=\lim_{x \to +\infty} \left|\frac{1}{x^{\frac{2}{3}}}\right|$$
The limit becomes a one variable limits just because the function has lost its depencence by $y$?
(2) If my thought on (1) is right, the one variable limit is such that $x\to+\infty$ because $|(x,y)| \to \infty \Leftrightarrow x\to+\infty \ \text{and}\ y\to+\infty$ so, eliminated the depencence of $y$, $x$ has necessarily to tend to $+\infty$?
(3) Why is $|\sin t| \leq |t|$ for all $t\in\mathbb{R}$ valid for $\sin(\sqrt[3]x y)$ even if we are in $\mathbb{R}^2$?
Thanks for your time and excuse by bad english.

REPLY [2 votes]: (1) It is true that if a function doesn't depend on a variable, then sending that variable to anything that doesn't affect the function. You can prove this similarly to how you would prove that $\lim_{x \to a} 1 = 1$.
However, the expression you've actually written is wrong, and your conceptual error lies in (2). $\|(x,y)\| \to \infty$ does not imply that $|x| \to \infty$. For example, take the sequence $(1/n, n)$ as $n \to \infty$to $\infty$ .
In fact, the limit in the question doesn't exist. Consider the path $\{ (x(u), y(u)) = (u^{-3}, u): u\in [1, \infty) \}$. Clearly as $u \to \infty,$ $\|(x(u), y(u))\| \to \infty$. But on this path the function is $$ f(u^{-3},u) = \frac{\sin (1)}{u^{-2}} = u^2 \sin(1),$$ which trivially blows up. Thus, along this path $f$ doesn't have a limit, ergo, the limit doesn't exist. [Note that the limit is not even $+\infty$ - go along the path $(4^3 u^{-3}, u)$ ]
To reiterate, ${x\to \infty, y \to \infty}$ is not the same as ${ \|(x,y)\| \to \infty}.$ If instead we were studying $\lim_{x\to \infty, y \to \infty} f(x,y)$, then your approach would be correct, and yield the limit $0$ (althuogh I would use $|\sin(t)| \le 1$ instead of $\le |t|$, since this is stronger for large $t$.)
For (3), this works because $\sin$ always acts on a single variable. You're defining $t(x,y) = x^{1/3}y,$ which is a map from $\mathbb{R}^2$ to $\mathbb{R}$. Then for this real number $t$, $|\sin(t)| \le |t|$. Then you can go back and substitute the value of $t$ in terms of $x,y$.


TITLE: Has martian sunset same spectra than this earthly bluish-violet sunset?
QUESTION [3 upvotes]: Has martian sunset same spectra than this earthly bluish-violet sunset?
What about sunset on Mercury?

REPLY [3 votes]: The composition of Martian atmosphere is quite different from the one on Mother Earth (see Mars-GRAM model developed by C.G.Justus from MSFC at Huntsville, Ala. for details). On this planet, colors at sunset (and the unforgettable green ray) are dependent on water content. On Mars, it is the amount of dust in the air and related scattering that changes the colors from one season to another. To see for yourself, please visit JPL's multimedia page with raw images from the Curiosity rover.

NASA rover Spirit on the rim of Gusev crater on May 19, 2005
Credit: NASA/JPL/Texas A&M/Cornell
A video with a Martian sunset seen from NASA rover Opportunity.
This said, for the same spectrum each camera has its own sensitivity curve, and cannot (broadly speaking) replace a human observer. Even corrected colors are not quite the same as the real stuff. For reference: different color sets in Gale Crater.

Curiosity on August 23, 2012
Credit: NASA/JPL-Caltech/MSSS
On Mercury, you will have to wait long to see the sunset, and will be disappointed by the colors due to lack of perceptible atmosphere. This assumes that your thermal control can cope with being continuously grilled by the Sun during the "day" and frozen at "night", and that your UV protection is strong enough to prevent rapid onset of cancer. Would say, these are rather pressing issues that significantly impair your ability to conduct observations.


TITLE: Problem with proof that positive infinite series are commuative
QUESTION [0 upvotes]: Proof from real analysis book:
Let  $\sum_{n=0}^{\infty}a_n$ converge, where  $a_n \geq 0, n \in \mathbb{N}$.
Then the series
$$
\sum_{k=1}^{\infty}a'_k = a'_1 + a'_2 + \cdots + a'_k + \cdots
$$
Is constructed by rearranging the elements of the original series
$$
a'_1 = a_{n_1}, \ a'_2 = a_{n_2}, \ \ldots, \ a'_k = a_{n_k}, \ \ldots
$$
where $(n_1,n_2,\ldots,n_k,\ldots)$ is a permutation of the set $\mathbb{N}$.
We must now prove that $\sum_{k=1}^{\infty}a'_k$ converges and has the same sum as the original series.
Let $s_n = \sum_{k=0}^{n}a_k$, $s'_k = \sum_{i=1}^{k}a'_i$ and $\lim_{n \to \infty}s_n = s $.
If for some $k\in\mathbb{N}$
$$
max\{n_1,n_2,\ldots,n_k\} = n_0
$$
then $s'_k \leq s_{n_0}$, it follows that $s'_k \leq s$ for all $k\in \mathbb{N}$. So the sequence $(s'_k)_{k\in\mathbb{N}}$ is bounded and increasing so it converges, $\lim_{k \to \infty}s'_k = s' $. It follows that $s' \leq s$.
The following part of the proof where the author proves that $s' \geq s$ confuses me:
Because the series $\sum_{n=0}^{\infty}a_n$ can be constructed from the series $\sum_{k=1}^{\infty}a'_k$ by rearranging it's elements, it follows that $s' \geq s$.
If we can use this kind of "rearrangement argument" couldn't we use it both ways? i.e. Because $\sum_{k=1}^{\infty}a'_k$ is constructed by rearranging elements of $\sum_{n=0}^{\infty}a_n$ it follows that $s'_k \leq s$.
If this argument could be used it would lead to a false conclusion that conditionally convergent series are also commutative.

REPLY [2 votes]: The argument is symmetric in the $a_k$ series and the $a_k'$ series. The point is that both of these series are series of positive elements, and either can be seen as the other with their elements rearranged.
This does not say anything about conditionally convergent series, since a series of positive numbers can never be conditionally convergent (as convergence is the same thing as absolute convergence here, since the absolute value of a positive number is positive).


TITLE: Definition of the total variation of a function $g:\mathbb{R}\to\mathbb{R}$
QUESTION [0 upvotes]: if the total variation of a a real function $f:[a,b]\to \mathbb{R}$ over $\textbf{P}=\{a=t_0<t_1<...<t_m=b\}$ is
$$
 V^{a}_{b}(f)=\sup_{\textbf{P}}V(f,\textbf{P})
$$
 where
$$
V(f,\textbf{P})=\sum^{m}_{i=1}|f(t_i)-f(t_{i-1})|
$$
then what is the total variation of a function $g:\mathbb{R}\to\mathbb{R}$? I didn't find a definition of this case.

REPLY [1 votes]: Do the same thing you do with integrals:  Take the (independent) limits as $a \rightarrow -\infty$ and $b \rightarrow \infty$.


TITLE: Simple model of car-following as a linear system of ODE
QUESTION [0 upvotes]: I have the following simple model of car-following without delay:
$\ddot{x}_k(t)=\lambda[\dot{x}_{k-1}(t)-\dot{x}_k(t)],k=1,2,...,n. \quad\qquad(1)$
Where $\ddot{x}_k$ is the acceleration of the follower, $\dot{x}_{k-1}(t)-\dot{x}_k(t)$ is the relative velocity between the leading car and the follower car  and $\lambda$ is the sensitivity.
How can I express the equation $(1)$ as the next linear system of ODE
$\dot{\mathbf{x}}(t)=A\mathbf{x}(t)+B\mathbf{\alpha}(t).$
Where $A$ is a matrix of $n\times n$ and $B$ is a matrix of $n\times m$.

REPLY [0 votes]: You get $\mathbf {\dot x}=A\mathbf x+\mathbf b$ where $A=λ(-I+S)$ with $S$ is the sub-diagonal matrix with entries $1$ on the first sub-diagonal. And $\mathbf b=λx_0(t)\mathbf e_1$.
Set $n=4$, write out the equations, especially the first one, and transcribe into matrix form to confirm that pattern.


TITLE: The group $G$ is a partition of equivalence classes
QUESTION [2 upvotes]: I am looking at the proof of the Lagrange Theorem:

Let $G$ a finite group and $H$ a subgroup of G. Then $|H| \mid |G|$.

If $g \in G$, then $|gH|=|H|$.
If $g_1, g_2 \in G$ we consider $g_1H$ and $g_2H$.
To continue we show that $$g_1H \cap g_2H=\varnothing \text{ or } g_1H=g_2H$$ as followed:
At the set $G$ we define a relation $\sim$ like that: $$g_1 \sim g_2 \Leftrightarrow g_2^{-1} g_1 \in H$$ Then we show that this relation $\sim$ is an equivalence relation.
So $G$ is a partition of equivalence classes.
(partition=union of disjoint subsets)
$$$$
Could explain me why when we know that there is an equivalence relation then the group $G$ is a partition of equivalence classes?

REPLY [3 votes]: Suppose the intersection of $g_{1}H$ and $g_{2}H$ is non-empty. Then there are $h_{1}$ and $h_{2}$ s.t. $g_{1}h_{1}=g_{2}h_{2}$.
If $x\in g_{1}H$, then
$x=g_{1}h=g_{2}h_{2}h_{1}^{-1}h\in g_{2}H$.
Thus $g_{1}H$ is a subset of $g_{2}H$.
If $x\in g_{2}H$, then
$x=g_{2}h=g_{1}h_{1}h_{2}^{-1}h\in g_{1}H$.
Thus $g_{2}H$ is a subset of $g_{1}H$.
Hence
$g_{1}H=g_{2}H$
Let $g\in G$. Then
$g=ge\in gH$
This proves that the left cosets of H in G are disjoint and that G is the union of these cosets.
Together with a proof of  $|gH|=|H|$ you are more or less done.


TITLE: The union of a strictly increasing sequence of $\sigma$-algebras is not a $\sigma$-algebra
QUESTION [28 upvotes]: The union of a sequence of $\sigma$-algebras need not be a $\sigma$-algebra, but how do I prove the stronger statement below?

Let $\mathcal{F}_n$ be a sequence of
  $\sigma$-algebras. If the inclusion
  $\mathcal{F}_n \subsetneqq \mathcal{F}_{n+1} $ is strict, then
  the union
  $\bigcup_{n=1}^{\infty}\mathcal{F}_n$
  is not a $\sigma$-algebra.

REPLY [18 votes]: I want to do three things:

give a counterexample to Jonas' lemma that there is necessarily a sequence of pairwise disjoint sets $F_n\in\mathcal{F}_{n+1}\setminus\mathcal{F}_n\;$,
show that there is however a sequence of pairwise disjoint sets $G_{k}\in\mathcal{F}_{n_k+1}\setminus\mathcal{F}_{n_k}$ for some strictly increasing sequence $n_k$ (so Jonas' proof still works), and
offer an alternative proof of the main statement, which also uses this modified lemma.

As a counterexample to the unmodified lemma, consider $\mathcal{F}_1=\{\emptyset,[0,6]\}$ and
$\mathcal{F}_2$, $\mathcal{F}_3$ and $\mathcal{F}_4$ the $\sigma$-algebras generated by adding $[0,3]$, $[1,2]$ and $[4,5]$ respectively, to their predecessors. (To extend this to a strictly increasing sequence of $\sigma$-algebras, we can keep adding arbitrary intervals with new boundaries, e.g. $[2^{-n}/2,2^{-n}]$). If we choose $[0,3]$ as $F_1$, there are no new sets in $\mathcal{F}_3$ that are disjoint from it, and if we choose its complement instead, the same is true for $\mathcal{F}_4$.
So the best we can hope for is a sequence of pairwise disjoint sets $G_k\in\mathcal{F}_{n_k+1}\setminus\mathcal{F}_{n_k}$ for some strictly increasing sequence $n_k$: Then we can form a new sequence of strictly increasing $\sigma$-algebras, $\mathcal{G}_k:=\mathcal{F}_{n_k}$, and then $G_k\in\mathcal{F}_{n_k+1}\setminus\mathcal{F}_{n_k}\subseteq\mathcal{G}_{k+1}\setminus\mathcal{G}_k$ will be a disjoint sequence as desired, and we can prove the claim for $\mathcal{G}=\bigcup G_k=\mathcal{F}$ without loss of generality. Thus, Jonas' proof will remain substantially intact. So let's show that there is such a sequence.
It's not clear (to me) from the question whether the $\mathcal{F}_n$ all have the same underlying set, so I'll first show that we can assume that they do without loss of generality. Each $\mathcal{F}_n$ contains its underlying set as an element, so the union $U$ of all these underlying sets is a countable union of elements of $\mathcal{F}$, and hence in $\mathcal{F}$, and hence in some $\mathcal{F}_{n_0}$. So all $\mathcal{F}_n$ after that have the same underlying set $U$, and without loss of generality we can drop the initial ones that don't.
Since the $\mathcal{F}_n$ are strictly increasing, we can choose some (not necessarily pairwise disjoint) sequence of sets $F_n\in\mathcal{F}_{n+1}\setminus\mathcal{F}_n$. (We need the axiom of countable choice to do that, but I suspect it would be difficult to impossible to prove any of this without some form of choice, so I won't worry about that in the following.)
Let's say $F_n$ is distinctive in $A\in\mathcal{F}_n$ if $F_n\cap A\notin\mathcal{F}_n$. This also implies $\overline{F_n}\cap A\notin\mathcal{F}_n$, since $\overline{\overline{F_n}\cap A}\cap A=(F_n\cup\overline{A})\cap A=F_n\cap A$. Also, if $F_n$ is distinctive in $A$ and $B\in\mathcal{F}_n$, then $F_n$ is distinctive in $A\cap B$ or in $A\cap \overline{B}$, for otherwise $F_n\cap A\cap B\in\mathcal{F_n}$ and $F_n\cap A\cap\overline{B}\in\mathcal{F_n}$ and thus $(F_n\cap A\cap B)\cup(F_n\cap A\cap\overline{B})=(F_n\cap A)\cap(B\cup\overline{B})=F_n\cap A\in\mathcal{F}_n$. (Since we're working within a single underlying set $U$, the complements are well-defined.)
Now let $n_0=0$ and $V_0=U$ and, by induction, construct a strictly increasing sequence $n_k$ together with sets $V_k$ and $G_k$ such that $V_k,G_k\in\mathcal{F}_{n_m+1}\setminus\mathcal{F}_{n_m}$ and $V_k,G_k\subseteq V_{k-1}$ for all $k\in\mathbb{N}$, that $G_k$ is disjoint from $G_j$ for all $k>j$, that $V_k$ is disjoint from $G_j$ for all $k\ge j$, and that for all $k$ infinitely many $F_n$ are distinctive in $V_k$.
There are no disjointness conditions to fulfill for $k=0$, so we merely have to note that infinitely many (namely all) of the $F_n$ are distinctive in $V_0=U$ (since $F_n\cap U=F_n\notin\mathcal{F}_n$) to get the induction off the ground. Then, assuming that $V_k$ and $G_k$ have the above properties for all $k<m$, take $n_m$ to be the first integer greater than $n_{m-1}$ such that $F_{n_m}$ is distinctive in $V_{m-1}$. This integer exists since infinitely many $F_n$ are distinctive in $V_{m-1}$. Consider $F_{n_m}$ and $\overline{F_{n_m}}$, which is also in $\mathcal{F}_{n_m+1}\setminus\mathcal{F}_{n_m}$. Every $F_j$ with $j>n_m$ that is distinctive in $V_{m-1}$ is distinctive in at least one of $V_{m-1}\cap F_{n_m}$ and $V_{m-1}\cap\overline{F_{n_m}}$. Since there are infinitely many such $F_j$, we can choose $V_m$ to be one of $V_{m-1}\cap F_{n_m}$ and $V_{m-1}\cap\overline{F_{n_m}}$ such that infinitely many $F_j$ are distinctive in $V_m$. Take $G_m$ to be the other of $V_{m-1}\cap F_{n_m}$ and $V_{m-1}\cap\overline{F_{n_m}}$. Since $V_{m-1}$, $F_{n_m}$ and $\overline{F_{n_m}}$ are all in $\mathcal{F}_{n_m+1}$, so are $V_m$ and $G_m$, and since $F_{n_m}$ is distinctive in $V_{m-1}$, neither $V_m$ nor $G_m$ is in $\mathcal{F}_{n_m}$. Thus $V_m,G_m\in\mathcal{F}_{n_m+1}\setminus\mathcal{F}_{n_m}$ as required. Also, since $V_{m-1}$ is disjoint from all $G_j$ with $j\le m-1$, i.e. $j<m$, so are $V_m$ and $G_m$, and $V_m$ is also disjoint from $G_m$, and hence from all $G_j$ with $j\le m$. That completes the induction, and thus the proof of the modified lemma, since the $G_k$ and $n_k$ for $k\in\mathbb{N}$ have the desired properties.
Now for the proof that I originally had in mind before I got sidetracked by the disjointness issue :-) It's similar in spirit to Jonas' proof in that it makes use of the fact that in cramming the uncountably many combinations of the $G_k$ into the countable sequence of the $\mathcal{G_k}$, one must invariably get ahead of oneself and generate some $G_k$ that wasn't supposed to be there yet.
Since the $G_k$ are disjoint, all their (finite and countably infinite) unions are distinct, and thus in one-to-one correspondence with (finite and countably infinite) binary strings, where a $1$ digit means that the corresponding $G_k$ is included in the union and a $0$ digit means that it isn't. All these unions must be in $\mathcal{G}$ if it is to be a $\sigma$-algebra. In particular, $G:=\bigcup G_k$ must be in $\mathcal{G}$, and thus in some $\mathcal{G}_{k_0}$. Without loss of generality, we can drop the $G_k$ with $k<k_0$ and assume that $G$ is in $G_1$, so that we can always form complements $\overline{G_k}\cap G$ in $G$, which corresponds to inverting all the digits in the corresponding string.
Now let's first try to derive a contradiction by trying to construct one of the $G_k$ in $\mathcal{G}_k$. To do this, we start with $G$ and first remove all $G_j$ for $j<k$ (which we can, since they are all in $\mathcal{G}_k$). Now assume that for each $j>k$ there is one of the above unions in $G_k$ such that its $j$-th digit differs from its $k$-th digit. If the $k$-th digit is $1$, we take the set itself, if it is $0$, we take its complement in $G$, thus inverting its digits. Then in either case the $k$-th digit is $1$ and the $j$-th digit is $0$ (since they differ by assumption). Now we can remove all $G_j$ for $j>k$ by intersecting with all these sets, leaving only $G_k$ and thus yielding the desired contradiction $G_k\in\mathcal{G}_k$. Thus, contrary to our assumption, there must be some $j>k$ such that the $j$-th and $k$-th digits coincide for all unions in $\mathcal{G}_k$, and this must be the case for all $k$.
This we can use to derive another contradiction, using a diagonal argument and forming a binary string as follows: Starting with $n_1=1$, in each step we choose $n_{i+1}>n_i$ such that the $n_{i+1}$-th and $n_i$-th digits coincide for all unions in $\mathcal{G}_{n_i}$, and we choose the $n_{i+1}$-th digit of the binary string being constructed such that it differs from the $n_i$-th digit. (The remaining digits can be chosen arbitrarily.) Then the union corresponding to this string is in none of the $\mathcal{G}_{n_i}$, and thus in none of the $\mathcal{G}_k$, and thus not in $\mathcal{G}$. This contradiction completes the proof.
Now one question remains: Either of the proofs (if we add the part about a pairwise disjoint sequence to Jonas' proof) is unlikely to be what whoever assigned the homework had in mind -- so is there a simpler proof?


text:
\begin{document}

\title{On the universality of the Carter and McLenaghan formula}

\author{Ion I. Cot\u aescu \\
{\it West University of Timi\c soara,}\\{\it V.
Parvan Ave. 4, RO-300223 Timi\c soara}}

\begin{abstract}
It is shown that the formula of the isometry generators of the spinor
representation given by Carter and McLenaghan is universal in the sense that
this holds for any representation either in local frames or even in natural
ones. The point-dependent spin matrices in natural frames are introduced for
any tensor representation deriving the covariant form of the isometry
generators in these frames.

Pacs: 04.20.Cv, 04.62.+v, 11.30.-j
\end{abstract}

\maketitle

\section{Introduction}

In general relativity there are many symmetries but only the isometries
(associated to Killing vectors) are able to produce conserved quantities via
Noether theorem. The physical fields minimally coupled to gravity take over
this symmetry transforming according to appropriate representations of the
isometry group. In the case of the scalar vector or tensor fields these
representations are completely defined by the well-known rules of the general
coordinate transformations since the isometries are in fact particular
automorphisms. On the other hand, the theory of spinor fields is formulated in
orthogonal local frames where the basis-generators of the spinor representation
were discovered by Carter and McLenaghan \cite{CML}

Some time ago we proposed a theory of external symmetry in the context of the
gauge covariant theories based on local orthogonal frames. We introduced there
new transformations which combine isometries and gauge transformations such
that the tetrad fields should remain invariant \cite{ES}. In this way we
obtained the external symmetry group which is nothing else that the universal
covering group of the isometry one. Moreover, we derived the general form of
the basis-generators of the representations of this group shoving that these
are given by a similar formula to that of Carter and McLenaghan.

In the present letter we should like to show that this formula holds even in
natural frames. To this end we define the spin matrices of the vector and
tensor representations in natural frames which are point-dependent and give
rise to the spin terms of the covariant form of our basis-generators. The
conclusion is that the Carter and McLenaghan formula is universal.

We start in the second section with a short introduction  to the tetrad gauge
covariant theories in which we defined our theory of external symmetry briefly
presented in the next section. The spin matrices in natural frames are
introduced in section three where the basis-generators of the vector and tensor
representations of the external symmetry group are obtained.

\section{Tetrad gauge covariance}

Let us consider the curved spacetime $M$ and a local chart (natural frame) of
coordinates $x^{\mu}$ (labeled by natural indices, $\mu, \nu,...=0,1,2,3$).
Given a gauge, we denote by $e_{\hat\mu}$ the tetrad fields that define the
local frames and by $\hat e^{\hat\mu}$ those of the corresponding coframes.
These have the usual orthonormalization properties, $\hat
e^{\hat\mu}_{\alpha}\, e_{\hat\nu}^{\alpha}=\delta^{\hat\mu}_{\hat\nu}$, $ \hat
e^{\hat\mu}_{\alpha}\, e_{\hat\mu}^{\beta}=\delta^{\beta}_{\alpha}$,
$e_{\hat\mu}\cdot e_{\hat\nu}=\eta_{\hat\mu \hat\nu}$, $\hat e^{\hat\mu}\cdot
\hat e^{\hat\nu}=\eta^{\hat\mu \hat\nu}$. The metric tensor $g_{\mu
\nu}=\eta_{\hat\alpha\hat\beta}\hat e^{\hat\alpha}_{\mu}\hat
e^{\hat\beta}_{\nu}$ raises or lowers the natural indices while for the local
indices ($\hat\mu, \hat\nu,...=0,1,2,3$) we have to use the Minkowski metric
$\eta=$diag$(1,-1,-1,-1)$. This metric remains invariant under the
transformations of its  gauge group, $O(3,1)$. This has as subgroup the Lorentz
group, $L_{+}^{\uparrow}$, of the transformations $\Lambda[A(\omega)]$
corresponding to the transformations $A(\omega)\in SL(2,\Bbb C)$ through the
canonical homomorphism. In the standard covariant parametrization, with the
real parameters $\omega^{\hat\alpha \hat\beta}=-\omega^{\hat\beta\hat\alpha}$,
the $SL(2,\Bbb C)$ transformation read
\begin{equation}\label{Aomega}
A(\omega)= e^{-\frac{i}{2}\omega^{\hat\alpha\hat\beta}
S_{\hat\alpha\hat\beta}}
\end{equation}
where $S_{\hat\alpha \hat\beta}$ are the covariant basis-generators of the
$sl(2,\Bbb C)$ Lie algebra. In fact, these are the principal spin operators
which generate the spin terms of other operators in the quantum theory. For
small values of $\omega^{\hat\alpha\hat\beta}$ the matrix elements of the
transformations $\Lambda$ in the local basis can be expanded as
$\Lambda^{\hat\mu\,\cdot}_{\cdot\,\hat\nu}[A(\omega)]=
\delta^{\hat\mu}_{\hat\nu} +\omega^{\hat\mu\,\cdot}_{\cdot\,\hat\nu}+\cdots$.

Assuming now that $M$ is orientable and time-orientable we can consider
$G(\eta)=L^{\uparrow}_{+}$  as the gauge group of the Minkowski metric $\eta$
\cite{WALD}. Then, the  fields with spin in local frames transform according to
finite-dimensional  linear representations, $\rho$, of the group $SL(2,\Bbb
C)$. In general, a matter field $\psi_{\rho}:M\to {\cal V}_{\rho}$ is defined
over $M$ with values in the vector space ${\cal V}_{\rho}$ of the
representation $\rho$ which is generally reducible. The covariant derivatives
of the field $\psi_{\rho}$,
\begin{equation}\label{der}
D_{\hat\alpha}^{\rho}= e_{\hat\alpha}^{\mu}D_{\mu}^{\rho}=
\hat\partial_{\hat\alpha}+\frac{i}{2}\, \rho(S^{\hat\beta\, \cdot} _{\cdot\,
\hat\gamma})\,\hat\Gamma^{\hat\gamma}_{\hat\alpha \hat\beta}\,,
\end{equation}
depend on the  connection coefficients in local frames,
$\hat\Gamma^{\hat\sigma}_{\hat\mu \hat\nu}=e_{\hat\mu}^{\alpha}
e_{\hat\nu}^{\beta}(\hat e_{\gamma}^{\hat\sigma} \Gamma^{\gamma}_{\alpha \beta}
-\hat e^{\hat\sigma}_{\beta, \alpha})$, which assure the covariance of the
whole theory under tetrad gauge transformations. This is the general framework
of the theories involving fields with half integer spin which the natural
frames are not dealing with.

\section{External symmetries in local frames}

A special difficulty in local frames is that the theory is no longer covariant
under isometries since these can change the tetrad fields that carry natural
indices. For this reason we proposed a theory of external symmetry in which
each isometry transformation is coupled to a gauge one able to correct the
position of the local frames such that the whole transformation should preserve
not only the metric but the tetrad gauge too \cite{ES}. Thus, for any isometry
transformation $x\to x'=\phi_{\xi}(x)=x+\xi^a k_a+...$, depending on the
parameters $\xi^a$ ($a,b,...=1,2...N$) of the isometry group $I(M)$, one must
perform the gauge transformation $A_{\xi}$ defined as
\begin{equation}\label{Axx}
\Lambda^{\hat\alpha\,\cdot}_{\cdot\,\hat\beta}[A_{\xi}(x)]=
\hat e_{\mu}^{\hat\alpha}[\phi_{\xi}(x)]\frac{\partial \phi^{\mu}_{\xi}(x)}
{\partial x^{\nu}}\,e^{\nu}_{\hat\beta}(x)
\end{equation}
with the supplementary condition $A_{\xi=0}(x)=1\in SL(2,\Bbb C)$.  Then the
transformation laws of our fields are
\begin{equation}\label{es}
(A_{\xi},\phi_{\xi}):\qquad
\begin{array}{rlrcl}
e(x)&\to&e'(x')&=&e[\phi_{\xi}(x)]\\
\hat e(x)&\to&\hat e'(x')&=&\hat e[\phi_{\xi}(x)]\\
\psi_{\rho}(x)&\to&\psi_{\rho}'(x')&=&\rho[A_{\xi}(x)]\psi_{\rho}(x)\,.
\end{array}
\qquad
\end{equation}
We have shown that the pairs $(A_{\xi},\phi_{\xi})$ constitute a well-defined
Lie group we called the external symmetry group, $S(M)$, pointing out that this
is just the universal covering group of $I(M)$ \cite{ES}. For small values of
$\xi^{a}$, the $SL(2,\Bbb C)$ parameters of $A_{\xi}(x)\equiv
A[\omega_{\xi}(x)]$ can be expanded as $\omega^{\hat\alpha\hat\beta}_{\xi}(x)=
\xi^{a}\Omega^{\hat\alpha\hat\beta}_{a}(x)+\cdots$, in terms of the functions
\begin{equation}\label{Om}
\Omega^{\hat\alpha\hat\beta}_{a}\equiv {\frac{\partial
\omega^{\hat\alpha\hat\beta}_{\xi}} {\partial\xi^a}}_{|\xi=0} =\left( \hat
e^{\hat\alpha}_{\mu}\,k_{a,\nu}^{\mu} +\hat e^{\hat\alpha}_{\nu,\mu}
k_{a}^{\mu}\right)e^{\nu}_{\hat\lambda}\eta^{\hat\lambda\hat\beta}
\end{equation}
which depend on the Killing vectors $k_a=\partial_{\xi_a}\phi_{\xi}|_{\xi=0}$
associated to $\xi^a$.

The last of Eqs. (\ref{es})  defines the operator-valued representation
$(A_{\xi},\phi_{\xi})\to T_{\xi}^{\rho}$ of the group $S(M)$ whose
transformations,
$(T_{\xi}^{\rho}\psi_{\rho})[\phi_{\xi}(x)]=\rho[A_{\xi}(x)]\psi_{\rho}(x)$,
leave the field equation invariant. Their basis-generators \cite{ES},
\begin{equation}\label{Sx}
X_{a}^{\rho}=i{\partial_{\xi^a} T_{\xi}^{\rho}}_{|\xi=0}=-i
k_a^{\mu}\partial_{\mu} +\frac{1}{2}\,\Omega^{\hat\alpha\hat\beta}_{a}
\rho(S_{\hat\alpha\hat\beta})\,,
\end{equation}
commute with the operator of the field equation and satisfy the commutation
rules $[X_{a}^{\rho}, X_{b}^{\rho}]=ic_{abc}X_{c}^{\rho}$ determined by the
structure constants, $c_{abc}$, of the $s(M)\sim i(M)$ algebras.  Eq.
(\ref{Sx}) can be put in covariant the form
\begin{equation}\label{CM}
X^{\rho}_{a}=-ik^{\mu}_{a}D_{\mu}^{\rho}+\frac{1}{2}\, k_{a\,
\mu;\,\nu}\,e^{\mu}_{\hat\alpha}\,e^{\nu}_{\hat\beta}\,
\rho(S^{\hat\alpha\hat\beta})\,,
\end{equation}
which represents a generalization to any representation $\rho$ of the famous
formula given by Carter and McLenaghan  for the spinor representation
$\rho_{spin}=(\frac{1}{2},0)\oplus (0,\frac{1}{2})$ \cite{CML}.

\section{Isometries in natural frames}

Whenever the spinors are absent, the matter fields are vectors or tensors of
different ranks  and the whole theory is independent on the tetrad fields
dealing with the natural frames only. Let us see what happens with our theory
of external symmetry in natural frames focussing on tensor fields. Any tensor
field, $\Theta$, transforms under isometries as $\Theta\to \Theta'
=T_{\xi}\Theta$, according to a  tensor representation of the group $S(M)$
defined by the well-known rule in natural frames
\begin{equation}
\left[\frac{\partial \phi^{\alpha}_{\xi}(x)}{\partial x_{\mu}}\frac{\partial
\phi^{\beta}_{\xi}(x)}{\partial x_{\nu}}...
\right]\left(T_{\xi}\Theta\right)_{\alpha\beta...}[\phi(x)]=\Theta_{\mu\nu...}(x)\,.
\end{equation}
Hereby one derives the basis-generators of the tensor representation,
$X_{a}=i\,\partial_{\xi_a}T_{\xi}|_{\xi=0}$, whose action reads
\begin{equation}\label{XT}
(X_a\,
\Theta)_{\alpha\beta...}=-i({k_a}^{\nu}\Theta_{\alpha\beta...;\,\nu}
+{k_a}^{\nu}_{~;\,\alpha}\Theta_{\nu\beta...}
+{k_a}^{\nu}_{~;\,\beta}\Theta_{\alpha\nu ...}...)\,.
\end{equation}
Our purpose is to show that the operators $X_a$  can be written in a form which
is equivalent to  Eq. (\ref{CM}) of Carter and McLanaghan.

We start with the vector representation $\rho_v=(\frac{1}{2},\frac{1}{2})$ of
the $SL(2, \Bbb C)$ group, generated by the spin matrices
$\rho_v(S^{\hat\alpha\hat\beta})$ which have the well-known matrix elements
\begin{equation}
[\rho_v(S^{\hat\alpha\hat\beta})]^{\hat\mu\,\cdot}_{\cdot\,\hat\nu}
=i(\eta^{\hat\alpha\hat\mu}\delta^{\hat\beta}_{\hat\nu}-
\eta^{\hat\beta\hat\mu}\delta^{\hat\alpha}_{\hat\nu})\,,
\end{equation}
in local bases. Furthermore, we define the point-dependent spin matrices in
natural frames whose matrix elements in the natural basis read
\begin{equation}\label{spin1}
(\tilde S^{\mu\nu})^{\sigma\,\cdot}_{\cdot\,\tau}
=e^{\mu}_{\hat\alpha}e^{\nu}_{\hat\beta}e^{\sigma}_{\hat\gamma} [\rho_v(
S^{\hat\alpha\hat\beta})]^{\hat\gamma\,\cdot}_{\cdot\,\hat\delta} \hat
e^{\hat\delta}_{\tau}=
i(g^{\mu\sigma}\delta^{\nu}_{\tau}-g^{\nu\sigma}\delta^{\mu}_{\tau})\,.
\end{equation}
In what follows we assume that these matrices represent the spin operators of
the vector representation in natural frames. We observe that these are the
basis-generators of the groups $G[g(x)]\sim G(\eta)$ which leave the metric
tensor $g(x)$ invariant in each point $x$. Since the representations  of these
groups  are point-wise equivalent with those of $G(\eta)$, one can show that in
each point $x$ the basis-generators $\tilde S^{\mu\nu}(x)$ satisfy the standard
commutation rules of the vector representation $\rho_v$ (but with $g(x)$
instead of $\eta$).

In general, the spin matrices of a tensor $\Theta$ of any rank, $n$, are the
basis-generators of the representation
$\rho_n=\rho_v^1\otimes\rho_v^2\otimes\rho_v^3\otimes....\otimes\rho_v^n$ which
read $\rho_n(\tilde S)=\tilde S^1\otimes I^2\otimes I^3... +I^1\otimes \tilde
S^2\otimes I^3...+....$. Using these spin matrices a straightforward
calculation shows that  Eq. (\ref{CM}) can be rewritten in natural frames as
\begin{equation}\label{Xvt}
X^{n}_{a}=-ik^{\mu}_{a}\nabla_{\mu}+\frac{1}{2}\, k_{a\, \mu;\,\nu}\,
\rho_n(\tilde S^{\mu\nu})\,,
\end{equation}
where $\nabla_{\mu}$ are the usual covariant derivatives. It is not difficult
to verify that the action of these operators is just that given by Eq.
(\ref{XT}) which means that $X_a^{n}$ are the basis-generators of a tensor
representation of rank $n$ of the group $S(M)$. Thus, it is clear that Eq.
(\ref{Xvt}) represents the generalization to natural frames of the Carter and
McLenaghan formula (\ref{CM}).

\section{Concluding remarks}

The principal conclusion here is that the Carter and McLenaghan formula is
universal since it holds not only in local frames but in natural frames too. In
local frames this formula can be written in the covariant form (\ref{CM}) or as
in Eq. (\ref{Sx}) where the orbital part (i.e. the first term) is completely
separated from the spin term (the second one). It is worth pointing out that
Eq. (\ref{Sx}) can not be rewritten in natural frames even though it might be
useful for analyzing the operators structure in the relativistic quantum
mechanics. This is because the connection in local frames can not be expressed
in terms of spin matrices $\tilde S$. Therefore, in natural frames we are
forced to use only the genuine Carter and McLenaghan formula (\ref{Xvt}).

This formula exhibits explicitly the point-dependent spin matrices of the
vector or tensor representations which may provide us with information about
the spin content of the various fields involved in theory. However, some
results could be surprising. Thus, for example, if a second order rank tensor
has the form $G_{\mu\nu}=g_{\mu\nu}F$ where $F$ is a scalar field then we
calculate $\rho_2(\tilde S^{\alpha\beta})G=0$ which indicates that the tensor
$G$ is spinless despite of the fact that it is of second rank. Consequently,
the metric tensor is also spinless as it seems to be natural since this is
covariantly  constant and invariant under isometries (such that $X^2_a\, g=0$).
Another example is presented in Ref. \cite{CCM} where we define the photon
polarization in de Sitter manifolds without to consider local frames.

Finally we note that, despite of our partial results, the problem of the spin
in general relativity remains open as long as we do not have an effective
theory similar to the Wigner theory of the induced representations of the
Poincar\' e group.

\subsection*{Acknowledgments}

We are grateful to Cosmin Crucean and Nistor Nicolaevici for interesting and
useful discussions on closely related subjects.

config: arxiv


text:
\section{First Cyclotomic Polynomial}
Tags: Examples of Cyclotomic Polynomials

\begin{theorem}
The '''first [[Definition:Cyclotomic Polynomial|cyclotomic polynomial]]''' is:
:$\map {\Phi_1} x = x - 1$
\end{theorem}

\begin{proof}
By definition:
:$\displaystyle \map {\Phi_1} x = \prod_\zeta \paren {x - \zeta}$
where the product runs over all [[Definition:Primitive Complex Root of Unity|primitive complex first roots of unity]].
A [[Definition:Root of Unity|root of unity]] has order $1$ {{iff}} it equals $1$.
{{explain|The above statement needs justification, with reference to the definition of the order of a root of unity.}}
Hence the only factor is $x - 1$.
{{MissingLinks|Factor of Polynomial -- for which we appear not to have a page.}}
[[Category:Examples of Cyclotomic Polynomials]]
czxoo4jr9iujpwf7gtp0n8wu4kr6pct
\end{proof}

config: wiki


text:
\begin{document}

\preprint{AJC-HEP-25}
\title{
Evaluation~of vacuum energy density~around geometrical defects~by the
WKB method}
\author{Kiyoshi~Shiraishi

}
\address{Akita Junior College\\
Shimokitade-sakura, Akita-shi, Akita 010, Japan
}

\begin{abstract}
The energy density of a conformally invariant scalar field
around a cosmic string is estimated by the WKB method.
This approach reproduces the precise value obtained
 by the other authors using the exact mode-sum method or
the method of mirror images.
The approximation is also in good agreement with the exact result
in the three-dimensional case.
We also evaluate the energy density
of a conformally invariant scalar field around a global
monopole by the same way find the known result again.
\end{abstract}
\vspace{7mm}
\pacs{PACS number(s): 03.70.+k, 04.60.+n, 98.80.Cq}

\maketitle

\section{Introduction}
The vacuum energy of free fields on the conical space created by the presence of
an idealized cosmic string \cite{V} can be computed by the several
 ways \cite{qfcs}.
The metric describing an infinitely long straight cosmic string laid
along the $z$ axis is given by \cite{V}
\be
ds^{2}=-dt^{2}+dz^{2}+dr^{2}+b^{2}r^{2}d\phi^{2},
\label{eq:met}
\ee
where $b$ is a parameter that characterizes the cosmic string.
Using this, the deficit angle is expressed as $2\pi(1-b)$
and the mass density of the string is $(1-b)/(4G)$.
For a conformally invariant scalar field, the vacuum expectation value
of the energy density at one-loop level
in the spacetime described by the metric (\ref{eq:met})
has been found to be \cite{qfcs}
\be
\rho_{vac} = -\frac{1}{1440\pi^{2}r^{4}}\left(\frac{1}{b^{4}}-1\right)\ .
\ee

In this paper, we evaluate the quantum vacuum energy of a conformally
invariant scalar field using the WKB method.
The derivation is simple and pedagogical:
Moreover, this yields considerably accurate values in many cases.
 As a quantum field,
 we consider only a conformally invariant scalar field in this paper.

The organization of this paper is as follows.
In Sec.~\ref{sec:cs} we study the WKB estimation of vacuum energy density
of a conformally invariant scalar field around a straight cosmic string.
The result is compared with the known one obtained by other methods.
 The technique is generalized to the cases of general spacetime
 dimensions in Sec.~\ref{sec:cone}\@.
 In Sec.~\ref{sec:gm},
we treat vacuum energy around a global monopole.
Sec,~\ref{sec:sum} is devoted to summary of the results.

\section{WKB evaluation of vacuum energy around a cosmic string}
\label{sec:cs}
The vacuum energy at one-loop level arises from the zero-point energy
 of quantum fields \cite{cas}.
Formally, it is written by
\be
E_{0}=\frac{1}{2}\sum_{\lambda}\omega_{\lambda}\ ,
\label{1}
\ee
where $\omega$ is the frequency of each normal mode
in the expansion of the field.
The subscript $\lambda$ characterizes each normal mode.
The formal expression (\ref{1}) diverges due to
unlimitedly high frequency modes.
Therefore, to get a meaningful conclusion for the vacuum energy
$E_{vac}$, we must regularize $E_{0}$
and subtract proper energy of standard,
which is usually defined for a flat Minkowsky space.

We start with the expression (\ref{1}) to obtain
vacuum energy density in the spacetime described
by the metric (\ref{eq:met})
representing the presence of a cosmic string.
We demonstrate evaluation of the vacuum energy
that comes from a conformally invariant scalar field
governed by the Lagrangian
\be
{\cal L}=\frac{1}{2}\nabla^{\mu}\varphi\nabla_{\mu}\varphi
+\frac{1}{2}\xi R \varphi^2,
\label{eq:lag}
\ee
where $R$ is the scalar curvature and
$\xi=1/6$ in the four-dimensional spacetime.

If the expression (\ref{1}) is calculated naively,
it is found to be divergent not only
because of the unlimitedly high frequency modes
but also because of the singularity of the space for the present case.
On the dimensional ground, the energy density should be proportional to
 $1/r^{4}$.
Other length or mass scales are absent in
the conformally invariant theory, at least in one-loop calculations.
Thus our aim can be said to be determination of the coefficient of $1/r^4$ in the
expression of the vacuum energy density.

The equation of motion for the scalar field is derived from
 (\ref{eq:lag}) as
\be
(\Box - {\xi} R)\varphi=0\ .
\label{eq:emo}
\ee
Now we define the following mode function:
\be
\varphi=e^{-i\omega t}e^{ikz}e^{i\ell \phi}\chi_{\omega k \ell}(r)\ ,
\label{eq:mode}
\ee
where $\ell=0, \pm 1, \pm 2,\ldots$.
Substituting the metric (\ref{eq:met}) and the
mode function (\ref{eq:mode}) into the wave equation (\ref{eq:emo}),
we get a differential equation for the radial function
 $\chi_{\omega k\ell}(r)$,
\be
\frac{1}{r}\frac{\partial}{\partial r}r\frac{\partial}{\partial r}
\chi_{\omega k\ell}(r)+
\left(\omega^{2}-k^{2}-\frac{\ell^{2}}{b^{2}r^{2}}\right)
\chi_{\omega k\ell}(r)=0\ .
\ee

To simplify the equation, we use the new coordinate $y$ defined by
\be
y=\ln{r/r_{0}}\ ,
\ee
where $r_{0}$ is an arbitrary constant.
Then the differential equation concerning the radial function becomes
\be
\frac{d^{2}\chi_{\omega k\ell}(y)}{dy^{2}}
+W(y;\omega,k,\ell)\chi_{\omega k\ell}(y)=0\ ,
\ee
where
\be
W(y;\omega,k,\ell)\equiv
(\omega^{2}-k^{2})r_{0}^{2}e^{2y}-\frac{\ell^{2}}{b^{2}}\ .
\ee

The solution according to the WKB approximation is given by
\be
\chi_{\omega k\ell}(y)\approx\frac{1}{\sqrt[4]{W(y;\omega,k,\ell)}}
\sin \int^{y}\sqrt{W(y;\omega,k,\ell)}\ dy\ .
\ee

Suppose that the ``wall'' is located at $r=L$,
which is an infrared cutoff in some sense.
On the other hand, near the conical singularity, we set a small cutoff
at $r=\delta$.
We assume the boundary conditions
$\chi_{\omega k\ell}=0$ at $r=\delta$ and $r=L$.
In this situation, a quantum number $n$ is associated with the radial
wave function as
\bea
n\pi&=&\int^{\ln L/r_{0}}_{\ln \delta/r_{0}}
\sqrt{W(y;\omega,k,\ell)}\ dy\nn
&=&\int^{L}_{\delta}\sqrt{\omega^{2}-k^{2}
-\frac{\ell^{2}}{b^{2}r^{2}}}\ dr\ .
\eea
Therefore the total number $g(\omega)$ of wave modes per unit length
along the cosmic string
with the frequency~$< \omega$ is written by
\be
g(\omega)=\int\frac{dk}{2\pi}
\sum^{}_{\ell}n(\omega,k,\ell)\ ,
\ee
where the sum over $\ell$ and integration over $k$ is taken just for real positive values of
the integrand.

We now get the vacuum energy per unit length along the cosmic string,
\bea
E_{0}&=&\frac{1}{2}\int dg(\omega)\ \omega \nn
&=&-\frac{1}{2}\int d\omega\ g(\omega) \nn
&=&-\frac{1}{2\pi}\int d\omega \int\frac{dk}{2\pi}
\sum^{}_{\ell}
 \int^{L}_{\delta}\sqrt{\omega^{2}-k^{2}
 -\frac{\ell^{2}}{b^{2}r^{2}}}\ dr\ .
\eea
Changing the order of integration, we have
\be
E_{0}=\int^{L}_{\delta}\ \rho_{0}(b)\ 2\pi
b\,rdr\ ,
\label{eq:ene}
\ee
with
\be
\rho_{0}(b)\equiv
-\frac{1}{4{\pi}^{2}br}\int d\omega \int\frac{dk}{2\pi}
\sum^{}_{\ell}
\sqrt{\omega^{2}-k^{2}-\frac{\ell^{2}}{b^{2}r^{2}}}\ .
\ee
The integration over $r$ in (\ref{eq:ene}) diverges
in the limit $\delta\rightarrow 0$,
since ``vacuum energy density'' $\rho_{0}(b)$ should be
proportional to
 $1/r^{4}$. Accordingly, we have only to manage
 the ultraviolet divergence
 in the formal expression of $\rho_{0}(b)$.

We again change the order of integration and perform the integration
over $\omega$ first. We treat the divergent integration by
 analytical continuation. That is, the square root in the expression
 of $\rho_{0}(b)$ is regarded as the $(\frac{1}{2}-\epsilon)$th power.
The outcome of the integration is
\be
\rho_{0}(b)=-\frac{\mu^{2\epsilon}}{4\pi^{2}br}\int \frac{dk}{2\pi}
\sum^{\infty}_{\ell=-\infty}\frac{1}{\sqrt{4\pi}}
\Gamma\left(\frac{3}{2}-\epsilon\right)
\Gamma\left(-1+\epsilon\right)
\left(k^{2}+\frac{\ell^{2}}{b^{2}r^{2}}\right)^{1-\epsilon}\ ,
\ee
where the constant $\mu$ has the dimension of mass.

Next, we perform the integration over $k$. Then we get
\be
\rho_{0}(b)=-\frac{\mu^{2\epsilon}}{4\pi^{2}br}
\sum^{\infty}_{\ell=-\infty}\frac{1}{4\pi}
\Gamma\left(\frac{3}{2}-\epsilon\right)
\Gamma\left(-\frac{3}{2}+\epsilon \right)
\left(\frac{\ell^{2}}{b^{2}r^{2}}\right)^{\frac{3}{2}-\epsilon}.
\label{eq:unsum}
\ee
Discarding the term for $\ell=0$, we can rewrite the above as
\be
\rho_{0}(b)=-\frac{(\mu br)^{2\epsilon}}{8\pi^{3}(br)^{4}}
\Gamma\left(\frac{3}{2}-\epsilon\right)
\Gamma\left(-\frac{3}{2}+\epsilon \right)
\zeta\left(-3+2\epsilon\right)\ ,
\ee
where $\zeta(z)$ is the Riemann's zeta function.

Taking the limit $\epsilon\rightarrow 0$ in the context of analytic continuation,
we find the following finite quantity:
\bea
\rho_{0}(b)&=&-\frac{1}{8\pi^{3}(br)^{4}}
\Gamma\left(\frac{3}{2}\right)
\Gamma\left(-\frac{3}{2}\right)
\zeta\left(-3\right)\nn
&=&-\frac{1}{1440\pi^{2}(br)^{4}}\ ,
\eea
where the numerical values are substituted (see, for example,
\cite{AS}.).

Finally, the finite vacuum energy density is obtained by subtraction as
\bea
\rho_{vac}&=&\rho_{0}(b)-\rho_{0}(1)\nn
&=&-\frac{1}{1440\pi^{2}r^{4}}\left(\frac{1}{b^{4}}-1\right).
\eea
This result coincides with the known result obtained
by exact mode summation or mirror-image method \cite{qfcs}.

We can also consider a ``twisted'' scalar field \cite{twist}, which has a
special  periodicity in $\phi$:
$\varphi(t,z,r,\phi)=-\varphi(t,z,r,\phi+2\pi)$.
For the twiwted field, the vacuum energy can be obtained by replacing
$\ell\rightarrow \ell+1/2$.
Thus the vacuum energy density before subtraction is derived as
\be
\rho_{0}^{T}(b)=-\frac{7}{8}\rho_{0}(b)\ .
\ee
Then the finite vacuum energy density is given by
\bea
\rho_{vac}^{T}&=&\rho_{0}^{T}(b)-\rho_{0}(1)\nn
&=&\frac{7b^{-4}+8}{11520\pi^{2}r^{4}}\ ,
\eea
which also turns out to be the exact expression \cite{qfcs}.

In the next section, the procedure of evaluation of vacuum energy
 is generalized to an arbitrary dimensional case.

\section{Vacuum energy for a conical defect in general dimensions}
\label{sec:cone}
In this section, we consider a conical singularity
 in general dimensions.
The $(d+3)$-dimensional metric is written by
\be
ds^{2}=-dt^{2}+(dx^{1})^{2}+\cdots +(dx^{d})^{2}
+dr^{2}+b^{2}r^{2}d\phi^{2}.
\label{eq:metg}
\ee
The Lagrangian for a conformal scalar field is the same as (\ref{eq:lag}),
except for $\xi=(d+1)/[4(d+2)]$.

The evaluation of vacuum energy density of a conformal scalar field
in this spacetime is done by a similar way that we showed
in the preceding section.
In our methods, the unregularized energy density per unit $d$-volume can be expressed as
\be
\rho_{0}(b)=-\frac{\mu^{2\epsilon}}{4\pi^{2}br}\int \frac{d^{d}k}{(2\pi)^{d}}
\sum^{\infty}_{\ell=-\infty}\frac{1}{\sqrt{4\pi}}
\Gamma\left(\frac{3}{2}-\epsilon\right)
\Gamma\left(-1+\epsilon \right)
\left(\sum^{d}_{i=1}(k^{i})^{2}+\frac{\ell^{2}}{b^{2}r^{2}}
\right)^{1-\epsilon}.
\ee
The difference from the previous section is the dimension of the integration over $k$'s.
Carrying out the integration over $k^{i}\ (i=1,\ldots,d)$ and arranging
the sum over $\ell$,
we have
\be
\rho_{0}(b)=-\frac{(\mu br)^{2\epsilon}}{2\pi^{2}
(4\pi)^{(d+1)/2}(br)^{d+3}}
\Gamma\left(\frac{3}{2}-\epsilon\right)
\Gamma\left(-\frac{d}{2}-1+\epsilon\right)
\zeta\left(-d-2+2\epsilon\right).
\label{rd}
\ee
Further applying the reciprocal formula for zeta and gamma functions
\cite{Er}
\be
\zeta(z)\Gamma\left(\frac{z}{2}\right)=
\pi^{z-1/2}\zeta(1-z)\Gamma\left(\frac{1-z}{2}\right)
\ee
to (\ref{rd}), we obtain
\be
\rho_{0}(b)=-\frac{1}{2^{d+3}\pi^{3(d+3)/2}(br)^{d+3}}
\Gamma\left(\frac{d+3}{2}\right)
\zeta\left(d+3\right),
\ee
where the limit $\epsilon\rightarrow 0$ has been taken.

Consequently, the regularized vacuum energy density
for an untwisted conformal scalar filed is given by
\bea
\rho_{vac}&=&\rho_{0}(b)-\rho_{0}(1)\nn
&=&-\frac{1}{(4\pi^{3})^{(d+3)/2}r^{d+3}}
\Gamma\left(\frac{d+3}{2}\right)
\zeta\left(d+3\right)
\left(\frac{1}{b^{d+3}}-1\right)
\label{eq:ved}
\eea

An exact result for $d=0$ has been shown by Souradeep and Sahni \cite{SS}.
 Their result is given by the form of integration,
\be
\rho_{vac:exact}=-\frac{1}{16\pi^{2}r^{3}}
\int^{\infty}_{0}\frac{du}{\sinh  u}
\left(
\frac{\coth  u}{\sinh^{2}  u}-
\frac{\coth  u/b}{b^{3}\sinh^{2}  u/b}
\right),
\label{eq:SSresult}
\ee
where the notation has been changed into ours.

On the other hand, our approximation (\ref{eq:ved}) gives
\be
\rho_{vac:WKB}=-\frac{1}{16\pi^{4}r^{3}}
\zeta\left(3\right)
\left(\frac{1}{b^3}-1\right)\ ,
\ee
for $d=0$.

The comparison between the exact and approximate results
is displayed in FIG. \ref{fig1}. We conclude that the result of the
WKB approximation is
in excellent agreement with the exact value for the three-dimensional case ($d=0$).

\begin{figure}
\centering
\includegraphics[width=8cm]
{wkbfig1.eps}
\caption{$r^{3}\rho_{vac}$ as a function of $b^{-1}$.
The solid line represents the exact value
 $r^{3}\rho_{vac:exact}$, while the dashed line represents
 our approximation
 $r^{3}\rho_{vac:WKB}$.}
\label{fig1}
\end{figure}

\section{Vacuum energy around a global monopole}
\label{sec:gm}
A global monopole \cite{BV}
can be regarded as a geometrical point singularity with
a deficit solid angle, if the finite-mass contribution is neglected.
The metric of the spacetime describing a global monopole is
\be
ds^{2}=-dt^{2}+dr^{2}+b^{2}r^{2}(d\theta^{2}
+\sin^{2}\theta\ d\phi^{2})\ .
\label{eq:1gm}
\ee

It is possible to generalize the metric to the ($d+N+1$)-dimensional one,
\be
ds^{2}=-dt^{2}+(dx^{1})^{2}+\cdots+(dx^{d})^{2}+
dr^{2}+b^{2}r^{2}d\Omega_{N-1}^{2}\  ,
\label{eq:metdn1}
\ee
where $d\Omega_{N-1}^{2}$ is a line element on an $(N-1)$-sphere
 with a unit radius.

The derivation of the formal expression for the vacuum energy of
a conformal scalar field in the spacetime described by the metric (\ref{eq:metdn1}) can be done
 similarly to that in the previous sections.

We have only to notice a few differences.
\begin{itemize}
\item The coupling to the scalar curvature $\xi$ is now
$(d+N-1)/[4(d+N)]$.

\item The value of the scalar curvature is nonzero for $N\geq 3$.
\item The mode function takes the form
\[
\varphi=
\frac{1}{r^{(N-2)/2}}
e^{-i\omega  t}e^{ikz}Y_{\ell\nu}^{(N-1)}(\Omega)
\chi_{\omega k \ell}(r)\ ,
\]
where
$Y_{\ell\nu}^{(N-1)}(\Omega)$ is the generalized spherical function
whose eigen value for the laplacian on $S^{N-1}$ is $\ell(\ell+N-2)$.
\end{itemize}

Hence we obtain
\be
\rho_{0}(b)=
-\frac{(\mu  br)^{2\epsilon}\Gamma(N/2)}{2^{d+3}\pi^{(d+N+3)/2}
(br)^{d+N+1}}
\Gamma\left(\frac{3}{2}-\epsilon\right)
\Gamma\left(-\frac{d}{2}-1+\epsilon\right)
\sum^{\infty}_{\ell=0}D_{\ell}
{\left[{\left(\ell+\frac{N-2}{2}\right)}^{2}+\sigma^{2}\right]}
^{\frac{d}{2}+1-\epsilon}\  ,
\label{eq:rbdn1}
\ee
where
\be
D_{\ell}\equiv
\frac{(2\ell+N-2)(\ell+N-3)!}{(N-2)!\ell !}\ ,
\ee
and
\be
\sigma^{2}\equiv
\frac{(d+1)(N-2)}{4(d+N)}(1-b^{2})\ .
\ee
The choice $d=1$ and $N=2$ leads to the vacuum energy around
 a cosmic string (\ref{eq:unsum}), etc..

Various ways to regularize the divergent quantity are
 known \cite{CW}.
 Instead of investigating general treatment, we study here the
 ``original'' case
with the metric (\ref{eq:1gm})
($d=0$ and $N=3$), i.e., the case with
a global monopole at the origin.
 The generalization of this example
to other cases is straightforward.

For $d=0$ and $N=3$, (\ref{eq:rbdn1}) becomes
\be
\rho_{0}(b)=-\frac{(\mu br)^{2\epsilon}}{2^{4}\pi^{5/2}(br)^{4}}
\Gamma\left(\frac{3}{2}-\epsilon\right)
\Gamma\left(-1+\epsilon\right)
\sum^{\infty}_{\ell=0}\ (2\ell+1)
{\left[{\left(\ell+\frac{1}{2}\right)}^{2}+\sigma^{2}\right]}
^{1-\epsilon}\ ,
\label{eq:rbgm}
\ee
with
\be
\sigma^{2}\equiv
\frac{1-b^{2}}{12}\ .
\ee
Using an expansion \cite{CW}
\be
{\left[{\left(\ell+\frac{1}{2}\right)}^{2}+\sigma^{2}\right]}
^{1-\epsilon}
=\sum^{\infty}_{m=0}\frac{\Gamma(m-1+\epsilon)}
{\Gamma(-1+\epsilon)\ m!} (-\sigma^{2})^{m}
{\left(\ell+\frac{1}{2}\right)}^{2-2\epsilon-2m}\ ,
\ee
we rewrite (\ref{eq:rbgm}) as
\be
\rho_{0}(b)=-\frac{(\mu br)^{2\epsilon}}{2^{3}\pi^{5/2}(br)^{4}}
\Gamma\left(\frac{3}{2}-\epsilon\right)
\sum^{\infty}_{m=0}\frac{\Gamma(m-1+\epsilon)}
{m!} (-\sigma^{2})^{m}
(2^{2m-3+2\epsilon}-1)\zeta(2m-3+2\epsilon)\ .
\ee

For the first three terms in the sum diverges as $1/\epsilon$
in the limit $\epsilon\rightarrow 0$,
we introduce the renormalization scale $\bar{\mu}$,
which involves the mass parameter $\mu$.
We can regard that the divergence and other finite terms
are absorbed into the choice of the renormalization scale.

Then we get the following expression
in the limit of $\epsilon\rightarrow 0$:
\be
\rho_{0}(b)=
-\frac{1}{768\pi^{2}(br)^{4}}
\left[\frac{7}{10}-\frac{1}{3}(1-b^2)+\frac{1}{6}(1-b^2)^2
\right]
\ln \bar{\mu} r\ .
\label{eq:gg}
\ee

The result should be  compared with the one obtained
by Mazzitelli and Lousto \cite{ML}.
In our notation, their result in \cite{ML} should read as
\be
\rho_{vac}=-\frac{1}{720\pi^{2}(b\,r)^{4}}(1-b^{2})
\left(1-\frac{1-b^{2}}{2}\right)\ \ln \bar{\mu} r\ ,
\ee
since a factor two has been missed there (cf.\ \cite{BD}).

One can easily find that this coincides with the vacuum energy density
obtained by our WKB approach $\rho_{vac}=\rho_{0}(b)-\rho_{0}(1)$, where
$\rho_{0}(b)$ is given in (\ref{eq:gg}).

\section{Summary}
\label{sec:sum}

We have shown the validity of the WKB method to obtain
one-loop vacuum energy density of a conformally invariant scalar
field around geometrical defects.

In particular, for the case with
a straight casmic string in four dimensional spacetime,
we have found that the WKB evaluation reproduces
an exact value of the vacuum energy density
for untwisted or twisted conformal scalar fields.
In the case with a three-dimensional conical spacetime,
the WKB result is not an exact value

but an excellent approximation of the vacuum energy density for
a conformally invariant scalar field.
The vacuum energy density around a global monopole has been
calculated by the WKB method   for
a conformally invariant scalar field.
The result coincides with the one obtained by another method.

The varidity of our WKB approach
is ensured by the following.
\begin{itemize}
\item The background metric of the present model
 contains no dimensionful constants except for $r$.
\item The Lagrangian for a scalar field in the present model
 is conformally invariant.
\item The regularized quantity is considered to be largely relied
on the divergence from rather high frequency modes.
\end{itemize}

It will be worth studying generalization of the WKB method
 to evaluation of free energy density of
 quantum fields in finite-temperature system with
geometrical defects.

\bibliographystyle{apsrev4-1}


TITLE: Why do two approaches to this capacitors problem give two answers?
QUESTION [0 upvotes]: I came across a capacitors problem that seemed to be very simple, but I can't figure reasoning as to why two approaches to the problem yield two different answers. One of them is wrong, but I can't tell why.

So in the figure above, consider the two faces of the cube connected by the wires as parallel plates of a capacitor, each with area $A$. It is filled completely with two materials of dielectric constants $\epsilon_1=2$ and $\epsilon_2=4$. The side length of the cube is $d$. Now, I thought of two ways to 'break' the system, as below:

The first figure is the correct way of doing the problem, and after calculating the capacitances of each individual block, and finding the net capacitance, the answer comes out to be $\frac{7A\epsilon_0}{3d}$. The second figure is what I thought could be another way of solving the question, but it yields a very different answer of about $\frac{12A\epsilon_0}{5d}$. And I cannot tell why. The reason could be that the potential of the face where I am making the partition in the second figure is not the same for both blocks (the ones to the right), so assigning them a parallel combination is an error. But I can't tell why the potential should be different. The charge is flowing to those blocks in a very uniform way from the left, they can't be at a different potential.
Original question from JEE Advanced 2015 paper 2Apologies if the figure is a bit sketchy, I tried my best to recreate it as I could not find a clear image of the problem on the internet.
Edit: In the first figure, the two blocks at the top are in series and the bottom block is in parallel combination with them. In the second figure, the two blocks at the right are in a parallel combination, and the block at the left is in a series combination with them.

REPLY [3 votes]: But I can't tell why the potential should be different. The charge is flowing to those blocks in a very uniform way from the left, they can't be at a different potential.
The above statement is the major mistake.
Let me assume your above statement is true, that there is uniform charge distribution on the plates, meaning electric field between the plates is E in free space.
So the field everywhere inside the dielectric e$_1$ is $\frac {E}{e_1} $
Similarly inside the dielectric e$_2$ it is $\frac {E}{e_2} $.
As it is a metal plate let the left plate have a constant potential V throughout.
Now travel from the left plate to the right through the top dielectrics (I'm really sorry that I couldn't attach a diagram right now)
The potential drop will be $\frac {Ed}{e_1} $+$\frac {Ed}{e_2} $ where d is the width of each dielectric
But if you travel similarly through the bottom portion the potential drop is $\frac {E×2d}{e_1} $
As the first plate is at the same potential this implies that the 2nd plate is at a different potential(For the given values of e $_1$ and e $_2$! Hence our assumption that the charge distribution on each plate is uniform is faulty.
This can now be done by taking field on the top portion as E1 and the bottom as E2.
Now equating them with the potential drops you should be able to prove your first approach.
A common rule of thumb I use is to take an entire strip of the dielectric between 2 plates and find the resultant capacitance of that strip considering dielectrics in series, then add those strips in parallel. You should be able to prove this as above


TITLE: Solutions to $1 - \frac{r'^2}{2c^2} + \frac{r r''}{c^2}=0$?
QUESTION [0 upvotes]: Sage says that$$\sqrt{2 \, c^{2} - e^{K_{1}} r\left(t\right)} e^{\left(-K_{1}\right)} = K_{2} + t$$$$-2\sqrt{2 \, c^{2} - e^{K_{1}} r\left(t\right)} e^{\left(-K_{1}\right)} = K_{2} + t$$are solutions to$$1 - \frac{r'^2}{2c^2} + \frac{r r''}{c^2}=0.$$Is that right?

REPLY [1 votes]: $$
1-\frac{r'^2}{2c^2} + \frac{rr''}{c^2} = 0
$$
$$
r'' = r'\dfrac{d}{dr}r'
$$
thus
$$
1 - \frac{r'^2}{2c^2} + \frac{r}{c^2}r'\dfrac{d}{dr}r' = \frac{r}{2c^2}\dfrac{d}{dr}r'^2 - \frac{r'^2}{2c^2}+1
$$
let $y = \frac{r'^2}{2c^2}$ we find
$$
r\dfrac{dy}{dr} -y+1 = 0
$$
thus
$$
\dot{y} -\frac{1}{r}y = -\frac{1}{r}
$$
integrating factor methods
$$
y\mathrm{e}^{-\ln r} = -\int\frac{1}{r}\mathrm{e}^{-\ln r}dr + C_1
$$
$$
\frac{y}{r} = -\int \frac{1}{r^2}dr + C_1 = \frac{1}{r} +C_1
$$
leads to
$$
y = 1 + C_1r = \frac{r'^2}{2c^2}
$$
thus
$$
r'^2 = 2c^2\left(1 + C_1r\right)\implies r' = \pm\sqrt{1+C_1r}\sqrt{2}c
$$
and solve.


TITLE: Channel Capacity of a Cycle Graph
QUESTION [1 upvotes]: I have the following problem: Given a discrete memoryless channel $Y = X + Z \mod5$, where $X$ is selected from one of 5 symbols (0, 1, 2, 3, 4), $Z$ randomly selected from (-1, 0, 1), and $X$ and $Z$ are independent, find the channel capacity. This is equivalent to finding the capacity of an undirected cycle graph.
The solution I have in hand starts with:
$C = \sup_{p_X(x)} I(X;Y) = \sup_{p_X(x)} H(Y) - H(Y|X)$
It then assumes that this is maximized if $Y$ has a uniform distribution, such that $H(Y) = log_2(5)$, and further assumes that $X$ will have a uniform distribution as a consequence. To get $H(Y|X)$, I assume that $H(Y|X) = H(X+Z\mod5|X) = H(Z|X)$, as $X$ does not add entropy if it is known. Since $X$ and $Z$ are independent, I then end up with $C = log_2(5) - H(Z)$.
This seems wrong, as it implies that the channel capacity of an undirected cycle graph can easily be found, but everything I've read says otherwise. Namely, that the capacity of an n-cycle graph cannot be reasonably calculated, and that for a 5-cycle, the actual channel capacity is something like $C = log_2(\sqrt5)$
Is there a flaw in my reasoning here? Am I misunderstanding my problem, and it really isn't equivalent to a cycle graph? Or is this right, and the capacity can be easily calculated if $H(Z)$ is known?
Edit:
The reason I'm confused is that this wikipedia article seems to perfectly describe this problem, yet lists the general case as an open problem in mathematics. The Wolfram Mathworld article on Shannon capacity does the same. Thus, I can't help but think that I'm making a critical error in my assumptions.
Even more interesting is that my reasoning that $X$ will have a uniform distribution, same as $Y$, must be wrong, as they would then have the same entropy, $log_2(5)$. Since $Y$ has been corrupted by random variable $Z$, this cannot be the case, right?

REPLY [1 votes]: Compare the following two definitions:
(i) Rate $R$ is achievable for a given channel if there exists a sequence of $\left(2^{nR},n \right)$-codes such that the probability of decoding error goes to zero as $n$ goes to infinity. Shannon capacity is the supremum of all achievable rates.
(ii) Rate $R$ is achievable with zero error for a given channel if there exists a $\left( 2^{nR},n\right)$-code with zero probability of decoding error. Zero-error capacity is the supremum of all achievable rates with zero-error.
The capacity of a graph $G$ refers to the zero-error capacity of the channel defined by the graph $G$, whereas your initial problem considers the traditional notion of Shannon capacity, which only asks for asymptotically vanishing error probability; hence, it is not equivalent to finding the capacity of an undirected cycle graph.