Hill’s diagrammatic method#
As discussed earlier in Markov chain tree theorem, the Markov chain tree theorem (also called Hill’s diagrammatic method) provides algebraic expressions for the steady-state probabilities of a receptor model. The function hill_diagrammatic_method() below takes a symbolic generator matrix for such a Markov chain as input and, using the Markov chain tree theorem, calculates the steady-state probability of each state.
def hill_diagrammatic_method(Q):
n = Q.nrows()
if Q.ncols() != n:
raise ValueError
z = [0]*n
for i in range(n):
a = [ j for j in range(n) ]
a.remove(i)
z[i] = (-1)^(n-1)*Q[a,a].determinant().simplify_full()
return z
Note
The receptor models considered here have state-transition diagrams with the topology of a simple symmetric directed graph (connected, no loops). The Markov chain tree theorem always applies to receptor models with these properties. However, there are Markov chains that cannot be analyzed in this way (e.g., Markov chains with an infinite number of states).
Receptor model with the topology of the cycle graph \(C_3\)#
To illustrate the function hill_diagrammatic_method(), consider a three-state receptor model that has a cycle.
var('p0 p1 p2 a01 a10 a02 a20 a12 a21')
d = {0: {1:a01, 2:a02}, 1: {0:a10, 2:a12}, 2: {1:a21, 0:a20}};
G = DiGraph(d,weighted=True)
vertex_positions = {0: (0, 0), 1: (1, 1.41), 2: (2, 0)}
G.plot(figsize=4,edge_labels=True,pos=vertex_positions,graph_border=True)
A module that was compiled using NumPy 1.x cannot be run in
NumPy 2.2.6 as it may crash. To support both 1.x and 2.x
versions of NumPy, modules must be compiled with NumPy 2.0.
Some module may need to rebuild instead e.g. with 'pybind11>=2.12'.
If you are a user of the module, the easiest solution will be to
downgrade to 'numpy<2' or try to upgrade the affected module.
We expect that some modules will need time to support NumPy 2.
Traceback (most recent call last): File "/usr/lib/python3.10/runpy.py", line 196, in _run_module_as_main
return _run_code(code, main_globals, None,
File "/usr/lib/python3.10/runpy.py", line 86, in _run_code
exec(code, run_globals)
File "/usr/lib/python3/dist-packages/sage/repl/ipython_kernel/__main__.py", line 3, in <module>
IPKernelApp.launch_instance(kernel_class=SageKernel)
File "/usr/lib/python3/dist-packages/traitlets/config/application.py", line 846, in launch_instance
app.start()
File "/usr/lib/python3/dist-packages/ipykernel/kernelapp.py", line 677, in start
self.io_loop.start()
File "/usr/lib/python3/dist-packages/tornado/platform/asyncio.py", line 199, in start
self.asyncio_loop.run_forever()
File "/usr/lib/python3.10/asyncio/base_events.py", line 603, in run_forever
self._run_once()
File "/usr/lib/python3.10/asyncio/base_events.py", line 1909, in _run_once
handle._run()
File "/usr/lib/python3.10/asyncio/events.py", line 80, in _run
self._context.run(self._callback, *self._args)
File "/usr/lib/python3/dist-packages/ipykernel/kernelbase.py", line 461, in dispatch_queue
await self.process_one()
File "/usr/lib/python3/dist-packages/ipykernel/kernelbase.py", line 450, in process_one
await dispatch(*args)
File "/usr/lib/python3/dist-packages/ipykernel/kernelbase.py", line 357, in dispatch_shell
await result
File "/usr/lib/python3/dist-packages/ipykernel/kernelbase.py", line 652, in execute_request
reply_content = await reply_content
File "/usr/lib/python3/dist-packages/ipykernel/ipkernel.py", line 353, in do_execute
res = shell.run_cell(code, store_history=store_history, silent=silent)
File "/usr/lib/python3/dist-packages/ipykernel/zmqshell.py", line 532, in run_cell
return super().run_cell(*args, **kwargs)
File "/usr/lib/python3/dist-packages/IPython/core/interactiveshell.py", line 2914, in run_cell
result = self._run_cell(
File "/usr/lib/python3/dist-packages/IPython/core/interactiveshell.py", line 2960, in _run_cell
return runner(coro)
File "/usr/lib/python3/dist-packages/IPython/core/async_helpers.py", line 78, in _pseudo_sync_runner
coro.send(None)
File "/usr/lib/python3/dist-packages/IPython/core/interactiveshell.py", line 3185, in run_cell_async
has_raised = await self.run_ast_nodes(code_ast.body, cell_name,
File "/usr/lib/python3/dist-packages/IPython/core/interactiveshell.py", line 3377, in run_ast_nodes
if (await self.run_code(code, result, async_=asy)):
File "/usr/lib/python3/dist-packages/IPython/core/interactiveshell.py", line 3457, in run_code
exec(code_obj, self.user_global_ns, self.user_ns)
File "/tmp/ipykernel_11707/710070645.py", line 5, in <module>
G.plot(figsize=Integer(4),edge_labels=True,pos=vertex_positions,graph_border=True)
File "/usr/lib/python3/dist-packages/IPython/core/displayhook.py", line 262, in __call__
format_dict, md_dict = self.compute_format_data(result)
File "/usr/lib/python3/dist-packages/IPython/core/displayhook.py", line 151, in compute_format_data
return self.shell.display_formatter.format(result)
File "/usr/lib/python3/dist-packages/sage/repl/display/formatter.py", line 181, in format
sage_format, sage_metadata = self.dm.displayhook(obj)
File "/usr/lib/python3/dist-packages/sage/repl/rich_output/display_manager.py", line 825, in displayhook
plain_text, rich_output = self._rich_output_formatter(obj, dict())
File "/usr/lib/python3/dist-packages/sage/repl/rich_output/display_manager.py", line 643, in _rich_output_formatter
rich_output = self._call_rich_repr(obj, rich_repr_kwds)
File "/usr/lib/python3/dist-packages/sage/repl/rich_output/display_manager.py", line 603, in _call_rich_repr
return obj._rich_repr_(self)
File "/usr/lib/python3/dist-packages/sage/plot/graphics.py", line 1000, in _rich_repr_
return display_manager.graphics_from_save(
File "/usr/lib/python3/dist-packages/sage/repl/rich_output/display_manager.py", line 731, in graphics_from_save
save_function(filename, **kwds)
File "/usr/lib/python3/dist-packages/sage/misc/decorators.py", line 410, in wrapper
return func(*args, **kwds)
File "/usr/lib/python3/dist-packages/sage/plot/graphics.py", line 3296, in save
from matplotlib import rcParams
File "/usr/lib/python3/dist-packages/matplotlib/__init__.py", line 109, in <module>
from . import _api, _version, cbook, docstring, rcsetup
File "/usr/lib/python3/dist-packages/matplotlib/rcsetup.py", line 27, in <module>
from matplotlib.colors import Colormap, is_color_like
File "/usr/lib/python3/dist-packages/matplotlib/colors.py", line 56, in <module>
from matplotlib import _api, cbook, scale
File "/usr/lib/python3/dist-packages/matplotlib/scale.py", line 23, in <module>
from matplotlib.ticker import (
File "/usr/lib/python3/dist-packages/matplotlib/ticker.py", line 136, in <module>
from matplotlib import transforms as mtransforms
File "/usr/lib/python3/dist-packages/matplotlib/transforms.py", line 46, in <module>
from matplotlib._path import (
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
AttributeError: _ARRAY_API not found
/usr/lib/python3/dist-packages/sage/repl/rich_output/display_manager.py:608: RichReprWarning: Exception in _rich_repr_ while displaying object: numpy.core.multiarray failed to import
warnings.warn(
A module that was compiled using NumPy 1.x cannot be run in
NumPy 2.2.6 as it may crash. To support both 1.x and 2.x
versions of NumPy, modules must be compiled with NumPy 2.0.
Some module may need to rebuild instead e.g. with 'pybind11>=2.12'.
If you are a user of the module, the easiest solution will be to
downgrade to 'numpy<2' or try to upgrade the affected module.
We expect that some modules will need time to support NumPy 2.
Traceback (most recent call last): File "/usr/lib/python3.10/runpy.py", line 196, in _run_module_as_main
return _run_code(code, main_globals, None,
File "/usr/lib/python3.10/runpy.py", line 86, in _run_code
exec(code, run_globals)
File "/usr/lib/python3/dist-packages/sage/repl/ipython_kernel/__main__.py", line 3, in <module>
IPKernelApp.launch_instance(kernel_class=SageKernel)
File "/usr/lib/python3/dist-packages/traitlets/config/application.py", line 846, in launch_instance
app.start()
File "/usr/lib/python3/dist-packages/ipykernel/kernelapp.py", line 677, in start
self.io_loop.start()
File "/usr/lib/python3/dist-packages/tornado/platform/asyncio.py", line 199, in start
self.asyncio_loop.run_forever()
File "/usr/lib/python3.10/asyncio/base_events.py", line 603, in run_forever
self._run_once()
File "/usr/lib/python3.10/asyncio/base_events.py", line 1909, in _run_once
handle._run()
File "/usr/lib/python3.10/asyncio/events.py", line 80, in _run
self._context.run(self._callback, *self._args)
File "/usr/lib/python3/dist-packages/ipykernel/kernelbase.py", line 461, in dispatch_queue
await self.process_one()
File "/usr/lib/python3/dist-packages/ipykernel/kernelbase.py", line 450, in process_one
await dispatch(*args)
File "/usr/lib/python3/dist-packages/ipykernel/kernelbase.py", line 357, in dispatch_shell
await result
File "/usr/lib/python3/dist-packages/ipykernel/kernelbase.py", line 652, in execute_request
reply_content = await reply_content
File "/usr/lib/python3/dist-packages/ipykernel/ipkernel.py", line 353, in do_execute
res = shell.run_cell(code, store_history=store_history, silent=silent)
File "/usr/lib/python3/dist-packages/ipykernel/zmqshell.py", line 532, in run_cell
return super().run_cell(*args, **kwargs)
File "/usr/lib/python3/dist-packages/IPython/core/interactiveshell.py", line 2914, in run_cell
result = self._run_cell(
File "/usr/lib/python3/dist-packages/IPython/core/interactiveshell.py", line 2960, in _run_cell
return runner(coro)
File "/usr/lib/python3/dist-packages/IPython/core/async_helpers.py", line 78, in _pseudo_sync_runner
coro.send(None)
File "/usr/lib/python3/dist-packages/IPython/core/interactiveshell.py", line 3185, in run_cell_async
has_raised = await self.run_ast_nodes(code_ast.body, cell_name,
File "/usr/lib/python3/dist-packages/IPython/core/interactiveshell.py", line 3377, in run_ast_nodes
if (await self.run_code(code, result, async_=asy)):
File "/usr/lib/python3/dist-packages/IPython/core/interactiveshell.py", line 3457, in run_code
exec(code_obj, self.user_global_ns, self.user_ns)
File "/tmp/ipykernel_11707/710070645.py", line 5, in <module>
G.plot(figsize=Integer(4),edge_labels=True,pos=vertex_positions,graph_border=True)
File "/usr/lib/python3/dist-packages/IPython/core/displayhook.py", line 262, in __call__
format_dict, md_dict = self.compute_format_data(result)
File "/usr/lib/python3/dist-packages/IPython/core/displayhook.py", line 151, in compute_format_data
return self.shell.display_formatter.format(result)
File "/usr/lib/python3/dist-packages/sage/repl/display/formatter.py", line 186, in format
if (not isinstance(obj, (IPYTHON_NATIVE_TYPES, Figure)) and
File "/usr/lib/python3/dist-packages/matplotlib/__init__.py", line 109, in <module>
from . import _api, _version, cbook, docstring, rcsetup
File "/usr/lib/python3/dist-packages/matplotlib/rcsetup.py", line 27, in <module>
from matplotlib.colors import Colormap, is_color_like
File "/usr/lib/python3/dist-packages/matplotlib/colors.py", line 56, in <module>
from matplotlib import _api, cbook, scale
File "/usr/lib/python3/dist-packages/matplotlib/scale.py", line 23, in <module>
from matplotlib.ticker import (
File "/usr/lib/python3/dist-packages/matplotlib/ticker.py", line 136, in <module>
from matplotlib import transforms as mtransforms
File "/usr/lib/python3/dist-packages/matplotlib/transforms.py", line 46, in <module>
from matplotlib._path import (
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
AttributeError: _ARRAY_API not found
---------------------------------------------------------------------------
ImportError Traceback (most recent call last)
/tmp/ipykernel_11707/710070645.py in <module>
3 G = DiGraph(d,weighted=True)
4 vertex_positions = {Integer(0): (Integer(0), Integer(0)), Integer(1): (Integer(1), RealNumber('1.41')), Integer(2): (Integer(2), Integer(0))}
----> 5 G.plot(figsize=Integer(4),edge_labels=True,pos=vertex_positions,graph_border=True)
/usr/lib/python3/dist-packages/IPython/core/displayhook.py in __call__(self, result)
260 self.start_displayhook()
261 self.write_output_prompt()
--> 262 format_dict, md_dict = self.compute_format_data(result)
263 self.update_user_ns(result)
264 self.fill_exec_result(result)
/usr/lib/python3/dist-packages/IPython/core/displayhook.py in compute_format_data(self, result)
149
150 """
--> 151 return self.shell.display_formatter.format(result)
152
153 # This can be set to True by the write_output_prompt method in a subclass
/usr/lib/python3/dist-packages/sage/repl/display/formatter.py in format(self, obj, include, exclude)
184 # use Sage rich output for any except those native to IPython, but only
185 # if it is not plain and dull
--> 186 if (not isinstance(obj, (IPYTHON_NATIVE_TYPES, Figure)) and
187 not set(sage_format.keys()).issubset([PLAIN_TEXT])):
188 return sage_format, sage_metadata
/usr/lib/python3/dist-packages/sage/misc/lazy_import.pyx in sage.misc.lazy_import.LazyImport.__instancecheck__ (build/cythonized/sage/misc/lazy_import.c:7695)()
914 True
915 """
--> 916 return isinstance(x, self.get_object())
917
918 def __subclasscheck__(self, x):
/usr/lib/python3/dist-packages/sage/misc/lazy_import.pyx in sage.misc.lazy_import.LazyImport.get_object (build/cythonized/sage/misc/lazy_import.c:2612)()
215 if likely(self._object is not None):
216 return self._object
--> 217 return self._get_object()
218
219 cpdef _get_object(self):
/usr/lib/python3/dist-packages/sage/misc/lazy_import.pyx in sage.misc.lazy_import.LazyImport._get_object (build/cythonized/sage/misc/lazy_import.c:3073)()
255 if self._feature:
256 raise FeatureNotPresentError(self._feature, reason=f'Importing {self._name} failed: {e}')
--> 257 raise
258
259 name = self._as_name
/usr/lib/python3/dist-packages/sage/misc/lazy_import.pyx in sage.misc.lazy_import.LazyImport._get_object (build/cythonized/sage/misc/lazy_import.c:2935)()
251
252 try:
--> 253 self._object = getattr(__import__(self._module, {}, {}, [self._name]), self._name)
254 except ImportError as e:
255 if self._feature:
/usr/lib/python3/dist-packages/matplotlib/__init__.py in <module>
107 # cbook must import matplotlib only within function
108 # definitions, so it is safe to import from it here.
--> 109 from . import _api, _version, cbook, docstring, rcsetup
110 from matplotlib.cbook import MatplotlibDeprecationWarning, sanitize_sequence
111 from matplotlib.cbook import mplDeprecation # deprecated
/usr/lib/python3/dist-packages/matplotlib/rcsetup.py in <module>
25 from matplotlib import _api, cbook
26 from matplotlib.cbook import ls_mapper
---> 27 from matplotlib.colors import Colormap, is_color_like
28 from matplotlib.fontconfig_pattern import parse_fontconfig_pattern
29 from matplotlib._enums import JoinStyle, CapStyle
/usr/lib/python3/dist-packages/matplotlib/colors.py in <module>
54 import matplotlib as mpl
55 import numpy as np
---> 56 from matplotlib import _api, cbook, scale
57 from ._color_data import BASE_COLORS, TABLEAU_COLORS, CSS4_COLORS, XKCD_COLORS
58
/usr/lib/python3/dist-packages/matplotlib/scale.py in <module>
21 import matplotlib as mpl
22 from matplotlib import _api, docstring
---> 23 from matplotlib.ticker import (
24 NullFormatter, ScalarFormatter, LogFormatterSciNotation, LogitFormatter,
25 NullLocator, LogLocator, AutoLocator, AutoMinorLocator,
/usr/lib/python3/dist-packages/matplotlib/ticker.py in <module>
134 import matplotlib as mpl
135 from matplotlib import _api, cbook
--> 136 from matplotlib import transforms as mtransforms
137
138 _log = logging.getLogger(__name__)
/usr/lib/python3/dist-packages/matplotlib/transforms.py in <module>
44
45 from matplotlib import _api
---> 46 from matplotlib._path import (
47 affine_transform, count_bboxes_overlapping_bbox, update_path_extents)
48 from .path import Path
ImportError: numpy.core.multiarray failed to import
Because every edge has an associated symbolic variable, we can produce the generator matrix as follows.
def generator(A):
return A-diagonal_matrix(sum(A.T))
Q = generator(G.weighted_adjacency_matrix(sparse=False))
show(Q)
The relative probabilities according to hill_diagrammatic_method() are:
z = hill_diagrammatic_method(Q)
for i in range(3):
print('z[%s] ='%i, f'{expand(z[i])}')
Each relative probability, when expanded, is a multinomial with three terms, because there are three spanning trees rooted in each vertex. Each term has two factors because any spanning tree of the cycle graph \(C_3\) has two edges.
Receptor model with topology of the House Graph#
We conclude this section with a receptor model that has more than one cycle, namely, the house graph.
var('p0 p1 p2 p3 p4 a01 a10 a02 a20 a04 a40 a12 a21 a23 a32 a34 a43')
d = {0: {1:a01, 2:a02, 4:a04}, 1: {0:a10, 2:a12}, 2: {1:a21, 0:a20, 3:a23}, 3: {2:a32, 4:a34}, 4: {3:a43, 0:a40}};
G = DiGraph(d,weighted=True)
vertex_positions = {0: (0, 0), 1: (1, 1.41), 2: (2, 0), 3: (2,-2), 4: (0,-2)}
G.plot(figsize=8,edge_labels=True,pos=vertex_positions,graph_border=True)
Q = generator(G.weighted_adjacency_matrix(sparse=False))
show(Q)
z = hill_diagrammatic_method(Q)
for i in range(5):
print('z[%s] ='%i, f'{expand(z[i])}')
In this case, each of the five relative probabilities is a multinomial with 10 terms because there are 10 rooted spanning trees associated to each state (vertex). Each term has 4 factors because any spanning tree of the house graph has 4 edges.