  We study the problem of strong coordination of the actions of two nodes $X$
and $Y$ that communicate over a discrete memoryless channel (DMC) such that the
actions follow a prescribed joint probability distribution. We propose two
novel random coding schemes and a polar coding scheme for this noisy strong
coordination problem, and derive inner bounds for the respective strong
coordination capacity region. The first scheme is a joint coordination-channel
coding scheme that utilizes the randomness provided by the DMC to reduce the
amount of local randomness required to generate the sequence of actions at Node
$Y$. Based on this random coding scheme, we provide a characterization of the
capacity region for two special cases of the noisy strong coordination setup,
namely, when the actions at Node $Y$ are determined by Node $X$ and when the
DMC is a deterministic channel. The second scheme exploits separate
coordination and channel coding where local randomness is extracted from the
channel after decoding. The third scheme is a joint coordination-channel polar
coding scheme for strong coordination. We show that polar codes are able to
achieve the established inner bound to the noisy strong coordination capacity
region and thus provide a constructive alternative to a random coding proof.
Our polar coding scheme also offers a constructive solution to a channel
simulation problem where a DMC and shared randomness are employed together to
simulate another DMC. Finally, by leveraging the random coding results for this
problem, we present an example in which the proposed joint scheme is able to
strictly outperform the separate scheme in terms of achievable communication
rate for the same amount of injected randomness into both systems. Thus, we
establish the sub-optimality of the separation of strong coordination and
channel coding with respect to the communication rate over the DMC.
