Re: string length question

From: Robert Israel (israel_at_math.ubc.ca)
Date: 09/21/04 

Date: 21 Sep 2004 06:53:19 GMT

In article <20040921003245.11769.00001065@mb-m29.aol.com>,
NKProductionZ <nkproductionz@aol.com> wrote:
>We have that string A can go into one of two forms
>either A --> BC and terminates or A --> ADA and D is terminal, but each of
>those A's can break up into either BC or ADA.

>what is the expected length of string A?

>the standard approach which i took fails, since i said let a be the expected
>length.
>in this case the answer would be the solution of a = .5*2 + .5(2a + 1) but this
>leads to 3/2 = 0.

It looks like you're trying to use a probability model where an A
goes into each form with probability 1/2, independent of what the
other A's do. Then if the expected length existed (as a finite number),
it would satisfy your equation. Since that equation leads to a
contradiction, the only possible conclusion is that this random variable
does not have an expected value.

Or to put it another way, let a_n be the expected length after n steps
(where in each step all the A's currently present break up). Write
a recurrence relation for a_n similar to your equation, and conclude
that a_n -> infinity as n -> infinity.

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

Relevant Pages

  • Re: Cantors diagonal proof wrong?
    ... Infinity is not an integer, ... just a string of digits, ... >possible to prove anything by contradiction. ...
    (sci.math)
  • Re: Demonstrating that 0.999... = 1
    ... > One of the attributes of a string is the number of items it contains. ... And if the word "infinity" is so clear, ... The question "Is there more reals than integers" is still hotly ... and the fact that teachers are ...
    (sci.math)
  • Re: Entropy
    ... I already said that a couple of times, but here again: If you have two such machines, then for any string A, the KC for the two machines differs at most by a constant c, independentof A. Thus, you can carry the limit of A to infinity. ... does *not* depend on the string. ... Because it doesn't change the property of KC of diverging or not diverging, and if KC diverges, it doesn't change the rate by which it diverges. ... In that case, for every universal Turing machine we find a *finite* program Y that generates the first N letters of A, and the size of this program *does not* depend on how many digits of A we asked for. ...
    (comp.compression)
  • Re: infinitely many nns = infinite nns?
    ... Dipshit: Axioms CANNOT BE "unbounded". ... What IS unbounded is THE LENGTH OF A TERM in the LANGUAGE ... NOT mean that the finite AXIOMS are "using the concept of" infinity: ... STRING IN the language is finite. ...
    (sci.logic)
  • Re: abundance of irrationals!)
    ... >>> there be an infinity larger that that of the continuum. ... >>> Each path is representable by an infinite string of zeros and ones. ... >> Oh Virgil, we've been through that already, haven't we? ... based on the idea that all countably infinite sets are equal. ...
    (sci.math)
Quantcast