0
$\begingroup$

Thanks in advance for the help.

Suppose I have an algorithm that may terminate in one of $N$ states. This algorithm operates by running $M$ steps. Each step $m_i, i \in \mathbb{N}^+$, has a probability of succeeding that is independent of other steps. In order for the algorithm to run successfully, all steps must be completed in order where step $m_1$ must be completed before $m_2$. When running a step, the algorithm may succeed or fail at it. If it fails, it will reattempt the step. However, for the entire duration of the algorithm, it can fail no more than $X$ times for $X \in \mathbb{N}^0$. After the $X^{th}$ failure, the algorithm will terminate. If a step is successfully ran, the algorithm will move to the next step or terminate if there are none.

Here is an example with 6 states, 2 steps, and one failure: ie $N = 6$, $M = 2$, $X = 1$. To try to make this a bit clearer, I will use a graphical representation where each matrix $n_j, j \in \mathbb{N}^+$ represents a single state. Columns represent steps and rows represent attempts. Since $X = 1$, there are 2 rows: one row for the first attempt and one row that accounts for a failure. $1$ represents a success, $0$ a failure, and a blank a non attempt due to that step not being ran. Assume that $m_1 = .9$ and $m_2 = .7$ where the first column gives state $1$ (ie $m_1$) and column $2$ gives state $2$.

$$n_1 = \begin{bmatrix} 1 & 1 \\ - & - \end{bmatrix}$$

$$n_2 = \begin{bmatrix} 1 & 0 \\ - & 1 \end{bmatrix}$$

$$n_3 = \begin{bmatrix} 1 & 0 \\ - & 0 \end{bmatrix}$$

$$n_4 = \begin{bmatrix} 0 & - \\ 1 & 1 \end{bmatrix}$$

$$n_5 = \begin{bmatrix} 0 & - \\ 1 & 0 \end{bmatrix}$$

$$n_6 = \begin{bmatrix} 0 & - \\ 0 & - \end{bmatrix}$$

Note that states $n_1$, $n_2$, and $n_4$ are the successful states. I am interested in calculating the probability that the algorithm ends in one of these successful states. It is quite clear to me that the probability the algorithm ends in state 1 (ie $n_1$) with probability $.9 * .7 = .63$. Because each step is independent of one another. The answer to my question should be the summation of the probabilities of ending in a successful state, namely the probabilities of ending in either $n_1$, $n_2$, or $n_4$.

I calculate all the probabilities in the following ways where $S$ is the ending state

$$P(S = n_1) = .9 * .7 = .63$$ $$P(S = n_2) = .9 * (1 - .7) * .7 = .189$$ $$P(S = n_3) = .9 * (1 - .7) * (1 - .7) = .081$$ $$P(S = n_4) = (1 - .9) * .9 * .7 = .063$$ $$P(S = n_5) = (1 - .9) * .9 * (1 - .7) = .027$$ $$P(S = n_6) = (1 - .9) * (1 - .9) = .01$$

These sum up to $1$ which is exactly what I'm looking for. However, I am not convinced that this is correct since I made these calculations using "elementary" statistics without thinking about what theorems or properties that I am using. What is tripping me up in particular is the fact that the number of attempts that the algorithm can take in each step is dependent on the number of attempts used in the previous steps. How is this actually accounted for in the math I have done (assuming I am correct) or where have I gone wrong? Specifically, if I am right, why am I right or if I am wrong, why am I wrong?

$\endgroup$
0
$\begingroup$

The way you've written the problem, I think $X=2$ in your example (the algorithm terminates after the 2nd failure). Otherwise I think your example is correct, though things are simple because you picked a simple problem. What theorems are you expecting to use? The way you account for the history dependence is that you have a different number of terms in each product (corresponding to the number of steps the algorithm takes).

More generally, you could compute the distribution using a Markov chain where you have states that encode the history of failures into them (note that this means you'll end up with a lot of states). Specifically, you will have $X+1$ copies of each state. $s_i^x$ corresponds to the state "running step $i$ with $x$ cumulative failures in the past". The chain progresses from $s_i^x$ to $s_{i+1}^x$ with the probability step $m_i$ succeeds, and from $s_i^x$ to $s_i^{x+1}$ with the probability that $m_i$ fails. There are $I(X+1)$ terminal states, corresponding to the $I$ ways the algorithm can terminate early, and the $IX$ ways the algorithm can successfully finish.

Using this chain you can make a (large) state transition matrix, and multiply it until it converges to get the distribution over the terminal states. If you actually try to do this, be sure to use sparse representations of your transition matrix since each row and column only has two entries (but there are an exponential number of rows and columns).

$\endgroup$

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.