If you pick a number x uniformly at random on the interval [ 0 , 1 ] , what is the probability that ⌊ lo g 2 x 1 ⌋ is odd, to 3 significant figures?
Note: ⌊ ⋅ ⌋ is the floor function .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Equivalently, if you write x in binary expansion it looks like a random sequence of 0s and 1s. The question is then the probability of x beginning with an odd number of 0s. This is the probability of getting an odd number of heads before getting a tail (on a fair coin).
Log in to reply
I thought along these lines (with the coin flipping and similar problems like the Brilliant lemonade pouring problem from some years ago) also.
Nice question and solution.
For x = 1/2 , 1/8 .... the given log(1/x) is odd. Not even. Isnt it ? Log(1/1/2) to the base 2 is 1 which is odd.
i discovered the same pattern gr8 question !!
For the last step you may assume that Sum for evens = 2 * Sum for odds, and sum of these Sums is 1, and you don't need to count Sum for odds through geometric progression.
Let f ( x ) = ⌊ lo g 2 x 1 ⌋ . Then:
If x > 2 1 , then 0 ≤ lo g 2 x 1 < 1 so that f ( x ) = 0 is even.
If x ≤ 2 1 , f ( x ) = f ( 2 x ) + 1 , so that f ( x ) has the opposite parity of f ( 2 x ) .
Therefore, P ( f ( x ) is odd ) = P ( x ≤ 2 1 and f ( 2 x ) is even ) = 2 1 ( 1 − P ( f ( x ′ ) is odd ) ) ; this is a simple linear equation P = 2 1 ( 1 − P ) , with solution P = P ( f ( x ) is odd ) = 1 / 3 ≈ 0 . 3 3 3 .
Generalization for arbitrary base b > 1 :
If you pick a number x randomly (and uniformly distributed) on [ 0 , 1 ] , the probability that ⌊ lo g b x 1 ⌋ is odd is equal to P = 1 + b 1 . The reasoning is similar: Let f ( x ) = ⌊ lo g b x 1 ⌋ . Then:
If x > b 1 , then 0 ≤ lo g b x 1 < 1 so that f ( x ) = 0 is even.
If x ≤ b 1 , f ( x ) = f ( b x ) + 1 , so that f ( x ) has the opposite parity of f ( b x ) .
Therefore, P ( f ( x ) is odd ) = P ( x ≤ b 1 and f ( b x ) is even ) = b 1 ( 1 − P ( f ( x ′ ) is odd ) ) ; this is a simple linear equation P = b 1 ( 1 − P ) , or b P = 1 − P , with solution P = P ( f ( x ) is odd ) = 1 + b 1 .
superb solution
Shit!!!! I did the same but for base e
it came as e/e+1
I don’t understand after “opposite parity” can you explain? Please
Log in to reply
Opposite parity = one is odd, the other is even.
Can you elaborate on the equality you conclude the linear equation from?
Doesn't the second equality only hold in case A=(x<=1/b) and B=(f(bx) is even) are indepentent events? Which they aren't in this case?
We are looking for the measure of the preimage of the set
[ 1 , 2 ) ⋃ [ 3 , 4 ) ⋃ [ 5 , 6 ) . . . .
via lo g 2 x 1 . Representing x in binary we must have that
x ∈ ( 0 . 0 1 2 , 0 . 1 2 ] ⋃ ( 0 . 0 0 0 1 2 , 0 . 0 0 1 2 ] ⋃ ( 0 . 0 0 0 0 0 1 2 , 0 . 0 0 0 0 1 2 ] . . . . .
Adding the lengths of the intervals we get the probability
P = 0 . 0 1 2 + 0 . 0 0 0 1 2 + 0 . 0 0 0 0 0 1 2 + . . . = 0 . 0 1 0 1 0 1 . . . 2
Now 3 P = P + 2 P = 0 . 0 1 0 1 0 1 . . . 2 + 0 . 1 0 1 0 1 0 . . . 2 = 0 . 1 1 1 1 1 1 . . . 2 = 1
So P = 3 1
Log base 2 of 1/x can be rewritten as -log base 2 of x.
Graphing -log base 2 of x yields segments of length (1 - 1/2) at y=0, segment of (1/2-1/4) at y=1, (1/4-1/8) at y=2, etc.
The function that gives the segment’s length at y=n is given by 2^{-n-1}
The probability of y being odd is the same as the sum of the segments at n being odd;
This turns into the infinite sum of 4^{-n}, 1/4 + 1/16 + 1/64....
which simplifies to 1/3, or 0.333.
Matlab Solution:
q=10000; %sqrt of number of experiments to perform
r = rand(q); %gen matrix of rand numbers
r = r(:); %make into vector for easy processing
x= floor(log(1./r)./log(2)); %apply function
odd = mod(x,2); %find odd vals of output
sum(odd)/q^2 %find p
ans = 0.3334
f(x)=floor(lg(1/x))
From 1/2 to 1 the function is 0: even
From 1/4 to 1/2 the function is 1: odd
From 1/8 to 1/4 the function is 2: even
From 1/16 to 1/8 the function is 3: odd etc
Each even interval has a corresponding odd interval which is half as wide, so overall the P(even)=2*P(odd)
P(even) = 2/3
P(odd) = 1/3
The approach which I followed is very naive I guess!
I plotted the graph of the function using maxima,
Looking at the plot we can easily come up with this series for the probability of odd number being chosen:
1 / 4 + 1 / 4 2 + 1 / 4 3 + 1 / 4 4 + 1 / 4 5 … which converges to 1 / 3 .
import java.util.*; public class Program{
public static void main(String[] args) {
double count=0, countodd=0, counteven=0;
double X;
for(int counter= 1; counter <=10000000; counter++ ){
X = Math.random();
double y = (Math.log(1/X))/(Math.log(2));
double z = Math.floor(y);
count= count+1;
if(z%2==0){
counteven= counteven+1;
}
else{
countodd=countodd+1;
}
}
System.out.println((countodd/count));
}
}
For the logs, I could only find log base 10, so I used change of base formula. I used mod 2 to find if the integer was even or not.
Problem Loading...
Note Loading...
Set Loading...
We can find the solution to this problem if we identify important "turning points" in the expression ⌊ lo g 2 x 1 ⌋ for specific values of x.
x = 1 : lo g 2 ( 1 1 ) = lo g 2 1 = 0
x = 2 1 : lo g 2 ( 2 1 1 ) = lo g 2 2 = 1
x = 4 1 : lo g 2 ( 4 1 1 ) = lo g 2 4 = 2
x = 8 1 : lo g 2 ( 8 1 1 ) = lo g 2 8 = 3
x = 1 6 1 : lo g 2 ( 1 6 1 1 ) = lo g 2 1 6 = 4
x = 3 2 1 : lo g 2 ( 3 2 1 1 ) = lo g 2 3 2 = 5
. . .
So, for values of x where 1 ≥ x > 2 1 , ⌊ lo g 2 x 1 ⌋ = 0 , which is even.
For values of x where 2 1 ≥ x > 4 1 , ⌊ lo g 2 x 1 ⌋ = 1 , which is odd.
For values of x where 4 1 ≥ x > 8 1 , ⌊ lo g 2 x 1 ⌋ = 2 , which is even.
For values of x where 8 1 ≥ x > 1 6 1 , ⌊ lo g 2 x 1 ⌋ = 3 , which is odd.
For values of x where 1 6 1 ≥ x > 3 2 1 , ⌊ lo g 2 x 1 ⌋ = 4 , which is even.
. . .
Therefore, the values for which ⌊ lo g 2 x 1 ⌋ is even is 2 1 + 8 1 + 3 2 1 . . . = n = 1 ∑ ∞ 2 2 n − 1 1 = n = 1 ∑ ∞ 4 n 2
The values for which for which ⌊ lo g 2 x 1 ⌋ is odd is 4 1 + 1 6 1 + 6 4 1 . . . = n = 1 ∑ ∞ 2 2 n 1 = n = 1 ∑ ∞ 4 n 1
We can evaluate the infinite sum for which ⌊ lo g 2 x 1 ⌋ is odd by using the formula ( a ) + ( a × r ) + ( a × r 2 ) + ( a × r 3 ) . . . = 1 − r a (as a side note, this formula only works when ∣ r ∣ < 1 ). The sum for odd numbers can be rewritten as ( 4 1 ) + ( 4 1 × 4 1 ) + ( 4 1 × ( 4 1 ) 2 ) + ( 4 1 × ( 4 1 ) 3 ) . . . = 1 − 4 1 4 1 = 4 3 4 1 = 3 × 4 4 = 3 1