Expectation/probability question (sorta like Craps, maybe?)

[montalbon]

I'll try to be as brief as possible:

I have a number of events that can happen, say e1, e2...eN. N isn't particularly large. Each event has a probability of "failure", p1, p2...pN (Actually, there will likely be an overall failure rate, that will be converted to a weighted probability based on some properties of the eN -- namely their size -- but that's probably not that important).

You can assume, the probabilities are independent. Failing at one point doesn't impact the failure at another point (again, this will be modeled in the overall failure rate.)

Upon a "failure", you have to start from the beginning, and incur a cost, c1, c2...cN, for failing on e1, e2...eN etc.

The entire process has a fixed cost for completion, C.

So let's say you have only two events, e1 and e2, and the you didn't fail on the first even, but did on the second (and then didn't fail on the first and second after the retry, obviously), your cost wold be c2 + C

If you failed on the third event, and then after retry, again failed on the first, your cost would be c3 + c1 + C.

And so on...

My questions is this: What would be the closed form solution for the expectation on the cost of this system, for a large number of trials?

I thought maybe it was E=p1(c1+E)+p2(c2+E)+⋯+pN(cN+E), but that doesn't seem right. Can anyone give me some pointers?

(I mentioned the craps thing because it was the closed analogue I could think of. Sort of how in this instance, you have to keep going until you reach the "end" without failing, and in craps it's sort of the reverse: you keep going until you fail. Okay, maybe it's not all that related).

Thanks!

 

[BGM]

I think the process can be described by a markov chain with the following transition matrix:


\(
\begin{bmatrix}
p_1 & 1 - p_1 & 0 & 0 & \ldots & 0 & 0\\
p_2 & 0 & 1 - p_2 & 0 & \ldots & 0 & 0\\
p_3 & 0 & 0 & 1 - p_3 & \ldots & 0 & 0\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
p_{N-1} & 0 & 0 & 0 & \ldots & 1 - p_{N-1} & 0 \\
p_N & 0 & 0 & 0 & \ldots & 0 & 1 - p_N \\
0 & 0 & 0 & 0 & \ldots & 0 & 1
\end{bmatrix}
\)

with the transition cost \( c_i \) for the transitions from state \( i \) to state \( 1 \), \( i = 1, 2, \ldots, n \) and
\( C \) for the transition from state \( N \) to the absorbing state.

So the question now is to calculate the expected cost until absorption.

Denote \( E_i \) be the expected cost until absorption, given now at state \( i \), \( i = 1, 2, \ldots, n \)

By the Markov property you may establish the following system of equations:

\( E_i = p_i(c_i + E_1) + (1 - p_i)E_{i+1}, i = 1, 2, \ldots, N - 1 \)
\( E_N = p_N(c_N + E_1) + (1 - p_N)C \)

Solving the system should give you \( E_1 \). Of course you can express this compactly as a product of an inverse of matrix with some vectors.

 

[montalbon]

I think the process can be described by a markov chain with the following transition matrix:


\(
\begin{bmatrix}
p_1 & 1 - p_1 & 0 & 0 & \ldots & 0 & 0\\
p_2 & 0 & 1 - p_2 & 0 & \ldots & 0 & 0\\
p_3 & 0 & 0 & 1 - p_3 & \ldots & 0 & 0\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
p_{N-1} & 0 & 0 & 0 & \ldots & 1 - p_{N-1} & 0 \\
p_N & 0 & 0 & 0 & \ldots & 0 & 1 - p_N \\
0 & 0 & 0 & 0 & \ldots & 0 & 1
\end{bmatrix}
\)

with the transition cost \( c_i \) for the transitions from state \( i \) to state \( 1 \), \( i = 1, 2, \ldots, n \) and
\( C \) for the transition from state \( N \) to the absorbing state.

So the question now is to calculate the expected cost until absorption.

Denote \( E_i \) be the expected cost until absorption, given now at state \( i \), \( i = 1, 2, \ldots, n \)

By the Markov property you may establish the following system of equations:

\( E_i = p_i(c_i + E_1) + (1 - p_i)E_{i+1}, i = 1, 2, \ldots, N - 1 \)
\( E_N = p_N(c_N + E_1) + (1 - p_N)C \)

Solving the system should give you \( E_1 \). Of course you can express this compactly as a product of an inverse of matrix with some vectors.

Okay, two things:

1). I'm not sure why in the first Ei term, it's pi(ci+E1). Should that be pi(ci+Ei)?

2). This is MUCH more complicated than I thought. I thought perhaps there was a tidy closed-form solution. I've run through a number of examples in simulation, and I can't seem to detect any simple patterns (even with, say, 2 events and probabilities like .5 and .75 and costs like 4 and 8).

Either way, thank you VERY much for responding. I didn't realize it was so complicated, as I said. Until I can plug in some numbers and see how the values change (and perhaps understand why they're changing) I'll probably stick with getting these numbers experimentally.

I think. Any last clarifying ideas? Either way, thanks again!

 

[BGM]

1. If your system reduce to 1 event only, then actually the time to complete is just a geometric random variable and in this case the closed form solution is obvious.

2. The subscript of the notation I used \( E_i \) represent the current state - i.e. imagine the next event to happen is the \( i \)th event. And you want to ask what is the expected cost until completion (i.e. absorption of markov chain)

3. The system is basically a simple first step analysis (or generally the law of total probability which I think you know as you can write down something similar). For example at the \( i \)th event, you can either failure and go back to state \( 1 \), or success and go to the next event \( i + 1 \).

4. The linear system have a special form and maybe have some nice closed form solution (sorry I am not good at linear algebra). For a 2 event case, it is a simple 2 by 2 system:

\( E_1 = p_1(c_1 + E_1) + (1 - p_1)E_2 \)
\( E_2 = p_2(c_2 + E_1) + (1 - p_2)C \)

Putting \( p_1 = 0.5, p_2 = 0.75, c_1 = 4, c_2 = 8 \)

and you shall obtain \( E_1 = C + 40, E_2 = C + 36 \)

 

[montalbon]

1. If your system reduce to 1 event only, then actually the time to complete is just a geometric random variable and in this case the closed form solution is obvious.

2. The subscript of the notation I used \( E_i \) represent the current state - i.e. imagine the next event to happen is the \( i \)th event. And you want to ask what is the expected cost until completion (i.e. absorption of markov chain)

3. The system is basically a simple first step analysis (or generally the law of total probability which I think you know as you can write down something similar). For example at the \( i \)th event, you can either failure and go back to state \( 1 \), or success and go to the next event \( i + 1 \).

4. The linear system have a special form and maybe have some nice closed form solution (sorry I am not good at linear algebra). For a 2 event case, it is a simple 2 by 2 system:

\( E_1 = p_1(c_1 + E_1) + (1 - p_1)E_2 \)
\( E_2 = p_2(c_2 + E_1) + (1 - p_2)C \)

Putting \( p_1 = 0.5, p_2 = 0.75, c_1 = 4, c_2 = 8 \)

and you shall obtain \( E_1 = C + 40, E_2 = C + 36 \)

I ran some experiments, and the "final answer" for p1 = .5, p2 = .75 (that is, the probability of an error is 75%), with c1 = 4 and c2 = 8 is 40.

That's reassuring! I can't remember if I got that number algebraically, since I think I threw that piece of scratch paper away, but it sounds right. I know algebraically you get something like E1 = E2 + 4, or E2 = 36. When I run these experiments, and I sum up (over all the trials) the "cost" of the first and second events (divided by the total number of trials), I get about 16 due to errors in the first event, and 24 due to errors in the second event.

So, those numbers sum to 40 (which is good!) and seem to signify the average cost contribution of the two events. Which means I'm probably mistaking what E2 is, since I thought it was "the expected cost of event 2" (which, seems to be 24, as I mentioned above).

I'll have to think more about this!

 

[BGM]

As I have explained before, \( E_2 \) is the expected cost of the whole process given that the next event to happen is event 2.