Subject: [bmwg] Help with draft-ietf-bmwg-hash-stuffing-05, 5.2.1. Calculating Bit-Stuffing Probability

From: "Jerry Perser" <[email-masked]>
Date: Mon, 14 Aug 2006 16:09:15 -0700

Could you expand on how a transition matrix works in section 5.2.1?  I'm not
a probability expert, but I keep getting a different answer than stated.

I am using Boolean logic to work out the probability.  Looking at the
diagram, I see 5 decisions between start and state 5.  It's not clear if the
bit stuffing happens in state 5 or after state 5.  Could this be clarified?
Each decision represents a bit.  So we have either 5 or 6 bits that get
stuffed to 6 or 7 bits.  I'll assume 6 bits because it's closer to the
drafts solution.

With 6 bits there are 64 possible combinations (2 ** 6).  It appears that
only one combination creates the bit stuffing, which is 111111.  So the
solution I come up with every time is 1 out of 64 or 1/64.  I have no idea
how to get 1/62.

Please help me.

Jerry Perser
Veriwave
Main :  818-338-4000
Direct: 818-338-4112
Fax:    818-338-4005

_______________________________________________
bmwg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/bmwg

---

From: "Player, Timmons" <[email-masked]>
Date: Tue, 15 Aug 2006 04:43:08 -1000

> -----Original Message-----
> From: Jerry Perser [mailto:[email-masked]] 
> Sent: Monday, August 14, 2006 7:09 PM
> To: [email-masked]
> Subject: [bmwg] Help with 
> draft-ietf-bmwg-hash-stuffing-05,5.2.1. Calculating 
> Bit-Stuffing Probability
> 
> Could you expand on how a transition matrix works in section 
> 5.2.1?  I'm not a probability expert, but I keep getting a 
> different answer than stated.
>
Sure.  However, others people's examples would probably be
better.  Please check out the following links for
explanations of "Markov chains."

http://mathworld.wolfram.com/MarkovChain.html
http://en.wikipedia.org/wiki/Examples_of_Markov_chains

> I am using Boolean logic to work out the probability.  
> Looking at the diagram, I see 5 decisions between start and 
> state 5.  It's not clear if the bit stuffing happens in state 
> 5 or after state 5.  Could this be clarified?
> Each decision represents a bit.  So we have either 5 or 6 
> bits that get stuffed to 6 or 7 bits.  I'll assume 6 bits 
> because it's closer to the drafts solution.
> 
The draft states that a bit is stuffed if and only if state 5 is
reached,
hence if you reach state 5, then a bit is stuffed.

And also hence, 5 bits are stuffed into 6 bits.

> With 6 bits there are 64 possible combinations (2 ** 6).  It 
> appears that only one combination creates the bit stuffing, 
> which is 111111.  So the solution I come up with every time 
> is 1 out of 64 or 1/64.  I have no idea how to get 1/62.
> 
> Please help me.

I think that there is some confusion here.  A stuff occurs after FIVE
sequential
1's bits.  A 6 bit string can be stuffed in three ways:  011111, 111110,
and
111111.  So, your 6 bit string should represent a probability of 3/64.

Additionally, the section you are referring to is determining the
probability
for an infinitely long bit string, not a fixed length bit string.  Exact
expectations
are given by the formula in section 5.2.2

And if we use it for your 6 bit case, we get f(6) = 2^(1) + 1 * 2^0 = 3.

Timmons

<DIV><FONT size="1">

E-mail confidentiality.
--------------------------------
This e-mail contains confidential and / or privileged information belonging to Spirent Communications plc, its affiliates and / or subsidiaries. If you are not the intended recipient, you are hereby notified that any disclosure, copying, distribution and / or the taking of any action based upon reliance on the contents of this transmission is strictly forbidden. If you have received this message in error please notify the sender by return e-mail and delete it from your system. If you require assistance, please contact our IT department at [email-masked].

Spirent Communications plc,
Spirent House, Crawley Business Quarter, Fleming Way, Crawley, West Sussex, RH10 9QL, United Kingdom.
Tel No. +44 (0) 1293 767676
Fax No. +44 (0) 1293 767677

Registered in England Number 470893
Registered at Spirent House, Crawley Business Quarter, Fleming Way, Crawley, West Sussex, RH10 9QL, United Kingdom 

Or if within the US,

Spirent Communications,
26750 Agoura Road, Calabasas, CA, 91302, USA.
Tel No. 1-818-676- 2300 

</FONT></DIV>