How to compute the expected number of sats to arrive in a probabilistic payment flow?

Question

Look at the following network example:

Assume S wants to send 3 sats to R. You can further assume that S has enough liquidity in each of its local channels to send up to 3 sats. Also assume the liquidity in channels (A,R), (B,R) and (C,R) is uniformly distributed.

one optimally reliable payment flow in this diagram looks like this:

1 sat: S --> A --> R   probability: 2/3
2 sats: S --> B --> R  probability: 3/5

This flow has a total probability of 2/3*3/5 = 2/5 = 0.4 = 40%

The question:

How to compute the expected value of Satoshis to arrive at R if S sends 3?

Option A

(which I already know is wrong but I write it down because I suspect some people might have a similar first thought)

Initially I thought this would just be 3 sats * 2/5 = 6/5 sats = 1.2 sats which is what one gets from multiplying the amount to send with the probability of the flow. This seems strange as sending 2 sats along S-->B-->R has a probability of 3/5 and with the reasoning of above an expectation value of 2 sats * 3/5 = 6/5 sats = 1.2 sats. as the expected value for 1 sat along the S-->A-->B path is larger than 0 this would be a contradiction to the additivity of the expected value.

Option B

Starting from the above reasoning we add the expected values for the disjoint paths so:

E[3 sats] = 1 sat * 2/3 + 2 sat * 3/5 = 10/15 sats + 18/15 sats = 28/15 sats

Option C

Of course the 2 satoshi path S-->B-->R does not have to be sent as one onion but could be sent as two onions with 1 sat each:

The first has a probability of 4/5 and the second has a conditional probability of 3/4 which is extensively explained at this issue. With the logic from option B one should be able to add those expected values. so we have the expected value for sending two sats in two seperate 1 sat onions along S--> B --> R would be computed as:

E[2 sats] = 1 sat * 4/5 + 1 sat * 3/4 = 31/20 sats 

If we add the 1 sat onion from the S-->A-->R which was 2/3 sats

we would expect to have

E[3 sats] = 31/20 sats + 2/3 sats = 93/60 sats + 40/60 sats = 132/60 sats = 33/15 sats

This is 5/15 sats = 1/3 sats more than the answer in option B

Option D

To make things worse I am confused if the expected values of dissecting the 2 sat onion in option C into two 1 sat onions can just linearly added up as the second onion is conditioned on having 2 sats of liquidity in the channel. If the first onion has failed the second one will certainly fail. Thus one would have to compute expected value for sending two 1 sat onions like this:

E[2 sats] = 1 sat * 4/5 + 1 sat * 3/5 = 7/5 sats

this would result in a total expected value of:

E[3 sats] = 2/3 sats + 7/5 sats = 10/30 sats + 21/15 sats = 31/15 sats

Thoughts

just for comparison here are the results

• Option A: 18/15
• Option B: 28/15
• Option C: 33/15
• Option D: 31/15

While Option B seems certainly right it makes sense to further dissect the 2 sats onion. In simulations I did it seems that Option D is correct which is a bit surprising for me. Using the formalism of probability theory the difference for the 2 sat path is:

• Option C: E[2 sats] = 1 sat * P(X>=1) + 1 sat * P(X>=2 | X >= 1)
• Option D: E[2 sats] = 1 sat * P(X>=1) + 1 sat * P(X>=2)

As said the simulated setting indicates that Option D is the correct answer but that is highly surprising to me as I would expect the second term to be a conditional probabilty.

Answer 1

Let's review the definition of expected value. The expected value of the random variable X given the state of the system O, denoted as E(X,O) is computed as:

E(X,O) = \sum_i p_i(O) X_i

The sum is over all microstates (all ways in which liquidity could be allocated in the channels) or equivalently one can choose to sum over all possible observable outcomes. The p_i(O) is the probability of verifying i given the state O, and X_i is the value that X takes if i is verified. Using this definition, one immediately sees that E(.,O) is a linear operator:

E(X+a*Y,O) = E(X,O) + a*E(Y,O)

That would be enough to answer your question. You get different answers because you have constructed your observables differently.

Case B

Your observable is the sum of two flows x that goes through S-A-R with 1 sat and y that goes through S-B-R with 2 sat.

E(x+y,O) = E(x,O) + E(y,O)

Now, x either fails (prob. 1/3) getting us 0 sat or it succeeds giving us 1 sat (prob. 2/3).

E(x,O) = 0*1/3 + 1*2/3 = 2/3

Similarly with y

E(y,O) = 0*2/5 + 2*3/5 = 6/5

Adding up to

E(x+y,O) = 2/3 + 6/5 = 28/15

But be careful, that here we are assuming that x outcome is independent of the outcome of y. This is the case if you are sending two single path payments.

Case A

If you instead consider an atomic multi-path payment in which either both x and y succeed or none will, then the two outcomes for x are again 1 sat and 0 sat, but with probabilities 2/3*3/5=2/5 (both x and y succeed) and 3/5 (all other cases) respectively:

E(x,O)= 1*2/5 + 0*3/5 = 2/5

similarly for y

E(y,O)= 2*2/5 + 0*3/5 = 4/5

Adding up to

E(x+y,O) = 2/5 + 4/5 = 6/5 = 18/15

Case D

You are building your observable as the sum of three single path flows (non-atomic): x representing 1 sat over S-A-R, y representing 1 sat over S-B-R and z representing 1 sat over S-B-R AFTER y. This is different from case B because y and z are not attached to each other, y might succeed and then z could fail.

Usual computations

E(x,O) = 0*1/3 + 1*2/3 = 2/3

for y

E(y,O) = 0*1/5 + 1*4/5 = 4/5

Then comes z, which will succeed only if there is enough liquidity for 2 sats on channel B-R, then

E(z,O) = 0*2/5 + 1*3/5= 3/5

Adding up:

E(x+y+z,O) = 2/3+4/5+3/5 = 31/15

Case C

Is similar to case D but the math is wrong. You are correctly computing E(x,O)=2/3 and E(y,O)=4/5, but with E(z,O) you are messing up with the conditional probability.

Let's see all possible outcomes:

• y fails, then also z fails, prob. 1/5, (having exactly 0 sat liquidity)
• y succeeds, but z fails, prob. 1/5, (having exactly 1 sat of liquidity)
• y succeeds, z succeeds, prob. 3/5, (all other cases which correspond to having enough liquidity for 2 sat) which is the same as the multiplication of y succeeding and the conditional prob. of z succeeding after y does (3/5 = 4/5 * 3/4).

E(z,O) = 0*1/5 + 0*1/5 + 1*3/5 = 3/5

It is important to state that z is tried after y or we get into race conditions.

Summary

• Case A is right if you send a two flow atomic payment,
• Case B is right if you send two single path payments,
• Case C is wrong,
• Case D is right if you send three single path payments.

I am confident that if you run the experiments you'll confirm.