<p>Let's review the definition of expected value.
The expected value of the random variable <code>X</code> given the state of the system <code>O</code>,
denoted as <code>E(X,O)</code> is computed as:</p>
<pre><code>E(X,O) = \sum_i p_i(O) X_i
</code></pre>
<p>The sum is over all <em>microstates</em> (all ways in which liquidity could be allocated in the channels) or equivalently one can choose to sum over all possible observable outcomes. The <code>p_i(O)</code> is the probability of verifying <code>i</code> given the state <code>O</code>, and <code>X_i</code> is the value that <code>X</code> takes if <code>i</code> is verified.
Using this definition, one immediately sees that <code>E(.,O)</code> is a linear operator:</p>
<pre><code>E(X+a*Y,O) = E(X,O) + a*E(Y,O)
</code></pre>
<p>That would be enough to answer your question.
You get different answers because you have constructed your observables differently.</p>
<h1>Case B</h1>
<p>Your observable is the sum of two flows <code>x</code> that goes through <code>S-A-R</code> with 1 sat and <code>y</code> that goes through <code>S-B-R</code> with 2 sat.</p>
<pre><code>E(x+y,O) = E(x,O) + E(y,O)
</code></pre>
<p>Now, <code>x</code> either fails (prob. 1/3) getting us 0 sat or it succeeds giving us 1 sat (prob. 2/3).</p>
<pre><code>E(x,O) = 0*1/3 + 1*2/3 = 2/3
</code></pre>
<p>Similarly with <code>y</code></p>
<pre><code>E(y,O) = 0*2/5 + 2*3/5 = 6/5
</code></pre>
<p>Adding up to</p>
<pre><code>E(x+y,O) = 2/3 + 6/5 = 28/15
</code></pre>
<p>But be careful, that here we are assuming that <code>x</code> outcome is independent of the outcome of <code>y</code>. This is the case if you are sending two single path payments.</p>
<h1>Case A</h1>
<p>If you instead consider an atomic multi-path payment in which either both <code>x</code> and <code>y</code> succeed or none will, then the two outcomes for <code>x</code> are again 1 sat and 0 sat, but with probabilities 2/3*3/5=2/5 (both <code>x</code> and <code>y</code> succeed)
and 3/5 (all other cases) respectively:</p>
<pre><code>E(x,O)= 1*2/5 + 0*3/5 = 2/5
</code></pre>
<p>similarly for <code>y</code></p>
<pre><code>E(y,O)= 2*2/5 + 0*3/5 = 4/5
</code></pre>
<p>Adding up to</p>
<pre><code>E(x+y,O) = 2/5 + 4/5 = 6/5 = 18/15
</code></pre>
<h1>Case D</h1>
<p>You are building your observable as the sum of three single path flows (non-atomic):
<code>x</code> representing 1 sat over <code>S-A-R</code>, <code>y</code> representing 1 sat over <code>S-B-R</code>
and <code>z</code> representing 1 sat over <code>S-B-R</code> AFTER <code>y</code>. This is different from case <strong>B</strong> because <code>y</code> and <code>z</code> are not attached to each other, <code>y</code> might succeed and then <code>z</code> could fail.</p>
<p>Usual computations</p>
<pre><code>E(x,O) = 0*1/3 + 1*2/3 = 2/3
</code></pre>
<p>for <code>y</code></p>
<pre><code>E(y,O) = 0*1/5 + 1*4/5 = 4/5
</code></pre>
<p>Then comes <code>z</code>, which will succeed only if there is enough liquidity for 2 sats on channel <code>B-R</code>, then</p>
<pre><code>E(z,O) = 0*2/5 + 1*3/5= 3/5
</code></pre>
<p>Adding up:</p>
<pre><code>E(x+y+z,O) = 2/3+4/5+3/5 = 31/15
</code></pre>
<h1>Case C</h1>
<p>Is similar to case <strong>D</strong> but the math is wrong.
You are correctly computing <code>E(x,O)=2/3</code> and <code>E(y,O)=4/5</code>, but with
<code>E(z,O)</code> you are messing up with the conditional probability.</p>
<p>Let's see all possible outcomes:</p>
<ul>
<li><code>y</code> fails, then also <code>z</code> fails, prob. 1/5, (having exactly 0 sat liquidity)</li>
<li><code>y</code> succeeds, but <code>z</code> fails, prob. 1/5, (having exactly 1 sat of liquidity)</li>
<li><code>y</code> succeeds, <code>z</code> succeeds, prob. 3/5, (all other cases which correspond to having enough liquidity for 2 sat)
which is the same as the multiplication of <code>y</code> succeeding and the conditional prob. of <code>z</code> succeeding after <code>y</code> does (3/5 = 4/5 * 3/4).</li>
</ul>
<pre><code>E(z,O) = 0*1/5 + 0*1/5 + 1*3/5 = 3/5
</code></pre>
<p>It is important to state that <code>z</code> is tried after <code>y</code> or we get into race conditions.</p>
<h1>Summary</h1>
<ul>
<li>Case <strong>A</strong> is right if you send a two flow atomic payment,</li>
<li>Case <strong>B</strong> is right if you send two single path payments,</li>
<li>Case <strong>C</strong> is wrong,</li>
<li>Case <strong>D</strong> is right if you send three single path payments.</li>
</ul>
<p>I am confident that if you run the experiments you'll confirm.</p>

CC BY-SA 4.0
2023-06-16T07:10:11.087Z
2023-06-16T08:02:56.533Z
2023-06-16T08:02:56.533Z
Lagrang3
<p>Look at the following network example:</p>
<p><a href="https://i.sstatic.net/36IfL.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/36IfL.png" alt="enter image description here" /></a></p>
<p>Assume <code>S</code> wants to send <code>3</code> sats to <code>R</code>. You can further assume that <code>S</code> has enough liquidity in each of its local channels to send up to <code>3</code> sats. Also assume the liquidity in channels <code>(A,R), (B,R)</code> and <code>(C,R)</code> is uniformly distributed.</p>
<p>one <a href="https://arxiv.org/abs/2107.05322" rel="nofollow noreferrer">optimally reliable payment flow</a> in this diagram looks like this:</p>
<pre><code>1 sat: S --&gt; A --&gt; R   probability: 2/3
2 sats: S --&gt; B --&gt; R  probability: 3/5
</code></pre>
<p>This flow has a total probability of <code>2/3*3/5 = 2/5 = 0.4 = 40%</code></p>
<p><strong>The question:</strong></p>
<p><strong>How to compute the expected value of Satoshis to arrive at <code>R</code> if <code>S</code> sends <code>3</code>?</strong></p>
<p><strong>Option A</strong></p>
<p>(which I already know is wrong but I write it down because I suspect some people might have a similar first thought)</p>
<p>Initially I thought this would just be <code>3 sats * 2/5 = 6/5 sats = 1.2 sats</code> 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 <code>S--&gt;B--&gt;R</code> has a probability of <code>3/5</code> and with the reasoning of above an expectation value of <code>2 sats * 3/5 = 6/5 sats = 1.2 sats</code>. as the expected value for 1 sat along the <code>S--&gt;A--&gt;B</code> path is larger than <code>0</code> this would be a contradiction to the additivity of the expected value.</p>
<p><strong>Option B</strong></p>
<p>Starting from the above reasoning we add the expected values for the disjoint paths so:</p>
<pre><code>E[3 sats] = 1 sat * 2/3 + 2 sat * 3/5 = 10/15 sats + 18/15 sats = 28/15 sats
</code></pre>
<p><strong>Option C</strong></p>
<p>Of course the 2 satoshi path <code>S--&gt;B--&gt;R</code> does not have to be sent as one onion but could be sent as two onions with 1 sat each:</p>
<p>The first has a probability of <code>4/5</code> and the second has a conditional probability of <code>3/4</code> which is <a href="https://github.com/lightningdevkit/rust-lightning/issues/1170#issuecomment-972396747" rel="nofollow noreferrer">extensively explained at this issue</a>. 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 <code>S--&gt; B --&gt; R</code> would be computed as:</p>
<pre><code>E[2 sats] = 1 sat * 4/5 + 1 sat * 3/4 = 31/20 sats 
</code></pre>
<p>If we add the 1 sat onion from the <code>S--&gt;A--&gt;R</code> which was <code>2/3</code> sats</p>
<p>we would expect to have</p>
<pre><code>E[3 sats] = 31/20 sats + 2/3 sats = 93/60 sats + 40/60 sats = 132/60 sats = 33/15 sats
</code></pre>
<p>This is <code>5/15 sats = 1/3 sats</code> more than the answer in option B</p>
<p><strong>Option D</strong></p>
<p>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:</p>
<pre><code>E[2 sats] = 1 sat * 4/5 + 1 sat * 3/5 = 7/5 sats
</code></pre>
<p>this would result in a total expected value of:</p>
<pre><code>E[3 sats] = 2/3 sats + 7/5 sats = 10/30 sats + 21/15 sats = 31/15 sats
</code></pre>
<p><strong>Thoughts</strong></p>
<p>just for comparison here are the results</p>
<ul>
<li><strong>Option A</strong>: <code>18/15</code></li>
<li><strong>Option B</strong>: <code>28/15</code></li>
<li><strong>Option C</strong>: <code>33/15</code></li>
<li><strong>Option D</strong>: <code>31/15</code></li>
</ul>
<p>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:</p>
<ul>
<li><strong>Option C</strong>: <code>E[2 sats] = 1 sat * P(X&gt;=1) + 1 sat * P(X&gt;=2 | X &gt;= 1)</code></li>
<li><strong>Option D</strong>: <code>E[2 sats] = 1 sat * P(X&gt;=1) + 1 sat * P(X&gt;=2)</code></li>
</ul>
<p>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.</p>

<lightning-network><lightning-routing>
How to compute the expected number of sats to arrive in a probabilistic payment flow?
Rene Pickhardt
# How to compute the expected number of sats to arrive in a probabilistic payment flow?

(Asked by: username_0 on 2023-03-03)

Look at the following network example:

[![enter image description here](https://i.sstatic.net/36IfL.png)](https://i.sstatic.net/36IfL.png)

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](https://arxiv.org/abs/2107.05322) 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](https://github.com/lightningdevkit/rust-lightning/issues/1170#issuecomment-972396747). 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.

**Tags:** lightning-network, lightning-routing


---

## 1 answers

### Answer by username_1 on 2023-06-16. Score: 0

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.


---

