7
$\begingroup$

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.

enter image description here

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.

enter image description here

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).

enter image description here

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

$\endgroup$
  • 1
    $\begingroup$ If you connect all nodes then you should connect each pair twice (2 directions), since >3 nodes is not a loop. Your ccw triangle would then be a simplified case with the cw transfers being 0%. $\endgroup$ – amI Feb 24 at 4:20
  • $\begingroup$ With the model that I'm going to use this for, transfers are only going to go in one direction for a given connection. $\endgroup$ – SuperCodeBrah Feb 24 at 4:28
  • $\begingroup$ OK, but your box will lack symmetry -- the number of transfers from each node cannot be the same (and there will be more than one 'type' of box). $\endgroup$ – amI Feb 24 at 4:36
  • $\begingroup$ I agree that it will lack symmetry, but symmetry isn't crucial to the problem I'm trying to solve, even if a lack of symmetry does prevent the possibility of reducing the problem into a relatively simple formula/algorithm. I don't know that such a formula exists, but I'm hoping it does. $\endgroup$ – SuperCodeBrah Feb 24 at 4:41
  • 1
    $\begingroup$ Have you seen marcov chains? $\endgroup$ – Dr Xorile Feb 24 at 17:01
12
$\begingroup$

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):

Marcov diagram

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

\begin{equation}M=\begin{bmatrix} 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 \end{bmatrix}\end{equation}

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

\begin{equation}M^{2^{100}}=\begin{bmatrix} 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 \end{bmatrix}\end{equation}

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:

Markov Diagram #2

This has a transition matrix of:

\begin{equation}M=\begin{bmatrix} 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 \end{bmatrix} \end{equation}

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

\begin{equation}M^{2^{100}}=\begin{bmatrix} 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 \end{bmatrix}\end{equation}

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)$.

$\endgroup$
  • 4
    $\begingroup$ I seem to recall there being a closed form solution for the final state distribution on absorbing Markov Chains, Indeed, the wikipedia page gives "absorbing probabilities" in closed form, with only one of the terms requiring a matrix inversion, so the iteration isn't absolutely necessary. $\endgroup$ – Bass Feb 24 at 19:16
  • 2
    $\begingroup$ That's a good point. But I'm dusting off 20-year-old memories here! I knew there was some clever Markov thing, but this was quicker for me to do (especially since the $2**100$ is essentially infinite and takes essentially no computational time at all to do!). I'd have to read up on that to update the answer and I'm out of time today. Unless you want to do it. I would +1 that answer! $\endgroup$ – Dr Xorile Feb 24 at 19:21
  • 2
    $\begingroup$ To add on to Bass' comment, if your original transition matrix is $Q$ (the upper-left block of $M$), we can compute the absorbing matrix $B$ (the upper-right block of $M^\infty$) as follows: let $\tilde Q=I-Q$; $N={\tilde Q}^{-1}$; $R$ is a matrix whose diagonal entries are the sum of the rows of $\tilde Q$; then $B=NR$. $\endgroup$ – 2012rcampion Feb 24 at 19:35
  • $\begingroup$ Well, I just got the kids to bed, and the alternative was doing the dishes, so, naturally.. :-) $\endgroup$ – Bass Feb 24 at 21:26
  • $\begingroup$ I've come across the idea of eigenvector centrality, which I've been able to approximate with an iterative method. Are you aware of a closed form solution that can be inferred from the absorption matrix? I can tell you that the centrality of each node converges to a percentage of the total centrality of the system, but I haven't been able to infer a function. Here's an example of one node's centrality values over a few iterations: 12, 15.035, 16.142, 16.819, 17.207..... 17.938. I hoped that the solution would be 12 / (1 - n), but that's apparently not the case. $\endgroup$ – SuperCodeBrah Mar 22 at 4:41
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice. +1 as promised... $\endgroup$ – Dr Xorile Feb 24 at 21:38
5
$\begingroup$

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. enter image description here

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.

$\endgroup$
  • $\begingroup$ This is amazing. I did notice that B and C both went up by 3% after one round (probably should have checked the next round to see the pattern). I'll have to play with it some more but very good stuff. I'm going to try to set up a more complicated example where every node has an initial, equal value but not all nodes are connected, but I imagine the same principle is in play. $\endgroup$ – SuperCodeBrah Feb 24 at 5:02
  • 1
    $\begingroup$ If you give more than one node initial value, then you'll have to calculate the equilibrium for each initial value and then just add all the equilibrium values together. Also, in my four container example there is only one loop. If the direction of flow was going from B to C and not from C to B, then container B would have a loop of stuff going from B to A to C to D to B and also from B to C to D to B. That's two loops with two common factors, so it's a sum to two geometric series. Not insurmountable, just something to keep an eye for. $\endgroup$ – Amorydai Feb 24 at 5:23
  • $\begingroup$ More great info - thanks. Just out of curiosity, did you recognize the general scenario or were you able to just quickly determine the pattern? If you recognized the scenario, I'd be curious to know in what fields it shows up. Maybe electrical or hydraulic engineering? I was going to use this to make a ranking system for sports where there's a starting amount of value distributed across all teams and winning teams take value from losing teams. It seems like it could be a widely applicable model. $\endgroup$ – SuperCodeBrah Feb 24 at 5:40
  • $\begingroup$ No, nothing like that, just saw that each container will have a running sum and determined that it's a sum of a series, that all. Actually, my previous comment is not entirely clear, thinking's about it some more, container B will still only have one common factor for the series, because that just depends on everything that's coming in and going out. It's just that all the containers will have different factors, not the same factors like in the examples so far. Good luck with your project! $\endgroup$ – Amorydai Feb 24 at 5:51
  • $\begingroup$ Oops, actually, I'm embarrassed. I underestimated the complexity of the four container system. The common factor is not going to be the same for all for of them even in my example. I will edit my answer.. $\endgroup$ – Amorydai Feb 24 at 6:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.