[Tccc] Jackson Network and Queueing Theory
Lachlan Andrew
lachlan.andrew
Tue Nov 22 21:48:46 EST 2011
Greetings Victor,
> Option 1 There is a queue with X := [P(B) = 1] and
> Y := [P(S) = 0] such that V(F, T) = T
> (meaning "if a queue is unbounded then the queue is unstable").
>
> Option 2 There is a queue with X := [P(B) = 1] and
> Y := [P(S) = 0] such that V(F, F) = T
> (meaning "if a queue is unbounded then the queue is stable").
>
> The above interpretation is the basis of your argument.
> But such an interpretation is wrong.
> The contrapositive of the implication in your option 1
> is "if a queue is stable then the queue is bounded",
> which is the result you have been arguing against.
> As shown in our response below, your option 2 leads
> to a contradiction. This is why we consider your argument
> incorrect
To show the flaw, it is enough to show that either option 1 or option
2 is possible. I will now show that both are.
Option 1.
Part of the problem with your argument against option 1 is with the
implicit quantifiers. I'm arguing against the claim that " *for all*
queues, if the queue is unbounded then it is unstable", (or the
contrapositive formulation "for all queues, if the queue is stable
then it is bounded"). I'm not arguing that there is no queue such
that, if it is unbounded then it is unstable.
Also, the English paraphrase you gave changes the definition of V.
What you did was negate the hypothesis of the implication, just
because it is being evaluated for a value that is false. That means
you changed the logical statement.
The correct logical paraphrase for option 1 is
"if a queue is bounded (which it isn't) then the queue is unstable",
which says nothing about what happens if the queue is unbounded.
If we have an M/M/1 queue A with rho > 1, then that particular queue
satisfies option 1. I claim it is unbounded, and unstable, so we get
" P(B) = 1 implies P(S) = 0"
<=> V(A is bounded, A is unstable)
<=> V(F,T)
<=> T
If we accept that the probabilities are both either 0 or 1, then the
contrapositive of this is
"P(S) != 0 implies P(B) != 1"
<=> V(A is stable, A is unbounded)
<=> V(F,T)
<=> T
Option 2.
Consider this time an M/M/1 queue C with rho < 1. Then I claim it is
unbounded and stable, so we get
"P(B)=1 implies P(S)=0"
<=> V(C is bounded, C is unstable)
<=> V(F,F) (* see below)
<=> T
The contrapositive is again
V(C is stable, C is unbounded)
<=> V(T,T)
<=> T
Again, the correct paraphrase doesn't say what happens if C is
unbounded. It is
"If C is bounded (which it isn't) then C is unstable (which it isn't)"
The contrapositive of this is
"If C is stable (which it is) then C is unbounded (which it is)".
This is not a contradiction (even though not all stable queues have
unbounded delay).
First, the apparent contradiction only arises because your paraphrase
has a different logical meaning from the original statement. Second,
there is actually no contradiction to the (logical) statement "if the
queue is unstable then the queue is bounded" in this case, because the
queue is not in fact unstable. That statement is simply V(F,F)
(although the propositions are different from the one at (*) above,
because your paraphrase simply negated both the hypothesis and
conclusion of the implication).
The third part of your email is again confusing the concepts of
logical implication and sufficient conditions. It is impossible to
"prove" V(T,T)=T, because that is simply the definition of the
"implication" operator in logic. I don't have the text you mentioned,
and so can't comment on that specifically.
Remember the difference between the logical statement "X implies Y"
and the English statement "X is a sufficient condition for Y"; if X
is false then the former is always true even if the latter is not.
Being unbounded need not a sufficient condition for being unstable,
just because there exists a queue that is unbounded and unstable.
I'm not sure what you mean when you say that my "understanding of V(F,
T) = V(F, F) = T appears to be incorrect". These are definitions, not
concepts. If you mean that my understanding of implication is
incorrect, then please tell me what is wrong with it. I have pointed
out several places where our usage seems to differ, but I believe that
my usage is standard.
Now consider the issue of notation. You wrote:
>>> Does this mean that you are using the queue specified
>>> in c) as a counterexample to
>>> V(T, F) = F where X : = [P(B) = 1], Y: = [P(S) = 0]?
>>
>> No. Re-read what you wrote. The expression "V(T, F) = F where X :
>> = [P(B) = 1], Y: = [P(S) = 0]" is not useful, because X and Y are
>> never used.
>
> Why do you say so? The use of X and Y is clear as shown
> by X : = [P(B) = 1], Y: = [P(S) = 0] , and with V(T, F) = F
> it is clear X = T and Y = F.
It is clear that you are *intending* to write X=T and Y=F.
However, you have *defined* X to be a propositional statement, which
can be false. Either you are *assuming* X=T, or *redefining* X=T. It
is not clear which, which makes discussion hard. If you are assuming
it, then your proof is flawed because what you are trying to prove is
that X=T (see "Thus P(B)=1" on line 3 of page 5). If you are
redefining X=T, then your proof is flawed the second definition is
inconsistent with the first one when (P(B)=1) is false.
At the risk of getting distracted, here is an analogous example.
Assume I want to show that "Your argument is valid implies your
conclusion is valid" is false. We have agreed that this can be
written:
V(your argument is valid, your conclusion is valid)=F.
You claim that this can be rewritten
V(T,F)=F
X := "your argument is valid" and Y := "your conclusion is valid".
We have agreed that V(T,F)=F, and so (if we allowed to rewrite things
this way) the claim has been proven.
If you think "but you are assuming my conclusion is not valid", then
you may see my point. We can't define a propositional variable to be
the truth of a particular statement, and then arbitrarily assume it
has a particular value.
--
Lachlan Andrew? Centre for Advanced Internet Architectures (CAIA)
Swinburne University of Technology, Melbourne, Australia
<http://caia.swin.edu.au/cv/landrew>
Ph +61 3 9214 4837
More information about the TCCC
mailing list