The probability of failing a sequential job before a deadline.
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Suppose we have $n$ days, and a job consisting of a number of sequential stages, so that each stage takes a day. Consider following stochastic process: the day $t$ for each stage is picked randomly from natural domain, but keeping the ordering of stages. As a result we get a random sequence of naturals $t_1, t_2,...$ with conditions: $0<t_ileq n$, $i<j$ implies $t_i<t_j$. The sequence rapidly becomes dence as $t_i$ approaches to $n$, and at some point it is impossible to add new term, so the sequence terminates.
I wish to find a probability $P_n(k)$ to get a sequence of $k$ terms for fixed $n$ by described process.
I have obtained empirical PMF for the distribution, using a simple program, and it looks good. But I want to get the analytic result.
The PMF for n = 10 obtained by imitational modelling
Also I have found solution for few special cases and a recurrent expressions for the PMF:
$$P_n(1)=0,\ P_n(2)=frac1n,\ P_n(3)=frac1nH_n-1,\ P_n(k)=frac1n[P_n-1(k-1)+P_n-2(k-1)+...+P_k-2(k-1)],\ P_n(n-1)=fracn(n-1)2n!=frac1(n-2)!,\ P_n(n)=frac1n!,$$ here $H_n$ is a harmonic number.
Moreover I could find exact expression for the expected value of $k$ for given $n$: $$mathbfE(k) = H_n.$$ This distribution should be named harmonic distribution :)
I would be happy to find a complete closed form solution. Combinatorial approach didn't help, unfortunately.
probability-theory probability-distributions stochastic-processes
asked Sep 2 at 11:08
samsergey
214
add a comment |Â
up vote
2
down vote
favorite
Suppose we have $n$ days, and a job consisting of a number of sequential stages, so that each stage takes a day. Consider following stochastic process: the day $t$ for each stage is picked randomly from natural domain, but keeping the ordering of stages. As a result we get a random sequence of naturals $t_1, t_2,...$ with conditions: $0<t_ileq n$, $i<j$ implies $t_i<t_j$. The sequence rapidly becomes dence as $t_i$ approaches to $n$, and at some point it is impossible to add new term, so the sequence terminates.
I wish to find a probability $P_n(k)$ to get a sequence of $k$ terms for fixed $n$ by described process.
I have obtained empirical PMF for the distribution, using a simple program, and it looks good. But I want to get the analytic result.
The PMF for n = 10 obtained by imitational modelling
Also I have found solution for few special cases and a recurrent expressions for the PMF:
$$P_n(1)=0,\ P_n(2)=frac1n,\ P_n(3)=frac1nH_n-1,\ P_n(k)=frac1n[P_n-1(k-1)+P_n-2(k-1)+...+P_k-2(k-1)],\ P_n(n-1)=fracn(n-1)2n!=frac1(n-2)!,\ P_n(n)=frac1n!,$$ here $H_n$ is a harmonic number.
Moreover I could find exact expression for the expected value of $k$ for given $n$: $$mathbfE(k) = H_n.$$ This distribution should be named harmonic distribution :)
I would be happy to find a complete closed form solution. Combinatorial approach didn't help, unfortunately.
probability-theory probability-distributions stochastic-processes
asked Sep 2 at 11:08
samsergey
214
For me, the question is unclear. What does it mean "... fail completion of $k$ stages"? It would be a good idea to make clear which is the probability space involved, at least the space $Omega$, which is the stochastic process, which are its times, a.s.o. ...
– dan_fulea
Sep 2 at 12:51
Thanks a lot, @dan_fulea, I have refined the formulation of a problem.
– samsergey
Sep 2 at 20:58
I think I understand the question now. It's still very hard to understand; "from natural domain" is unclear (if I understand correctly, it should be something like "uniformly from the remaining days"), and the crucial aspect that the days for the stages are picked sequentially, in the order in which the stages are to be completed, is missing from the exposition and can only be guessed. (Which is too bad, because it's an interesting question.)
– joriki
Sep 2 at 20:58
"uniformly from the remaining days" -- exactly! And your guess is absolutely right.
– samsergey
Sep 2 at 21:13
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Suppose we have $n$ days, and a job consisting of a number of sequential stages, so that each stage takes a day. Consider following stochastic process: the day $t$ for each stage is picked randomly from natural domain, but keeping the ordering of stages. As a result we get a random sequence of naturals $t_1, t_2,...$ with conditions: $0<t_ileq n$, $i<j$ implies $t_i<t_j$. The sequence rapidly becomes dence as $t_i$ approaches to $n$, and at some point it is impossible to add new term, so the sequence terminates.
I wish to find a probability $P_n(k)$ to get a sequence of $k$ terms for fixed $n$ by described process.
I have obtained empirical PMF for the distribution, using a simple program, and it looks good. But I want to get the analytic result.
The PMF for n = 10 obtained by imitational modelling
Also I have found solution for few special cases and a recurrent expressions for the PMF:
$$P_n(1)=0,\ P_n(2)=frac1n,\ P_n(3)=frac1nH_n-1,\ P_n(k)=frac1n[P_n-1(k-1)+P_n-2(k-1)+...+P_k-2(k-1)],\ P_n(n-1)=fracn(n-1)2n!=frac1(n-2)!,\ P_n(n)=frac1n!,$$ here $H_n$ is a harmonic number.
Moreover I could find exact expression for the expected value of $k$ for given $n$: $$mathbfE(k) = H_n.$$ This distribution should be named harmonic distribution :)
I would be happy to find a complete closed form solution. Combinatorial approach didn't help, unfortunately.
probability-theory probability-distributions stochastic-processes
asked Sep 2 at 11:08
samsergey
214
Suppose we have $n$ days, and a job consisting of a number of sequential stages, so that each stage takes a day. Consider following stochastic process: the day $t$ for each stage is picked randomly from natural domain, but keeping the ordering of stages. As a result we get a random sequence of naturals $t_1, t_2,...$ with conditions: $0<t_ileq n$, $i<j$ implies $t_i<t_j$. The sequence rapidly becomes dence as $t_i$ approaches to $n$, and at some point it is impossible to add new term, so the sequence terminates.
I wish to find a probability $P_n(k)$ to get a sequence of $k$ terms for fixed $n$ by described process.
I have obtained empirical PMF for the distribution, using a simple program, and it looks good. But I want to get the analytic result.
The PMF for n = 10 obtained by imitational modelling
Also I have found solution for few special cases and a recurrent expressions for the PMF:
$$P_n(1)=0,\ P_n(2)=frac1n,\ P_n(3)=frac1nH_n-1,\ P_n(k)=frac1n[P_n-1(k-1)+P_n-2(k-1)+...+P_k-2(k-1)],\ P_n(n-1)=fracn(n-1)2n!=frac1(n-2)!,\ P_n(n)=frac1n!,$$ here $H_n$ is a harmonic number.
Moreover I could find exact expression for the expected value of $k$ for given $n$: $$mathbfE(k) = H_n.$$ This distribution should be named harmonic distribution :)
I would be happy to find a complete closed form solution. Combinatorial approach didn't help, unfortunately.
probability-theory probability-distributions stochastic-processes
probability-theory probability-distributions stochastic-processes
asked Sep 2 at 11:08
samsergey
214
asked Sep 2 at 11:08
samsergey
214
edited Sep 5 at 1:29
asked Sep 2 at 11:08
samsergey
214
asked Sep 2 at 11:08
samsergey
214
asked Sep 2 at 11:08
samsergey
214
214
For me, the question is unclear. What does it mean "... fail completion of $k$ stages"? It would be a good idea to make clear which is the probability space involved, at least the space $Omega$, which is the stochastic process, which are its times, a.s.o. ...
– dan_fulea
Sep 2 at 12:51
Thanks a lot, @dan_fulea, I have refined the formulation of a problem.
– samsergey
Sep 2 at 20:58
I think I understand the question now. It's still very hard to understand; "from natural domain" is unclear (if I understand correctly, it should be something like "uniformly from the remaining days"), and the crucial aspect that the days for the stages are picked sequentially, in the order in which the stages are to be completed, is missing from the exposition and can only be guessed. (Which is too bad, because it's an interesting question.)
– joriki
Sep 2 at 20:58
"uniformly from the remaining days" -- exactly! And your guess is absolutely right.
– samsergey
Sep 2 at 21:13
add a comment |Â
For me, the question is unclear. What does it mean "... fail completion of $k$ stages"? It would be a good idea to make clear which is the probability space involved, at least the space $Omega$, which is the stochastic process, which are its times, a.s.o. ...
– dan_fulea
Sep 2 at 12:51
Thanks a lot, @dan_fulea, I have refined the formulation of a problem.
– samsergey
Sep 2 at 20:58
I think I understand the question now. It's still very hard to understand; "from natural domain" is unclear (if I understand correctly, it should be something like "uniformly from the remaining days"), and the crucial aspect that the days for the stages are picked sequentially, in the order in which the stages are to be completed, is missing from the exposition and can only be guessed. (Which is too bad, because it's an interesting question.)
– joriki
Sep 2 at 20:58
"uniformly from the remaining days" -- exactly! And your guess is absolutely right.
– samsergey
Sep 2 at 21:13
For me, the question is unclear. What does it mean "... fail completion of $k$ stages"? It would be a good idea to make clear which is the probability space involved, at least the space $Omega$, which is the stochastic process, which are its times, a.s.o. ...
– dan_fulea
Sep 2 at 12:51
For me, the question is unclear. What does it mean "... fail completion of $k$ stages"? It would be a good idea to make clear which is the probability space involved, at least the space $Omega$, which is the stochastic process, which are its times, a.s.o. ...
– dan_fulea
Sep 2 at 12:51
Thanks a lot, @dan_fulea, I have refined the formulation of a problem.
– samsergey
Sep 2 at 20:58
Thanks a lot, @dan_fulea, I have refined the formulation of a problem.
– samsergey
Sep 2 at 20:58
I think I understand the question now. It's still very hard to understand; "from natural domain" is unclear (if I understand correctly, it should be something like "uniformly from the remaining days"), and the crucial aspect that the days for the stages are picked sequentially, in the order in which the stages are to be completed, is missing from the exposition and can only be guessed. (Which is too bad, because it's an interesting question.)
– joriki
Sep 2 at 20:58
I think I understand the question now. It's still very hard to understand; "from natural domain" is unclear (if I understand correctly, it should be something like "uniformly from the remaining days"), and the crucial aspect that the days for the stages are picked sequentially, in the order in which the stages are to be completed, is missing from the exposition and can only be guessed. (Which is too bad, because it's an interesting question.)
– joriki
Sep 2 at 20:58
"uniformly from the remaining days" -- exactly! And your guess is absolutely right.
– samsergey
Sep 2 at 21:13
"uniformly from the remaining days" -- exactly! And your guess is absolutely right.
– samsergey
Sep 2 at 21:13
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
It appears that I have found (almost guessed) the answer. The PMF for the length of sequences build by described process could be computed exactly in closed form using Stirling numbers of the first kind:
$$
P_n(k) = genfrac[]0ptnkfrac1n!\
E(k) = H_n\
Var(k) = H_n - H_n^(2)
$$
Even though I'm interested in a proof, especially combinatorial. It is obvious that factorial in denominator counts all possible sequences, however, what is a connection between ordered sequences and cycles, which are counted by Stirling numbers?
Does anyone know the name of this distribution?
answered Sep 5 at 6:21
samsergey
214
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
It appears that I have found (almost guessed) the answer. The PMF for the length of sequences build by described process could be computed exactly in closed form using Stirling numbers of the first kind:
$$
P_n(k) = genfrac[]0ptnkfrac1n!\
E(k) = H_n\
Var(k) = H_n - H_n^(2)
$$
Even though I'm interested in a proof, especially combinatorial. It is obvious that factorial in denominator counts all possible sequences, however, what is a connection between ordered sequences and cycles, which are counted by Stirling numbers?
Does anyone know the name of this distribution?
answered Sep 5 at 6:21
samsergey
214
add a comment |Â
up vote
1
down vote
accepted
It appears that I have found (almost guessed) the answer. The PMF for the length of sequences build by described process could be computed exactly in closed form using Stirling numbers of the first kind:
$$
P_n(k) = genfrac[]0ptnkfrac1n!\
E(k) = H_n\
Var(k) = H_n - H_n^(2)
$$
Even though I'm interested in a proof, especially combinatorial. It is obvious that factorial in denominator counts all possible sequences, however, what is a connection between ordered sequences and cycles, which are counted by Stirling numbers?
Does anyone know the name of this distribution?
answered Sep 5 at 6:21
samsergey
214
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
It appears that I have found (almost guessed) the answer. The PMF for the length of sequences build by described process could be computed exactly in closed form using Stirling numbers of the first kind:
$$
P_n(k) = genfrac[]0ptnkfrac1n!\
E(k) = H_n\
Var(k) = H_n - H_n^(2)
$$
Even though I'm interested in a proof, especially combinatorial. It is obvious that factorial in denominator counts all possible sequences, however, what is a connection between ordered sequences and cycles, which are counted by Stirling numbers?
Does anyone know the name of this distribution?
answered Sep 5 at 6:21
samsergey
214
It appears that I have found (almost guessed) the answer. The PMF for the length of sequences build by described process could be computed exactly in closed form using Stirling numbers of the first kind:
$$
P_n(k) = genfrac[]0ptnkfrac1n!\
E(k) = H_n\
Var(k) = H_n - H_n^(2)
$$
Even though I'm interested in a proof, especially combinatorial. It is obvious that factorial in denominator counts all possible sequences, however, what is a connection between ordered sequences and cycles, which are counted by Stirling numbers?
Does anyone know the name of this distribution?
answered Sep 5 at 6:21
samsergey
214
edited Sep 12 at 0:58
answered Sep 5 at 6:21
samsergey
214
answered Sep 5 at 6:21
samsergey
214
answered Sep 5 at 6:21
samsergey
214
214
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2902601%2fthe-probability-of-failing-a-sequential-job-before-a-deadline%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
For me, the question is unclear. What does it mean "... fail completion of $k$ stages"? It would be a good idea to make clear which is the probability space involved, at least the space $Omega$, which is the stochastic process, which are its times, a.s.o. ...
– dan_fulea
Sep 2 at 12:51
Thanks a lot, @dan_fulea, I have refined the formulation of a problem.
– samsergey
Sep 2 at 20:58
I think I understand the question now. It's still very hard to understand; "from natural domain" is unclear (if I understand correctly, it should be something like "uniformly from the remaining days"), and the crucial aspect that the days for the stages are picked sequentially, in the order in which the stages are to be completed, is missing from the exposition and can only be guessed. (Which is too bad, because it's an interesting question.)
– joriki
Sep 2 at 20:58
"uniformly from the remaining days" -- exactly! And your guess is absolutely right.
– samsergey
Sep 2 at 21:13