.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/information_theory/channels/plot_05_blahut_arimoto.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_information_theory_channels_plot_05_blahut_arimoto.py>`
        to download the full example code or to run this example in your browser via JupyterLite.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_information_theory_channels_plot_05_blahut_arimoto.py:


The Blahut-Arimoto algorithm (1972)
===================================

Most channels have no closed-form capacity. Blahut and Arimoto
independently found an alternating maximization that converges to it,
with upper and lower bounds that squeeze together at every step. Here
it recovers :math:`1 - h(p)` for the binary symmetric channel and
finds the capacity and skewed optimal input of the Z channel, and
:math:`\log_2 3` for the noisy typewriter (send every other letter).

.. GENERATED FROM PYTHON SOURCE LINES 14-37



.. image-sg:: /api/gallery/information_theory/channels/images/sphx_glr_plot_05_blahut_arimoto_001.png
   :alt: BSC(0.1) C = 0.5310, input [0.5 0.5], Z channel (1->0 w.p. 0.4) C = 0.4068, input [0.591 0.409], noisy typewriter, 6 letters C = 1.5850, input [0.167 0.167 0.167 0.167 0.167 0.167]
   :srcset: /api/gallery/information_theory/channels/images/sphx_glr_plot_05_blahut_arimoto_001.png
   :class: sphx-glr-single-img





.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    from mathematicskit.information_theory import blahut_arimoto, bsc_capacity

    channels = {
        "BSC(0.1)": [[0.9, 0.1], [0.1, 0.9]],
        "Z channel (1->0 w.p. 0.4)": [[1.0, 0.0], [0.4, 0.6]],
        "noisy typewriter, 6 letters": 0.5 * np.eye(6) + 0.5 * np.roll(np.eye(6), 1, axis=1),
    }
    fig, axes = plt.subplots(1, 3, figsize=(13, 3.8))
    for ax, (name, W) in zip(axes, channels.items(), strict=True):
        r = blahut_arimoto(W, tol=1e-9)
        k = np.arange(1, r.iterations + 1)
        ax.plot(k, r.upper_bounds, label="upper bound")
        ax.plot(k, r.lower_bounds, label="lower bound")
        ax.set_xscale("log")
        ax.set_title(f"{name}\nC = {r.capacity:.4f}, input {np.round(r.input_distribution, 3)}", fontsize=9)
        ax.set_xlabel("iteration")
    axes[0].axhline(bsc_capacity(0.1), color="k", ls=":", label="1 - h(0.1)")
    axes[0].legend(fontsize=8)
    axes[0].set_ylabel("bits per use")
    fig.tight_layout()


.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.219 seconds)


.. _sphx_glr_download_api_gallery_information_theory_channels_plot_05_blahut_arimoto.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: lite-badge

      .. image:: images/jupyterlite_badge_logo.svg
        :target: ../../../../lite/lab/index.html?path=api/gallery/information_theory/channels/plot_05_blahut_arimoto.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_05_blahut_arimoto.ipynb <plot_05_blahut_arimoto.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_05_blahut_arimoto.py <plot_05_blahut_arimoto.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_05_blahut_arimoto.zip <plot_05_blahut_arimoto.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_