mjhjmtu

I'm trying to derive a generic formula for a programming algorithm. I might be overthinking this or underthinking it... we'll see.

Each of the triangles below represents a container. Each container will transfer a percentage of whatever is transferred into it to the downstream container until a homeostasis is found.

In the diagram, A, B, and C will transfer 50%, 20%, and 30% respectively of what is transferred into them.

Here's what a few iterations of this looks like assuming the first transfer from outside the system is into container A. It's important to note that the amount transferred out of a container at a given iteration would only be a percentage of what is transferred in on the last iteration (i.e., NOT the total already in the container). These numbers appear to be going to a limit (and intuitively they have to be), but I'm not sure what the formula should be.

This is a very simple example, but I'm looking for would need to be able to capture more complex scenarios. This could be done with a brute force approach, but I'm hoping there's a simplified method. As containers are added, things can quickly get out of hand. For example, going from 3 containers to 4 and keeping connections between all of them increases the number of connections from 3 to 6 (I believe this would follow the 1, 3, 6, 10, 15, 21... pattern).

Okay, let's see what you've got, SE.

So this is a classic example of Markov chains. The only slight trick is that you only want the material that's coming in fresh. But that's no problem: we just create a separate container next to each container to absorb the rest of the liquid.

[Aside: As @Bass points out in the comments, this is known as an absorbing Markov chain. However, we will just continue without this as it may be easier to follow. See @Bass's excellent answer for how this can be done using those methods if you know about this.]

So adapt your diagram as follows (which could easily be adapted to as many nodes as you like):

Now if we take the state as A,B,C,A',B',C', then we have a transition matrix of:

beginequationM=beginbmatrix
0 & 0.5 & 0 & 0.5 & 0 & 0 \
0 & 0 & 0.2 & 0 & 0.8 & 0 \
0.3 & 0 & 0 & 0 & 0 & 0.7 \
0 & 0 & 0 & 1 & 0 & 0 \
0 & 0 & 0 & 0 & 1 & 0 \
0 & 0 & 0 & 0 & 0 & 1
endbmatrixendequation

We can then raise this to the power of a large number. I did a loop in python where I set $M = M$**2 ($M$ was a numpy array). This yields:

beginequationM^2^100=beginbmatrix
0.0 & 0.0 & 0.0 & 0.51546 & 0.41237 & 0.07216 \
0.0 & 0.0 & 0.0 & 0.03093 & 0.82474 & 0.14433 \
0.0 & 0.0 & 0.0 & 0.15464 & 0.12371 & 0.72165 \
0.0 & 0.0 & 0.0 & 1.0 & 0.0 & 0.0 \
0.0 & 0.0 & 0.0 & 0.0 & 1.0 & 0.0 \
0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 1.0
endbmatrixendequation

Then, you just need to multiply this by your initial state. In your case, it's $[1,0,0,0,0,0]$, so the top row is your final state. But if you started with some liquid coming into several of them you'd be able to do that too.

And, obviously, this can be easily generalized. You just need to be able to multiply matrices!

For example, suppose we wanted to look at the example created by @VadimEvstifeev. Then we add the nodes to collect the liquid as before:

This has a transition matrix of:

beginequationM=beginbmatrix
0 & 0 & 0.5 & 0.25 & 0.25 & 0 & 0 & 0 \
0.1 & 0 & 0 & 0 & 0 & 0.9 & 0 & 0 \
0 & 0.3 & 0 & 0.4 & 0 & 0 & 0.3 & 0 \
0 & 0.2 & 0 & 0 & 0 & 0 & 0 & 0.8 \
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1
endbmatrix
endequation

Doing the same thing (for i in range(100): M=M**2), we get:

beginequationM^2^100=beginbmatrix
0.0 & 0.0 & 0.0 & 0.0 & 0.25615 & 0.22131 & 0.15369 & 0.36885 \
0.0 & 0.0 & 0.0 & 0.0 & 0.02561 & 0.92213 & 0.01537 & 0.03689 \
0.0 & 0.0 & 0.0 & 0.0 & 0.00973 & 0.35041 & 0.30584 & 0.33402 \
0.0 & 0.0 & 0.0 & 0.0 & 0.00512 & 0.18443 & 0.00307 & 0.80738 \
0.0 & 0.0 & 0.0 & 0.0 & 1.0 & 0.0 & 0.0 & 0.0 \
0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 1.0 & 0.0 & 0.0 \
0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 1.0 & 0.0 \
0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 1.0
endbmatrixendequation

And once again, it depends on your initial state, but if it's $(1,0,0,0,0,0,0,0)$ (i.e. start with 1 in $A$), then the final state is $(0.25615, 0.22131, 0.15369, 0.36885)$.

EDIT: I have underestimated the complexity of the four container system. There are multiple loops and each container will have its own common factor when computing the sum of the geometric series. Alas, I was unable to determine what that factor is yet, because the loops are nesting and my final sum in all containers does not equal exactly 1. My solution for the 3 container system is still valid though.

This is nothing more than a geometric series sum. You have to do one loop just to see what the starting value and the common ratio is. Common ratio will actually be the same for all 3 containers. In your example, container A starts with 1. After a full iteration container A will get 1 * 0.5 * 0.2 * 0.3 = 0.03 back. That's 3% of what it started with. You can see that all the containers will always get back 3% of what they start the round with.

The amount of stuff in container A will be the sum of all that is left in there after each iteration. Since 50% is leaving container A that means that 50% remains. 1/2 * 1 + 1/2 * 0.03 + 1/2 * 0.03^2 + 1/2 * 0.03^3 + ...

The sum of a geometric series is given by the formula: sum(n=0 to infinity) of a * r^n = a / (1 - r).

So the amount of stuff in container A is 1/2 / (1 - 0.03) = 50/97.

For B, 80% is always left in the container. And it first gets 1/2 from A on round one.

4/5 * 1/2 + 4/5 * 1/2 * 0.03 + 4/5 * 1/2 * 0.03^2 + ... = 4/5 * 1/2 / (1 - 0.03) = 40/97

Similarly for C, 70% is left and originally it gets 1/10 from B on round one.

7/10 * 1/10 + 7/10 * 1/10 * .03 + 7/10 * 1/10 + 0.03^2 + ... = 7/10 * 1/10 / (1 - 0.03) = 7/97

As you can see the sum of all the stuff in all the containers is 1.

For more containers you just have to do one iteration and find out the initial value and the common ratio.

In this example the numbers in red indicate the percent that leaves the container. The number in green indicate the value that each container gets on the first round. And the blue number represents the calculated common ratio for the A container. Each container will have a different ratio, but I can't figure out exactly how to find that just yet.

Here's DrXorile's excellent answer for the first question again, but redone with closed form matrix algebra instead of computational iteration. (Contains a program for solving the general case.)

Start by tabulating the transitions in two tables:

How much keeps moving (to where?):

 Q = [ 0 0.5 0 % from A
 0 0 0.2 % from B
 0.3 0 0 ] % from C
 % to A B C
 

How much stops (in where?):

 % stops at A B C 
 R = [ 0.5 0 0 % when visiting A
 0 0.8 0 % when visiting B
 0 0 0.7 ] % when visiting C
 

Then, we look up the correct wikipedia page, and find the clever math trick

..for finding the Absorption Matrix B given these tables. It's like this:

 I = eye(size(Q)) % An Identity Matrix of the proper size
 N = inv ( I - Q ) % The Fundamental Matrix of Q (the clever bit)

The fundamental matrix tells "If you start at some container (each has its own row), how many times would you expect each container (each has its own column) to be visited in total."


Given the fundamental matrix, we can just multiply it by the portion that gets stopped/absorbed each visit (tabulated in matrix R) and the result is the amount that finally ends up in each container.

B = N*R % The Absorption Matrix of Q and R 

and since we start with "everything in A", the result is

just the first row of the absorption matrix B

FromA = B(1, :)

or

0.515464 0.412371 0.072165.

which, as expected, is exactly the same final answer as gotten by @DrXorile.

Since you'll obviously want to mess around with the values, etc, I put this on TIO.run, (the notation above is actually Octave code, ready to run), so you can try it online! Remember to keep both of the matrices Q and R square, and of the same size, if you add more containers to the problem.