Probability of 0 bit in ASCII text files

Click For Summary

Discussion Overview

The discussion revolves around the probability of drawing a 0 bit from ASCII text files, particularly focusing on the implications of the Most Significant Bit (MSB) being 0. Participants explore the probability of drawing a second 0 bit given that the first drawn bit was 0, considering various assumptions about independence and replacement in the drawing process.

Discussion Character

  • Exploratory
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • Some participants assert that the MSB is always 0, leading to a higher probability of drawing 0s compared to 1s.
  • One participant questions whether the draws are independent and whether they are with or without replacement.
  • Another participant argues that the first draw provides information about the file, affecting the probability of subsequent draws.
  • There is a proposal that the probability of drawing a 0 bit can be calculated using Bayes' theorem, leading to a value of 9/16 for the overall probability of drawing a 0.
  • Some participants discuss the implications of drawing without replacement, suggesting that the first draw influences the second draw's probability.
  • There is a calculation presented for the probability of the first bit being an MSB given that it was a 0, leading to a value of 2/9.
  • Several participants express confusion over the calculations and the reasoning behind the probabilities, particularly regarding the elimination of possibilities after drawing a 0.
  • One participant mentions that if the file is large, the effect of replacement may be negligible, while for smaller files, the first draw significantly impacts the second.
  • There are discussions about the statistical distribution of characters in English text, although some participants clarify that the initial assumptions state that bits are equally likely except for the MSB.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the exact probability of drawing a second 0 given the first was 0. There are competing views on the independence of draws, the impact of the MSB, and the correct application of probability formulas.

Contextual Notes

Participants express uncertainty regarding the assumptions made about the distribution of bits and the implications of drawing with or without replacement. There are unresolved questions about the correct interpretation of probabilities and the calculations involved.

Who May Find This Useful

This discussion may be of interest to those studying probability theory, information theory, or anyone involved in data encoding and compression, particularly in the context of ASCII text files.

  • #31
haruspex said:
How do you get that? Should be 3/8*1/2*1/2 + 5/8*1/2*1/2*1/2 = 11/64

No, 13/256

You are right. Thanks.
Please let me confirm about the "1/2".
1st.
Analysis: The number of "1/2 " at the right part (of +) is 2^-(N-1), and left is 2^-N.
right? but Where the " number of 1/2 " comes from? Is that because of the N that is number of successive zero bits taken from ASCII?
2nd.
If N>8, then we should assume it is impossible. In other words, the answer should be 0. Am I correct?
 
Last edited:
Physics news on Phys.org
  • #32
Cylab said:
Where the " number of 1/2 " comes from? Is that because of the N that is number of successive zero bits taken from ASCII?
Yes. If N ≤ 8, one of the N might be a leading bit, but only one.
With probability N/8, there is a leading bit. That bit will be 0. The other N-1 may be 0 or 1, equally likely. So prob that all N are 0 is 2-(N-1).
With prob 1-N/8, there is no leading bit. All N may be 0 or 1, equally likely. So prob that all N are 0 is 2-N.
Adding up: (N/8)*2-(N-1) + (1-N/8)*2-N = 2-N(1+N/8).
If N>8, then we should assume it is impossible. In other words, the answer should be 0.
Not at all. You are now guaranteed one leading 0, and the question becomes whether there's 1 or 2. In general, if we write N = 8A+B, B < 8, what do you think the formula would be?
 
  • #33
haruspex said:
Adding up: (N/8)*2-(N-1) + (1-N/8)*2-N = 2-N(1+N/8).

Thanks. the explanations are really helpful.
So in other words,
「We can assume that there are seven bits (or N<8) and that there is at most one MSB bit (which means either one MSB or zero MSB) in it. Thus we can compute the probability of having zero MSB, plus the probability of having one MSB. right ?」


haruspex said:
Not at all. You are now guaranteed one leading 0, and the question becomes whether there's 1 or 2. In general, if we write N = 8A+B, B < 8, what do you think the formula would be?

Analysis:
1st. as the same token, If we let N be 15bits , then the it must contain at least one MSB or at most two MSBs. We add the probability of having one MSB and having two MSBs in it.
2nd. further, when N is 37 bits, then it must contain at least four or at most five MSBs. And so on ...
So what it turns out to be? Just replacing N with 8A+B seems not sufficient for the computations, unless I understand what 'A', 'B' stand for.
Will you furnish some explanations further please?
 
  • #34
Cylab said:
1st. as the same token, If we let N be 15bits , then the it must contain at least one MSB or at most two MSBs. We add the probability of having one MSB and having two MSBs in it.
How about you complete that and post the formula you get?
2nd. further, when N is 37 bits, then it must contain at least four or at most five MSBs. And so on ...
So what it turns out to be? Just replacing N with 8A+B seems not sufficient for the computations, unless I understand what 'A', 'B' stand for.
A and B are integers, 0 ≤ B < 8, N=8A+B. That completely defines A and B. A = integer part of N/8; B = N modulo 8.
 
  • #35
haruspex said:
How about you complete that and post the formula you get?

A and B are integers, 0 ≤ B < 8, N=8A+B. That completely defines A and B. A = integer part of N/8; B = N modulo 8.

OK! But the analysis concentrates on MSB only (say, N=7); so the formula maybe like;
P(MSB)=P(MSB |H0)P(H0) + P(MSB |H1)P(H1)
(Let Hi be the event that there are i MSB bits in N, for i = 0, 1, 2, 3….. )
where P(MSB |H0) stands for conditional probability of MSB bit in N given it is H0 which equals 0 (no MSB) and P(MSB |H1) stands for conditional probability of MSB bit in the N given it is H1 which equals 1/7 (one MSB);

But it is little different from the point of N=8A+B. right?
I could not figure out the computation.
 
  • #36
Cylab said:
the analysis concentrates on MSB only (say, N=7); so the formula maybe like;
P(MSB)=P(MSB |H0)P(H0) + P(MSB |H1)P(H1)
(Let Hi be the event that there are i MSB bits in N, for i = 0, 1, 2, 3….. )
where P(MSB |H0) stands for conditional probability of MSB bit in N given it is H0 which equals 0 (no MSB) and P(MSB |H1) stands for conditional probability of MSB bit in the N given it is H1 which equals 1/7 (one MSB);
That's all true, but I'm not sure where it gets you. What are you trying to solve here?
Are we done with the N≤8 case?
 
  • #37
haruspex said:
That's all true, but I'm not sure where it gets you. What are you trying to solve here?
Are we done with the N≤8 case?

How about investigation of N > 8 case?
Just can`t quiet figure out how N=8A+B works.
 
  • #38
Cylab said:
How about investigation of N > 8 case?
Just can`t quiet figure out how N=8A+B works.
N=8A+B, B<8, means there are A whole bytes and B odd bits, so either A or A+1 MSBs included.
See what gaps you can fill in here:
Prob that this includes A+1 MSB's = ...?; if A+1 MSBs, prob that all N bits are 0 is ...?
Prob that this includes A MSB's = ...?; if A MSBs, prob that all N bits are 0 is ...?
Adding this up, prob that all N bits are 0 is ...?
 
  • #39
haruspex said:
N=8A+B, B<8, means there are A whole bytes and B odd bits, so either A or A+1 MSBs included.
See what gaps you can fill in here:
Prob that this includes A+1 MSB's = ...?; if A+1 MSBs, prob that all N bits are 0 is ...?
Prob that this includes A MSB's = ...?; if A MSBs, prob that all N bits are 0 is ...?
Adding this up, prob that all N bits are 0 is ...?

haruspex said:
if A+1 MSBs, prob that all N bits are 0 is ...?
That is not easy for me Sir.
Analysis: Since the N bits are drawn consecutively from ASCII, there is only 1 character (out of 2^256), which is are all 0. So only 1 MSB. Thus, the Prob =1/2^256.
Others seem to follow the conception , or I misunderstood your point?

Question:
1) Pr[0] in ASCII (assume each character appears with same ratio) equals = 1/8+1/2=5/8. Is it OK?
2) Successive 7 bits are drawn at random from ASCII bits (e.g. no bias of character distribution), what is Pr[0] in the 7 bits?
Successive 4 bits are drawn (same condition with above), what is Pr[0] in the 4 bits?
So, say, Successive N bits are drawn (same condition) , what is Pr[0] in the N bits?
Analysis:
Do you think it is same case? remember you explained that N/8*2^-N + (1-N/8)*2^-(N+1) . Does the formula apply to the case of 2).

Shed some lights on please.
 
  • #40
Cylab said:
Analysis: Since the N bits are drawn consecutively from ASCII, there is only 1 character (out of 2^256), which is are all 0. So only 1 MSB. Thus, the Prob =1/2^256.
The N bits might start in the middle of one byte, span several whole bytes, and finish part way through the last. For each whole byte, prob of all zeroes is 1/128 (since MSB always zero).
If the N bits include A MSBs then how many non-MSBs do they include?
What is the prob that the A MSBs are all 0?
What is the prob that the non-MSBs are all 0?
So what is the prob that all N bits are 0?
Question:
1) Pr[0] in ASCII (assume each character appears with same ratio) equals = 1/8+1/2=5/8. Is it OK?
No. 1/8 that bit is MSB, so 7/8 that it is non-MSB. P[0] = 1/8 + 7/8*1/2 = 9/16. We went through that much earlier in the thread.
2) Successive 7 bits are drawn at random from ASCII bits (e.g. no bias of character distribution), what is Pr[0] in the 7 bits?
Successive 4 bits are drawn (same condition with above), what is Pr[0] in the 4 bits?
So, say, Successive N bits are drawn (same condition) , what is Pr[0] in the N bits?
Analysis:
Do you think it is same case? remember you explained that N/8*2^-N + (1-N/8)*2^-(N+1) . Does the formula apply to the case of 2).
I believe you are misquoting the formula. In post #27 I explained that the prob of N consecutive 0 bits (N≤8) is 2-N(1+N/8).
 
  • #41
haruspex said:
I believe you are misquoting the formula. In post #27 I explained that the prob of N consecutive 0 bits (N≤8) is 2-N(1+N/8).

That is right and it was good explanation.
Now, say, two N consecutive bits are taken (or two groups) (N1=7, and N2=4).
So the prob is different in following cases in comparing of same amount of 0`s?
1st case: (in N1=7) Pr[0], Pr[00],..,Pr[0000] =?
2nd case: (in N2=4) Pr[0], Pr[00],..,Pr[0000] =?
 
  • #42
Cylab said:
1st case: (in N1=7) Pr[0], Pr[00],..,Pr[0000] =?
2nd case: (in N2=4) Pr[0], Pr[00],..,Pr[0000] =?
I don't understand your question. What does Pr[0] mean in the context of N1=7? Is it the probability that the next bit is zero given the preceding 7 were?
 
  • #43
haruspex said:
I don't understand your question. What does Pr[0] mean in the context of N1=7? Is it the probability that the next bit is zero given the preceding 7 were?

Sorry!
I meant the prob of 0 within N1 =7 consecutively drawn from ASCII .
In other words, say, now we have a group of bits consists of many N1, each of which is consecutive 7 bits drawn from ASCII. what is Prob[0], Prob[00] in the group respectively?

2nd case. another group of bits with same condition, where N2=4. What is Prob[0], Prob[00] within the second group respectively?

Is (N1)Prob[0] = (N2)Prob[0] right, or should it be unequal?
 
Last edited:
  • #44
Cylab said:
Is (N1)Prob[0] = (N2)Prob[0] right,
Of course. The bits don't know how many others were chosen.
 
  • #45
haruspex said:
Of course. The bits don't know how many others were chosen.

So you are saying following are correct?

(N1=7)Prob[0] = (N2=4)Prob[0]
(N1=7)Prob[00] = (N2=4)Prob[00]
(N1=7)Prob[000] = (N2=4)Prob[000]
...
 
  • #46
To be completely clear:
If you choose N consecutive bits, the probability that the first R of those bits are all zero (R <= N), depends only on R. It cannot depend on N.
Further, if you choose N consecutive bits, then choose R consecutive bits from those N, the probability that the first R of those bits are all zero depends only on R.
(This seems so obvious that I worry that I have not understood the question.)
 
  • #47
haruspex said:
To be completely clear:
If you choose N consecutive bits, the probability that the first R of those bits are all zero (R <= N), depends only on R. It cannot depend on N.
Further, if you choose N consecutive bits, then choose R consecutive bits from those N, the probability that the first R of those bits are all zero depends only on R.
(This seems so obvious that I worry that I have not understood the question.)

case: N1=7 & N2=4 . Assume N is taken from X bits, which is ASCII.
take R=2 bits from N1 & N2 respectively, what is prob that they are two 0 bits.

1st. (N1 case) : {(9X/16)C2 * (7X/16)C5 } / xC7.
1st. (N2 case) : {(9X/16)C2 * (7X/16)C2 } / xC4.

Seems it depends on N too.
 
Last edited:
  • #48
Cylab said:
1st. (N1 case) : {(9X/16)C2 * (7X/16)C5 } / xC7.
I have no idea what that notation means.
 
  • #49
haruspex said:
I have no idea what that notation means.

Hypergeometric Distribution.

X: number of ASCII bits , from which N is taken.
Pr[0] = 9/16.

xC7 : The number of combinations of x , taken 7 at a time.
 
  • #50
Cylab said:
Hypergeometric Distribution.

X: number of ASCII bits , from which N is taken.
Pr[0] = 9/16.

xC7 : The number of combinations of x , taken 7 at a time.

So how do I read (9X/16)C2? If I plug in X=7, that gives (63/16)C2, which is meaningless.
 
  • #51
haruspex said:
So how do I read (9X/16)C2? If I plug in X=7, that gives (63/16)C2, which is meaningless.

C: combinations
Pr[0] = 9/16.
X: number of ASCII bits , from which N is taken.
case: N1=7 & N2=4 . Assume N is taken from X bits, which is ASCII.
Other definitions should be clear
 
  • #52
Cylab said:
C: combinations
Pr[0] = 9/16.
X: number of ASCII bits , from which N is taken.
case: N1=7 & N2=4 . Assume N is taken from X bits, which is ASCII.
Other definitions should be clear
You wrote (9X/16)C2, and you have still offered no reasonable explanation for that notation. Did you mean (9/16)XC2?
 
  • #53
haruspex said:
You wrote (9X/16)C2, and you have still offered no reasonable explanation for that notation. Did you mean (9/16)XC2?

X: The number of bits in ASCII.
9X/16: The number of 0 bits in the X that are classified as successes.
7 or 4: The number(s) of bits taken consecutively from X.
2: The number of 2 zeros in the 7 or 4 that are classified as successes.
(9X/16)C2 : The number of combinations of 9X/16, taken two 0 bits at a time.
 
  • #54
Cylab said:
X: The number of bits in ASCII.
9X/16: The number of 0 bits in the X that are classified as successes.
7 or 4: The number(s) of bits taken consecutively from X.
2: The number of 2 zeros in the 7 or 4 that are classified as successes.
(9X/16)C2 : The number of combinations of 9X/16, taken two 0 bits at a time.
Now that you have explained that, thankyou, I can see where it is wrong.
For one thing, that analysis treats all bits as independently 0 or 1, regardless of their proximity to each other. Bits multiples of 8 positions apart will be positively correlated, and at other distances negatively correlated.
More significantly, let's look at what these represent:
1st. (N1 case) : {(9X/16)C2 * (7X/16)C5 } / xC7.
1st. (N2 case) : {(9X/16)C2 * (7X/16)C2 } / xC4.
The first is the probability of picking 7 bits that are exactly two 0 bits and 5 1 bits; the second is the prob of picking 4 bits that are exactly 2 and 2. No wonder they're different! In the problem I thought we were discussing, P[00] doesn't care what the remaining 2 or 5 bits are.
 
  • #55
haruspex said:
Now that you have explained that, thankyou, I can see where it is wrong.
For one thing, that analysis treats all bits as independently 0 or 1, regardless of their proximity to each other. Bits multiples of 8 positions apart will be positively correlated, and at other distances negatively correlated.
More significantly, let's look at what these represent:
1st. (N1 case) : {(9X/16)C2 * (7X/16)C5 } / xC7.
1st. (N2 case) : {(9X/16)C2 * (7X/16)C2 } / xC4.
The first is the probability of picking 7 bits that are exactly two 0 bits and 5 1 bits; the second is the prob of picking 4 bits that are exactly 2 and 2. No wonder they're different! In the problem I thought we were discussing, P[00] doesn't care what the remaining 2 or 5 bits are.

You are right!
P[00] doesn't care what the remaining 2 or 5 bits are.
So does the calculation in the following two cases, which are the prob of P[00] taken from N1 and N2 respectively regardless of the contents of the N1 & N2.
1st. (N1 case) : {(9X/16)C2 * (7X/16)C5 } / xC7.
1st. (N2 case) : {(9X/16)C2 * (7X/16)C2 } / xC4.
 
  • #56
Cylab said:
So does the calculation in the following two cases, which are the prob of P[00] taken from N1 and N2 respectively regardless of the contents of the N1 & N2.
1st. (N1 case) : {(9X/16)C2 * (7X/16)C5 } / xC7.
1st. (N2 case) : {(9X/16)C2 * (7X/16)C2 } / xC4.
Once again, I'm not at all sure what you are saying. Are you insisting that the above formulae are correct for P[00]? I have just explained to you why they are not.
 
  • #57
haruspex said:
Once again, I'm not at all sure what you are saying. Are you insisting that the above formulae are correct for P[00]? I have just explained to you why they are not.

Just focusing your points.

Following link may help you clarify your analysis mentioned so far.
http://en.wikipedia.org/wiki/Hypergeometric_distribution
 

Similar threads

Graduate What Is the Probability of 0 in ASCII Bit Strings?
  • · Replies 7 ·
Replies
7
Views
3K
Undergrad Understanding extinction probability in simple GWP
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Building a better ranking system (probability)
  • · Replies 1 ·
Replies
1
Views
1K
Undergrad Calculating Probability of Drawing Card Combos: A Closer Look at Counting
  • · Replies 9 ·
Replies
9
Views
3K
MHB Find the probability of being same
  • · Replies 1 ·
Replies
1
Views
2K
High School Death Rally: an intricate probability problem?
  • · Replies 8 ·
Replies
8
Views
3K
Computing conditional extinction probabilities for pollen cells
  • · Replies 1 ·
Replies
1
Views
1K
Undergrad Taking socks out of drawers, conditional probability
  • · Replies 36 ·
2
Replies
36
Views
5K
Undergrad How Can I Calculate the Probability in a Multi-Level Box System?
  • · Replies 2 ·
Replies
2
Views
2K
Graduate A game of seemingly mutually independent events
  • · Replies 7 ·
Replies
7
Views
2K