Probability Question - forumla for F(x)=P(X&lt;x)

Original post by ghostwalker

You should note that each term corresponds to a non-zero

x_i

.

Study the pattern.

Don't want to say any more than that - have a think.

Right so just to clarify are the

x_i

such that

x = 0.x_1x_2x_3...x_n

?? Or does each

x_i

have its own binary expansion and so

x = x_1 + x_2 + ... + x_n

? I am not completely sure about this.

(edited 10 years ago)

Reply 22

Original post by hmark101

Right so just to clarify are the

x_i

such that

x = 0.x_1x_2x_3...x_n

Yes, they're the digits in the binary representation of x.

(edited 10 years ago)

Reply 23

Original post by ghostwalker

Yes, they're the digits in the binary representation of x.

Ok thanks. But can the

x_i

be any number between 0 and 9? Or only 0 or 1? For example, consider x = 0.0004882815. Clearly any number starting with '0.0003' is less than x, but how would you calculate the probablitly of getting 0.0003 (specifically the 3)?

Reply 24

Original post by hmark101

Ok thanks. But can the

x_i

If you look back at the original question, you'll see the representation has to be in binary, and it must be a terminating binary.

0.125, would be 0.001 in binary

0.0003 has no terminating binary representation.

Just as 1/3 in decimal = 0.3333.... has no terminating decimal representation.

You're only interested in values of x which do have a terminating binary representation.

Reply 25

Original post by ghostwalker

Right. Sorry can you tell me exactly how you convert decimals into binary representations?

Also, the question says x is the summation of x_i/2^i - however from before the x_i are the digits in the binary representation of x, so what is the summation about?? Sorry again - I can't seem to understand this!

Reply 26

Original post by hmark101

Right. Sorry can you tell me exactly how you convert decimals into binary representations?

It's not relevant to the question. I'd search for "number bases" and fractions on the internet if you wish to learn about it.

Also, the question says x is the summation of x_i/2^i - however from before the x_i are the digits in the binary representation of x, so what is the summation about?? Sorry again - I can't seem to understand this!

Again it's not relevant to the question. I'd search for "numbers" and "place value" if you want to investigate it.

You're told everything you need regarding the expansion in the question.

PS: I would investigate it, as you really ought to know about this.

(edited 10 years ago)

Reply 27

DFranklin

Original post by hmark101

Right. Sorry can you tell me exactly how you convert decimals into binary representations?To convert x (between 0 and 1) into binary.

Your binary representation starts with "0.".

Repeat (indefinitely) the following algorithm:


    Multiply x by 2.
    If x >= 1:
        add a "1" at the end of your representation and subtract 1 from x.
    otherwise:
       add a "0" to the end of your representation.

(Obviously, if at some stage x = 0, you can terminate, because x will be 0 at every subsequent stage).

Reply 28

Original post by ghostwalker

...

Sorry for the late reply in getting back to you - had some mock exams.

On to the question, lets consider n=1. If x = x_1 / 2, to calculate P(X <= x) we have, in this case x = 0 or x = 1/2, so we need to calculate P(X <= 0) and P(X <= 1/2). Is this right?

What then would P(X <= 0.5) be? This is where I am having difficulty understanding. It's any number starting with 0,0, 0.1,..,0.4. But what's the probablity of these?

Following on we calculate P(X <= x) when x = x_1 / 2 + x_2 / 4 (so n = 2)? So we need to calculate P(X <= 0), P(X <= 1/2), P(X <= 1/4) and P(X <= 3/4). Etc.

Reply 29

Original post by hmark101

0.5 in binary is 0.1, so, X1 = 1

By our previous working F(0.5) = P(X1= 0), and this is the probability that our binary representation starts with 0.0

Reply 30

Original post by ghostwalker

0.5 in binary is 0.1, so, X1 = 1

By our previous working F(0.5) = P(X1= 0), and this is the probability that our binary representation starts with 0.0

Ok, I see, so for n=1, F(x) = q.

For n=2, P(X <= x) = x_1 / 2 + x_2 / 4. So we need to calculate P(X <= 0), P(X <= 1/2), P(X <= 1/4) and P(X <= 3/4).

P(X <= 1/2) = F(0.5). 0.5 in binary is 0.1, so we need any number starting with 0.0 i.e. prob = q.

P(X <= 1/4) = F(0.25). 0.25 in binary is 0, so this is just 0.

P(X <= 3/4) = F(0.75). 0.75 in binary is 0.11, so we need any number starting with: '0.0', '0.10' i.e. prob = q, pq respectively.

So for n=2, F(x) = q + q + qp = 2q + pq. Is this all right?

(edited 10 years ago)

Reply 31

Original post by hmark101

...

F(x) is a function of x, it is not one specific value for all x, or even for a specific n.

F(0.5) = q, not F(x)=q (other than to say this is true when x=0.5 ).

Given the representation of x in the binary form

0.x_1x_2\ldots x_n

what is F(x)?

Perhaps it would be clearer to ask what is

\operatorname{F}(0.x_1x_2\ldots x_n)

where

0.x_1x_2\ldots x_n

is the binary representation of x. Your final answer is going to be a function of

x_1,x_2,\ldots,x_n,n

You do not add up all the values for a given n, rather you use the method we used with x = 0.10011001 - you just need to formalise that to cover all cases.

(edited 10 years ago)

Reply 32

Original post by ghostwalker

0.x_1x_2\ldots x_n

what is F(x)?

Perhaps it would be clearer to ask what is

\operatorname{F}(0.x_1x_2\ldots x_n)

where

0.x_1x_2\ldots x_n

is the binary representation of x. Your final answer is going to be a function of

x_1,x_2,\ldots,x_n,n

You do not add up all the values for a given n, rather you use the method we used with x = 0.10011001 - you just need to formalise that to cover all cases.

Right I understand. But then how would we generalise it and cover all cases? And again you mentioned

0.x_1x_2\ldots x_n

is the binary representation of x but what about the

2^i

i.e x_1/2, x_2/4 etc? We know that each x_i can only be 0 or 1 right? So do we just consider each case? Surely thats too many cases to consider. I may be being stupid but I really can't see how to do this question and its so fustrating!

A push in the right direction of actually solving for F(x) would be much appreciated. Thanks for the help so far.

Reply 33

Original post by hmark101

Right I understand. But then how would we generalise it and cover all cases?

That's what you need to work out.

And again you mentioned

0.x_1x_2\ldots x_n

is the binary representation of x but what about the

2^i

i.e x_1/2, x_2/4 etc?

It's only relevant in working out the binary representation of x, and you don't really need that here. It's taken as read for this question - see the original question.

We know that each x_i can only be 0 or 1 right? So do we just consider each case? Surely thats too many cases to consider. I may be being stupid but I really can't see how to do this question and its so fustrating!

A push in the right direction of actually solving for F(x) would be much appreciated. Thanks for the help so far.

I don't know what else to suggest other than what I already have.

Particularly pay attention to the working for x = 0.10011001

Try a few more cases yourself perhaps, but the hint to generalising has already been spelt out in this thread, in relation to the x = 0.10011001 example.

Reply 34

Ah yes, I've had trouble with this question for ages aswell.

Original post by ghostwalker

...

Can you explain how to find F(x), and what the formula for F(x) is?? I understand the x = 0.10011001 example fully, but have no idea how to generalise. Many thanks.

Reply 35

Original post by fkhan100

Ah yes, I've had trouble with this question for ages aswell.

Can you explain how to find F(x), and what the formula for F(x) is?? I understand the x = 0.10011001 example fully, but have no idea how to generalise. Many thanks.

See post #21. I can't think of anything else to say without actually doing it.

Reply 36

Original post by ghostwalker

See post #21. I can't think of anything else to say without actually doing it.

Ok thanks. What do you mean by "each term corresponds to a non-zero x_i" - which term are you referring to?

Reply 37

Original post by fkhan100

Ok thanks. What do you mean by "each term corresponds to a non-zero x_i" - which term are you referring to?

The terms in F(x), quoted in the same post!

Reply 38

Original post by ghostwalker

The terms in F(x), quoted in the same post!

Ok so basically we have F(x) = F(0.x_1x_2...x_n). Each x_i can be zero or one, right?

So if x_1 = 1 ---> F(x) = P(X<=x) = the set of all binary numbers starting with '0.0', and that has probability q.

So the x_1 term in the forumla for F(x) is (q(x_1)). Is that the right approach?

Reply 39