  The problem of polar coding for an arbitrary sequence of independent
binary-input memoryless symmetric (BMS) channels $\left\{W_i\right\}_{i=1}^{N}$
is considered. The sequence of channels is assumed to be completely known to
both the transmitter and the receiver (a coherent scenario). Also, at each code
block transmission, each of the channels is used only once. In other words, a
codeword of length $N$ is constructed and then the $i$-th encoded bit is
transmitted over $W_i$. The goal is to operate at a rate $R$ close to the
average of the symmetric capacities of $W_i$'s, denoted by $\overline{I}_N$. To
this end, we construct a polar coding scheme using Arikan's channel
polarization transform in combination with certain permutations at each
polarization level and certain skipped operations. In particular, given a
non-stationary sequence of BMS channels $\left\{W_i\right\}_{i=1}^{N}$ and
$P_e$, where $0 < P_e <1$, we construct a polar code of length $N$ and rate $R$
guaranteeing a block error probability of at most $P_e$ for transmission over
$\left\{W_i\right\}_{i=1}^{N}$ such that $$ N \leq
\frac{\kappa}{(\overline{I}_N - R)^{\mu}}, $$ where $\mu$ is a constant and
$\kappa$ is a constant depending on $P_e$ and $\mu$. We further show a
numerical upper bound on $\mu$ that is: $\mu \leq 7.34$ for non-stationary
binary erasure channels and $\mu \leq 8.54$ for general non-stationary BMS
channels. The encoding and decoding complexities of the constructed polar code
preserve $O(N \log N)$ complexity of Arikan's polar codes. In an asymptotic
sense, when coded bits are transmitted over a non-stationary sequence of BMS
channels $\left\{W_i\right\}_{i=1}^{\infty}$, our proposed scheme achieves the
average symmetric capacity $$ \overline{I}(\left\{W_i\right\}_{i=1}^{\infty})
:= \lim_{N\rightarrow \infty} \frac{1}{N}\sum_{i=1}^N I(W_i), $$ assuming that
the limit exists.
