Problem 1: Unbiased Random Walk Hitting 0¶

In the CRN Problem Session, Problem 2, we studied a birth-death process. This can be seen as a random walk on the natural numbers.

Here, we want you to use a simple and powerful argument that sometimes works. Assume we start at a $k \geq 0$. If $k = 0$, we are done. If not, we move left to $k-1$ with probability $1/2$ and right to $k+1$ with $1/2$. This is called an unbiased random walk on the line with adsorption at $0$.

a) Show that this random walk hits $0$ with probability $1$ repeatedly using symmetry arguments (going left is as likely as going right for the same distance).

Show hint

For any position $k$ the probability of hitting $0$ and $2k$ is identical by symmetry. Further, one can show that it must sum up to $1$ (the probability it always stays within 1 and $2k-1$ is 0.) Thus both must be $1/2$.

Repeat this argument.

Problem 2: Self-Destructive Interactions¶

We discussed in the lecture a simple distributed algorithm / CRN with the only reaction being

$$ A + B \rightarrow \emptyset $$

a) Write a formula for the expected time until consensus is reached assuming the system starts at $A_0 > B_0$.

Show hint

Each, A and B, decreases simultaneously by 1 at rate

$$ \delta A B $$

Assuming the population starts at $A_0 > B_0$, it traverses the states $(A_0 - k, B_0 - k)$ for $0 \leq k \leq B_0$. Each of the decrements follows an exponential distribution and the decrements are independent from each other.

b) For a fixed $B_0$ that is the minimum of $A_0$ and $B_0$, what is the $A_0 \geq B_0$ that has the worst-case (maximal) time until consensus.

Show hint

Take the formula you derived in (a) and study when the terms

$$ \frac{1}{\delta (A_0-k)(B_0-k)} $$

are maximal for $A_0$ given that $A_0 \geq B_0$.

c) Given the outcomes from (a) and (b), use the bound in (b) to show that the expected time until consensus is in $O(1)$.

Show hint

Using bound (b), proceed with

$$ \frac{1}{\delta (A_0-k)(B_0-k)} \leq \frac{1}{\delta (B_0-k)^2} $$

and reformulate to bound with

$$ \sum_{m=1}^{\infty}\frac{1}{m^2} $$

Problem 3: Non-Self-Destructive Interactions¶

In this problem, we study the Pairwise Annihilation protocol with non-self-destructive interactions. That is, we replace the reaction $A+B \to \emptyset$ by the two reactions $A+B\to A$ and $A+B \to B$ (both with rate constant $\delta/2$).

How does this change affect the probability of achieving majority consensus? All ways of tackling this problem are fair game, in particular analytical reasoning, simulation, and thought experiments with proof ideas.

Show hint

For simulation: Change the MobsPy code to the given reactions and compare the results.

For analysis and thought experiments: The random choice which of the two species dies behaves like an unbiased coin. Each coin flip has the possibility to decrease or increase the difference by $1$. Consider how many coin flips are needed for the majority to win (at least, there may be more in fact). Now check how likely it is for such many coin flips to reverse the order of A and B for a given gap $A-B$.

More hints

For analysis and thought experiments: Take a look at the Binomial distribution (approximated well by the Normal distribution for large $n$).

Problem 4: Biological Implementation via Conjugation¶

In this problem, we want to model and simulate a plausible biological implementation of the Pairwise Annihilation protocol. For that, we will assume:

individual birth and death reactions
birth reactions of the form $A + R \to A + A$ with some resource $R$
a typical resource concentration of about $[R] = 10^8 mL^{-1}$ in LB medium
non-self-destructive interactions since bacterial conjugation is uni-directional
a significantly increased death rate (as opposed to instant annihilation) after conjugation by the other species
a realistic conjugation rate for E. coli, taken from this paper for example

Some rates and parameters are missing from the above list. Try to find estimations for them on your own (sources are abound).

a) How would you design the genetic constructs?

Show hint

Think of it as a genetic circuit as we had it in the first lecture. You do not need to specify the parts, but what would be expressed and what does this activate/repress.

b) Analyze the model you came up with via simulation.

Show hint

Copy the MobsPy model from the lecture and modify it accordingly. First plot the behavior over time to get a feeling for its plausibility. Then check if you can reproduce the S-shaped probability curve from the lecture with this model.