[Tccc] Jackson Network and Queueing Theory
Lachlan Andrew
lachlan.andrew
Thu Nov 24 14:43:46 EST 2011
Greetings Victor,
I assume you are talking about example 1. This is consistent with my
understanding of implication. I'll explain in detail below. First
let me clarify something:
I'm *not* arguing that the statement "bounded implies unstable" is
true in general. That seems to be what you assume I am saying. That
would be saying "For all queues, V(X,Y) = T", which is what is
generally meant when someone says "X implies Y".
Instead, I am pointing out that the flow your logic is "(for all
queues, V(X,Y)=T) is false, therefore (for all queues, V(X,Y)=F) is
true". (Correct me if I'm wrong.) That statement isn't true. The
correct logic is "(for all queues, V(X,Y)=T) is false, therefore (for
some queues, V(X,Y)=F) is true". (See again the fourth relation at
<http://en.wikipedia.org/w/index.php?title=Quantification&oldid=457601452#Equivalent_Expressions>.)
What I am saying is there also exist some queues Q for which V(X
restricted to Q,Y restricted to Q)=T, simply because X(restricted to
Q) is false.
For an analogy of why quantifiers are important, consider the
implication (B): "If A is odd then A is prime". That is not true in
general, but if it is restricted to 2 <= A <= 7 then it is true. That
means we can't say "(For all A, (B) is true) is false, therefore (for
all A, (B) is false) is true". There exists some A's (like some Q's)
for which (B) is true. In particular, it is true for A=2 ((F,T),
analogous to an unstable M/M/1) and A=4 ((F,F), analogous to a stable
M/M/1).
Now consider the example in the book.
The implication is "(m is divisible by 6) implies (m is divisible by 2)"
To paraphrase your "option 1" and "option 2" for this example, we get:
>> Option 1 There is a queue with X := [m is divisible by 6] and
>> Y := [m is divisible by 2] such that V(F, T) = T
>> (meaning "if m is indivisible by 6 then the m is divisible by 2").
(Recall that you negated the "if" part, just because we are
considering a case where the "if" part is false.)
Now clearly, for m=4, we get V(X,Y) = V(F,T) = T, but we don't get
the statement "(For all m) if m is indivisible by 6 then m is
divisible by 2".
Similarly
>> Option 2 There is a queue with X := [m is divisible by 6] and
>> Y := [m is indivisible by 2] such that V(F, F) = T
>> (meaning "if m is indivisible by 6 then m is indivisible by 2").
Clearly, for m=1 we get V(X,Y) = V(F,F) = 1, but we don't get the
statement "(For all m), if m is indivisible by 6 then m is indivisible
by 2".
My claim is that an unstable and a stable M/M/1 queue are analogous to
m=4 and m=1 (respectively).
The analogy isn't perfect, because the example given in the book is an
implication which is true *for all* m.
Again, if you think I am mistaken, please tell me what error you think
I am making. Statements such as "contradicts the intended meaning of"
aren't very precise. I'm stubborn enough to keep this up for weeks,
but progress will be much faster if you point out flaws in my
argument, instead of just saying "your argument is flawed".
On 24 November 2011 21:46, Prof. Victor Li <vli at eee.hku.hk> wrote:
> Dear Lachlan,
>
> The key issue to be resolved in this discussion is the meaning
> of V(F, T) = V(F, F) = T. Your understanding of V(F, T) = V(F, F) = T
> contradicts the intended meaning of V(F, T) = V(F, F) = T
> given by logicians. So your use of V(F, T) = V(F, F) = T
> contradicts the intended use of V(F, T) = V(F, F) = T in mathematics. For
> your convenience, we have attached a copy of the page from the book
> mentioned in our previous e-mail. The example given on
> that page illustrates clearly the intended use of V(F, T) = V(F, F) = T
> according to its
> intended meaning given by logicians. Hopefully the example will convince you
> that neither your understanding nor your use of V(F, T) = V(F, F) = T is
> correct.
> Best Regards,
>
> Guang-Liang and Victor
>
>
> -----Original Message----- From: Lachlan Andrew Sent: Wednesday, November
> 23, 2011 10:48 AM To: Prof. Victor Li Cc: tccc at lists.cs.columbia.edu
> Subject: Re: [Tccc] Jackson Network and Queueing Theory
> 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
>
> _______________________________________________
> IEEE Communications Society Tech. Committee on Computer Communications
> (TCCC) - for discussions on computer networking and communication.
> Tccc at lists.cs.columbia.edu
> https://lists.cs.columbia.edu/cucslists/listinfo/tccc
--
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