Munkres §53: Covering Spaces


Claim: If $Y$ has the discrete topology and $p:X\times Y\to X$ is projection on the first coordinate, then $p$ is a covering map.

Proof: Clearly, $p$ is continuous and surjective, and if $U_x$ is a neighborhood of $x\in X$, then
$$p^{-1}\left(U_x\right)=U_x\times Y=\bigsqcup_{y\in Y}\underbrace{U_x\times\left\{y\right\}}_{V_y},$$
where $\left.p\right|_{V_y}$ is a homeomorphism of $V_y$ onto $U_x$.
$$\tag*{$\blacksquare$}$$
Claim: If $U$ is evenly covered by $p$ and connected, then the partition of $p^{-1}\left(U\right)$ into slices is unique.

Proof: If there exist two distinct slices $\left\{V_\alpha\right\}$ and $\left\{W_\beta\right\}$, then there exists $\alpha'$ with $V_{\alpha'}\neq W_\beta$ for all $\beta$. If $\beta'$ is such that $A:=V_{\alpha'}\cap W_{\beta'}\neq\varnothing$, then
$$\bigcup_{\substack{\alpha\neq\alpha'\\\beta\neq\beta'}}V_\alpha\cap W_\beta=A^c.$$$$\tag*{$\Large↯$}$$
Claim: If $p:E\to B$ is a covering map, $B$ is connected, and $\left|p^{-1}\left(b_0\right)\right|=k$, then $\left|p^{-1}\left(b\right)\right|=k$ for all $b$, so $E$ is a $k$-fold covering of $B$.

Proof: Let $C:=\left\{b\in B:\left|p^{-1}\left(b\right)\right|=k\right\}$, $D:=\left\{b\in B:\left|p^{-1}\left(b\right)\right|\neq k\right\}$, and $b\in C$. Then there is a neighborhood $U\ni b$ such that there is a partition of $p^{-1}\left(U\right)$ into $k$ slices because each slice is homeomorphic to $U$. Therefore, for all $x\in U$, $\left|p^{-1}\left(x\right)\right|=k$, implying that $C$ is open. Similarly, $D$ is open. Finally, note that $C\cap D=\varnothing$ and $C\cup D=B$ by definition. $$\tag*{$\Large↯$}$$
Claim: If $q:X\to Y$ and $r:Y\to Z$ are covering maps and $r^{-1}\left(z\right)$ is finite for all $z\in Z$, then $p=r\circ q$ is a covering map.

Proof: Let $z\in Z$. Then there is a neighborhood $U$ of $z$ such that $\left\{U_i\right\}$ is a finite partition of $r^{-1}\left(U\right)$ into slices. Let $v_i$ be the only element in $r^{-1}\left(z\right)\cap U_i$. Then there is a neighborhood $V_i$ of $v_i$ such that $\left\{V_{i_\alpha}\right\}$ is a partition of $q^{-1}\left(V_i\right)$ into slices. Let$$C:=\bigcap_ir\left(U_i\cap V_i\right).$$Then $C$ is open and evenly covered by $r$. Let $W_{i_\alpha}:=q^{-1}\left(U_i\cap V_i\right)\cap V_{i_\alpha}$. Then $C$ is a neighborhood of $z$ such that $\left\{W_{i_\alpha}\right\}$ is a partition of $p^{-1}\left(C\right)$ into slices.$$\tag*{$\blacksquare$}$$
Claim: If $p:S^1\to S^1$ is defined by $z\mapsto z^n$, where $S^1:=\left\{z\in\mathbb C:\left|z\right|=1\right\}$, then $p$ is a covering map.

Proof: Let $z\in S^1$. Then $z=e^{i\theta'}$ for some $\theta'\in\left[0,2\pi\right)$. Define $\phi:\mathbb R\to S^1$ by $\theta\mapsto e^{i\theta}$, let $U:=\phi\left(\left(\theta'-\pi/2,\theta'+\pi/2\right)\right)$, and let $n=2$. Then$$p^{-1}\left(U\right)=\phi\left(\left(\frac12\theta'-\frac14\pi,\frac12\theta'+\frac14\pi\right)\right)\sqcup\phi\left(\left(\frac12\theta'+\frac34\pi,\frac12\theta'+\frac54\pi\right)\right).$$ This generalizes analogously to arbitrary $n$.$$\tag*{$\blacksquare$}$$
Claim: If $p:E\to B$ is a covering map and $B$ is Hausdorff, then $E$ is Hausdorff.

Proof: Let $x,y\in E$ be distinct. If $p(x)=p(y)$, then $x$ and $y$ are in different slices. Otherwise, there are neighborhoods $U$ and $V$ of $p\left(x\right)$ and $p\left(y\right)$ with slices $\left\{U_i\right\}$ and $\left\{V_i\right\}$. If $U$ and $V$ are disjoint, then $x$ and $y$ are in disjoint slices. Otherwise, since $B$ is Hausdorff, there are disjoint neighborhoods $U'$ and $V'$ of $p\left(x\right)$ and $p\left(y\right)$. Therefore, $p^{-1}\left(U'\right)\cap U_i$ and $p^{-1}\left(V'\right)\cap V_i$ are disjoint neighborhoods of $x$ and $y$. Analogous arguments work for $B$ regular, completely regular, and locally compact Hausdorff.$$\tag*{$\blacksquare$}$$
ClaimIf $p:E\to B$ is a covering map, $B$ is compact, and $p^{-1}\left(b\right)$ is finite for all $b$, then $E$ is compact.

Proof: Let $\left\{U_i\right\}$ be an open cover of $E$ and let $b\in B$. Then there is a neighborhood $V$ of $b$ such that $\left\{V_j\right\}$ is a finite partition of $p^{-1}\left(V\right)$ into slices. Let $U_{i_j}$ be such that $p^{-1}\left(b\right)\cap U_{i_j}\cap V_j\neq\varnothing$. Then $W_b:=\bigcap_jp\left(U_{i_j}\cap V_j\right)$ is a neighborhood of $b$ such that $p^{-1}\left(W_b\right)$ is covered by finitely-many $U_i$. Since $B$ is compact, so finitely-many $W_b$ cover $B$, implying that finitely-many $p^{-1}\left(W_b\right)$ cover $E$. Therefore, finitely-many $U_i$ cover $E$.$$\tag*{$\blacksquare$}$$

Reinforcement Learning, Pt. 1

A Markov Decision Process (MDP) is a $5$-tuple

$$(S,A,P,\gamma,R),$$
where

  1. $S$ is a set of states,
  2. $A$ is a set of actions,
  3. $P:(s,a,s')\mapsto[0,1]$ is a probability distribution representing the probability of going from state $s$ to state $s'$ after taking action $a$,
  4. $\gamma\in[0,1)$, and
  5. $R:S\to\mathbb R$ and $R:S\times A\to\mathbb R$ represent the reward for being in state $s$ and for being in state $s$ after taking action $a$, respectively.
A policy is a map $\pi:S\to A$.

A value associated to a policy $\pi$ is a map

$$\begin{align}V^\pi:S&\to\mathbb R\\s&\mapsto\mathbb E[R(s_0)+\gamma R(s_1)+\gamma^2R(s_2)+\cdots|s_0=s,\pi]\\&=R(s)+\gamma\sum_{s'\in S}P(s,\pi(s),s')V^\pi(s').\end{align}$$
The last expression above is called a Bellman equation.

A policy and its associated value are dual in the sense that one can be determined from the other.

The optimal value is the map

$$\begin{align}V^*:S&\to\mathbb R\\s&\mapsto\max_\pi V^\pi(s)\\&=R(s)+\gamma\max_{a\in A}\sum_{s'\in S}P(s,a,s')V^*(s').\end{align}$$

The optimal policy is the map

$$\begin{align}\pi^*:S&\to A\\s&\mapsto\arg\max_{a\in A}\sum_{s'\in S}P(s,a,s')V^*(s').\end{align}$$

The following is the value iteration algorithm:

  1. Set $V(s)=0$ for all $s\in S$.
  2. For all $s\in S$, set $$V(s)=R(s)+\gamma\max_{a\in A}\sum_{s'\in S}P(s,a,s')V(s').$$
  3. Repeat step 2 until convergence.
Convergence is due to the fact that $V$ is a contraction mapping.

The following is the policy iteration algorithm:

  1. Initialize $\pi$ randomly.
  2. Set $V=V^\pi$.
  3. For all $s\in S$, set $$\pi(s)=\arg\max_{a\in A}\sum_{s'\in S}P(s,a,s')V(s').$$
  4. Repeat step 2 until convergence.

Chess Gem

This is the most insane game that I have ever seen. It was between Stockfish and AlphaZero. It looks like Stockfish is giving up all of its pieces, but they are all poisoned.

Click on the title of the blog entry to render the embed because it appears to be buggy.

Effective Python 86 - 90

Click here for the first post, which contains the context of this series.

Item #86: Consider module-scoped code to configure deployment environments.

  • Programs often need to run in multiple deployment environments that each have unique assumptions and configurations.
  • You can tailor a module's contents to different deployment environments by using normal Python statements in module scope.
  • Module contents can be the product of any external condition, including host introspection through the sys and os modules.

Item #87: Define a root Exception to insulate callers from APIs.

  • Defining root exceptions for modules allows API consumers to insulate themselves from an API.
  • Catching root exceptions can help you find bugs in code that consumes an API.
  • Catching the Python Exception base class can help you find bugs in API implementations.
  • Intermediate root exceptions let you add more specific types of exceptions in the future without breaking your API consumers.

Item #88: Know how to break circular dependencies.

  • Circular dependencies happen when two modules must call into each other at import time. They can cause your program to crash at startup.
  • The best way to break a circular dependency is by refactoring mutual dependencies into a separate module at the bottom of the dependency tree.
  • Dynamic imports are the simplest solution for breaking a circular dependency between modules while minimizing refactoring and complexity.

Item #89: Consider warnings to refactor and migrate usage.

  • The warnings module can be used to notify callers of your API about deprecated usage. Warning messages encourage such callers to fix their code before later changes break their programs.
  • Raise warnings as errors by using the -W error command-line argument to the Python interpreter. This is especially useful in automated tests to catch potential regressions of dependencies.
  • In production, you can replicate warnings into the logging module to ensure that your existing error reporting systems will capture warnings at runtime.
  • It's useful to write tests for the warnings that your code generates to make sure that they'll be triggered at the right time in any of your downstream dependencies.

Item #90: Consider static analysis via typing to obviate bugs.

  • Python has special syntax and the typing built-in module for annotating variables, fields, functions, and methods with type information.
  • Static type checkers can leverage type information to help you avoid many common bugs that would otherwise happen at runtime.
  • There are a variety of best practices for adopting types in your programs, using them in APIs, and making sure they don't get in the way of your productivity.

Effective Python 81 - 85

Click here for the first post, which contains the context of this series.

Item #81: Use tracemalloc to understand memory usage and leaks.

  • It can be difficult to understand how Python programs use and leak memory.
  • The gc module can help you understand which objects exist, but it has no information about how they were allocated.
  • The tracemalloc built-in module provides powerful tools for understanding the sources of memory usage.

Item #82: Know where to find community-built modules.

  • The Python Package Index (PyPI) contains a wealth of common packages that are built and maintained by the Python community.
  • pip is the command-line tool you can use to install packages from PyPI.
  • The majority of PyPI modules are free and open source software.

Item #83: Use virtual environments for isolated and reproducible dependencies.

  • Virtual environments allow you to use pip to install many different versions of the same package on the same machine without conflicts.
  • Virtual environments are created with python -m venv, enabled with source bin/activate, and disabled with deactivate.
  • You can dump all of the requirements of an environment with python3 -m pip freeze. You can reproduce an environment by running python3 -m pip install -r requirements.txt.

Item #84: Write docstrings for every function, class, and module.

  • Write documentation for every module, class, method, and function using docstrings. Keep them up-to-date as your code changes.
  • For modules: Introduce the contents of a module and any important classes or functions that all users should know about.
  • For classes: Document behavior, important attributes, and subclass behavior in the docstring following the class statement.
  • For functions and methods: Document every argument, returned value, raised exception, and other behaviors in the docstring following the def statement.
  • If you're using type annotations, omit the information that's already present in type annotations from docstrings since it would be redundant to have it in both places.

Item #85: Use packages to organize modules and provide stable APIs.

  • Packages in Python are modules that contain other modules. Packages allow you to organize your code into separate, non-conflicting namespaces with unique absolute module names.
  • Simple packages are defined by adding an __init__.py file to a directory that contains other source files. These files become the child modules of the directory's package. Package directories may also contain other packages.
  • You can provide an explicit API for a module by listing its publicly visible names in its __all__ special attribute.
  • You can hide a package's internal implementation by only importing public names in the package's __init__.py file or by naming internal-only members with a leading underscore.
  • When collaborating within a single team or on a single codebase, using __all__ for explicit APIs is probably unnecessary.

Effective Python 76 - 80

Click here for the first post, which contains the context of this series.

Item #76: Verify related behaviors in TestCase subclasses.

  • You can create tests by subclassing the TestCase class from the unittest built-in module and defining one method per behavior you'd like to test. Test methods on TestCase classes must start with the word test.
  • Use the various helper methods defined by the TestCase class, such as assertEqual, to confirm expected behaviors in your tests instead of using the built-in assert statement.
  • Consider writing data-driven tests using the subTest helper method in order to reduce boilerplate.

Item #77: Isolate tests from each other with setUp, tearDown, setUpModule, and tearDownModule.

  • It's important to write both unit tests (for isolated functionality) and integration tests (for modules that interact with each other).
  • Use the setUp and tearDown methods to make sure your tests are isolated from each other and have a clean test environment.
  • For integration tests, use the setUpModule and tearDownModule module-level functions to manage any test harnesses you need for the entire lifetime of a test module and all of the TestCase classes that it contains.

Item #78: Use mocks to test code with complex dependencies.

  • The unittest.mock module provides a way to simulate the behavior of interfaces using the Mock class. Mocks are useful in tests when it's difficult to set up the dependencies that are required by the code that's being tested.
  • When using mocks, it's important to verify both the behavior of the code being tested and how dependent functions were called by that code, using the Mock.assert_called_once_with family of methods.
  • Keyword-only arguments and the unittest.mock.patch family of functions can be used to inject mocks into the code being tested.

Item #79: Encapsulate dependencies to facilitate mocking and testing.

  • When unit tests require a lot of repeated boilerplate to set up mocks, one solution may be to encapsulate the functionality of dependencies into classes that are more easily mocked.
  • The Mock class of the unittest.mock built-in module simulates classes by returning a new mock, which can act as a mock method, for each attribute that is accessed.
  • For end-to-end tests, it's valuable to refactor your code to have more helper functions that can act as explicit seams to use for injecting mock dependencies in tests.

Item #80: Consider interactive debugging with pdb.

  • You can initiate the Python interactive debugger at a point of interest directly in your program by calling the breakpoint built-in function.
  • The Python debugger prompt is a full Python shell that lets you inspect and modify the state of a running program.
  • pdb shell commands let you precisely control program execution and allow you to alternate between inspecting program state and progressing program execution.
  • The pdb module can be used for debug exceptions after they happen in independent Python programs (using python -m pdb -c continue <program path>) or the interactive Python interpreter (using import pdb; pdb.pm()).

Effective Python 71 - 75

Click here for the first post, which contains the context of this series.

Item #71: Prefer deque for producer-consumer queues.

  • The list type can be used as a FIFO queue by having the producer call append to add items and the consumer call pop(0) to receive items. However, this may cause problems because the performance of pop(0) degrades superlinearly as the queue length increases.
  • The deque class from the collections built-in module takes constant time—regardless of length—for append and popleft, making it ideal for FIFO queues.

Item #72: Consider searching sorted sequences with bisect.

  • Searching sorted data contained in a list takes linear time using the index method or a for loop with simple comparisons.
  • The bisect built-in module’s bisect_left function takes logarithmic time to search for values in sorted lists, which can be orders of magnitude faster than other approaches.

Item #73: Know how to use heapq for priority queues.

  • Priority queues allow you to process items in order of importance instead of in first-in, first-out order.
  • If you try to use list operations to implement a priority queue, your program's performance will degrade superlinearly as the queue grows.
  • The heapq built-in module provides all of the functions you need to implement a priority queue that scales efficiently.
  • To use heapq, the items being prioritized must have a natural sort order, which requires special methods like __lt__ to be defined for classes.

Item #74: Consider memoryview and bytearray for zero-copy interaction with bytes.

  • The memoryview built-in type provides a zero-copy interface for reading and writing slices of objects that support Python's high-performance buffer protocol.
  • The bytearray built-in type provides a mutable bytes-like type that can be used for zero-copy data reads with functions like socket.recv_from.
  • A memoryview can wrap a bytearray, allowing for received data to be spliced into an arbitrary buffer location without copying costs.

Item #75: Use repr strings for debugging output.

  • Calling print on built-in Python types produces the human-readable string version of a value, which hides type information.
  • Calling repr on built-in Python types produces the printable string version of a value. These repr strings can often be passed to the eval built-in function to get back the original value.
  • %s in format strings produces human-readable strings like str. %r produces printable strings like repr. F-strings produce human-readable strings for replacement text expressions unless you specify the !r suffix.
  • You can define the __repr__ special method on a class to customize the printable representation of instances and provide more detailed debugging information.