Logarithmic Probability

If you pick a number x x uniformly at random on the interval [ 0 , 1 ] , [0,1], what is the probability that log 2 1 x \left\lfloor \log _{2}\frac{1}{x}\right\rfloor is odd, to 3 significant figures?

Note: \lfloor \cdot \rfloor is the floor function .


The answer is 0.333.

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.

8 solutions

Calvin Osborne
Jan 21, 2018

We can find the solution to this problem if we identify important "turning points" in the expression log 2 1 x \big\lfloor \log _{2}\frac{1}{x}\big\rfloor for specific values of x.

x = 1 x = 1 : log 2 ( 1 1 ) = log 2 1 = 0 \log _{2}(\frac{1}{1}) = \log _{2}1 = 0

x = 1 2 x = \frac{1}{2} : log 2 ( 1 1 2 ) = log 2 2 = 1 \log _{2}(\frac{1}{\frac{1}{2}}) = \log _{2}2 = 1

x = 1 4 x = \frac{1}{4} : log 2 ( 1 1 4 ) = log 2 4 = 2 \log _{2}(\frac{1}{\frac{1}{4}}) = \log _{2}4 = 2

x = 1 8 x = \frac{1}{8} : log 2 ( 1 1 8 ) = log 2 8 = 3 \log _{2}(\frac{1}{\frac{1}{8}}) = \log _{2}8 = 3

x = 1 16 x = \frac{1}{16} : log 2 ( 1 1 16 ) = log 2 16 = 4 \log _{2}(\frac{1}{\frac{1}{16}}) = \log _{2}16 = 4

x = 1 32 x = \frac{1}{32} : log 2 ( 1 1 32 ) = log 2 32 = 5 \log _{2}(\frac{1}{\frac{1}{32}}) = \log _{2}32 = 5

. . . ...

So, for values of x x where 1 x > 1 2 1 \geq x > \frac{1}{2} , log 2 1 x = 0 \big\lfloor \log _{2}\frac{1}{x}\big\rfloor = 0 , which is even.

For values of x x where 1 2 x > 1 4 \frac{1}{2} \geq x > \frac{1}{4} , log 2 1 x = 1 \big\lfloor \log _{2}\frac{1}{x}\big\rfloor = 1 , which is odd.

For values of x x where 1 4 x > 1 8 \frac{1}{4} \geq x > \frac{1}{8} , log 2 1 x = 2 \big\lfloor \log _{2}\frac{1}{x}\big\rfloor = 2 , which is even.

For values of x x where 1 8 x > 1 16 \frac{1}{8} \geq x > \frac{1}{16} , log 2 1 x = 3 \big\lfloor \log _{2}\frac{1}{x}\big\rfloor = 3 , which is odd.

For values of x x where 1 16 x > 1 32 \frac{1}{16} \geq x > \frac{1}{32} , log 2 1 x = 4 \big\lfloor \log _{2}\frac{1}{x}\big\rfloor = 4 , which is even.

. . . ...

Therefore, the values for which log 2 1 x \big\lfloor \log _{2}\frac{1}{x}\big\rfloor is even is 1 2 + 1 8 + 1 32 . . . = n = 1 1 2 2 n 1 = n = 1 2 4 n \frac{1}{2} + \frac{1}{8} + \frac{1}{32} ... = \displaystyle\sum_{n=1}^{\infty} \frac{1}{2^{2n - 1}} = \displaystyle\sum_{n=1}^{\infty} \frac{2}{4^{n}}

The values for which for which log 2 1 x \big\lfloor \log _{2}\frac{1}{x}\big\rfloor is odd is 1 4 + 1 16 + 1 64 . . . = n = 1 1 2 2 n = n = 1 1 4 n \frac{1}{4} + \frac{1}{16} + \frac{1}{64} ... = \displaystyle\sum_{n=1}^{\infty} \frac{1}{2^{2n}} = \displaystyle\sum_{n=1}^{\infty} \frac{1}{4^{n}}

We can evaluate the infinite sum for which log 2 1 x \big\lfloor \log _{2}\frac{1}{x}\big\rfloor is odd by using the formula ( a ) + ( a × r ) + ( a × r 2 ) + ( a × r 3 ) . . . = a 1 r (a) + (a \times r) + (a \times r^{2}) + (a \times r^{3})... = \frac{a}{1 - r} (as a side note, this formula only works when r < 1 |r| < 1 ). The sum for odd numbers can be rewritten as ( 1 4 ) + ( 1 4 × 1 4 ) + ( 1 4 × ( 1 4 ) 2 ) + ( 1 4 × ( 1 4 ) 3 ) . . . = 1 4 1 1 4 = 1 4 3 4 = 4 3 × 4 = 1 3 (\frac{1}{4}) + (\frac{1}{4} \times \frac{1}{4}) + (\frac{1}{4} \times (\frac{1}{4})^{2}) + (\frac{1}{4} \times (\frac{1}{4})^{3})... = \frac{\frac{1}{4}}{1 - \frac{1}{4}} = \frac{\frac{1}{4}}{\frac{3}{4}} = \frac{4}{3 \times 4} = \boldsymbol{\frac{1}{3}}

Equivalently, if you write x x in binary expansion it looks like a random sequence of 0s and 1s. The question is then the probability of x 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).

Antoine G - 3 years, 4 months ago

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.

David Richner - 3 years, 4 months ago

Nice question and solution.

David Richner - 3 years, 4 months ago

Nice! I used Desmos first and then discovered a pattern quite similar to yours.

Toby M - 3 years, 4 months ago

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.

Vikas Rv - 3 years, 4 months ago

i discovered the same pattern gr8 question !!

Dhairy Agrawal - 3 years, 4 months ago

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.

Андрей Фасалов - 3 years, 4 months ago
Arjen Vreugdenhil
Jan 29, 2018

Let f ( x ) = log 2 1 x . f(x) = \lfloor \log_2 \frac 1x \rfloor. Then:

  • If x > 1 2 x > \tfrac12 , then 0 log 2 1 x < 1 0 \leq \log_2 \frac 1x < 1 so that f ( x ) = 0 f(x) = 0 is even.

  • If x 1 2 x \leq \tfrac 12 , f ( x ) = f ( 2 x ) + 1 f(x) = f(2x) + 1 , so that f ( x ) f(x) has the opposite parity of f ( 2 x ) f(2x) .

Therefore, P ( f ( x ) is odd ) = P ( x 1 2 and f ( 2 x ) is even ) = 1 2 ( 1 P ( f ( x ) is odd ) ) ; \mathbb P (f(x)\ \text{is odd}) = \mathbb P\big(x \leq \tfrac12\ \text{and}\ f(2x)\ \text{is even}\big) = \tfrac12\big(1 - \mathbb P (f(x')\ \text{is odd})\big); this is a simple linear equation P = 1 2 ( 1 P ) P = \tfrac12(1 - P) , with solution P = P ( f ( x ) is odd ) = 1 / 3 0.333 . P = \mathbb P (f(x)\ \text{is odd}) = \boxed{1/3 \approx 0.333}.


Generalization for arbitrary base b > 1 b > 1 :

If you pick a number x x randomly (and uniformly distributed) on [ 0 , 1 ] [0,1] , the probability that log b 1 x \lfloor \log_b \frac 1 x \rfloor is odd is equal to P = 1 1 + b . P = \frac 1{1 + b}. The reasoning is similar: Let f ( x ) = log b 1 x . f(x) = \lfloor \log_b \frac 1x \rfloor. Then:

  • If x > 1 b x > \tfrac1b , then 0 log b 1 x < 1 0 \leq \log_b \frac 1x < 1 so that f ( x ) = 0 f(x) = 0 is even.

  • If x 1 b x \leq \tfrac 1b , f ( x ) = f ( b x ) + 1 f(x) = f(bx) + 1 , so that f ( x ) f(x) has the opposite parity of f ( b x ) f(bx) .

Therefore, P ( f ( x ) is odd ) = P ( x 1 b and f ( b x ) is even ) = 1 b ( 1 P ( f ( x ) is odd ) ) ; \mathbb P (f(x)\ \text{is odd}) = \mathbb P\big(x \leq \tfrac1b\ \text{and}\ f(bx)\ \text{is even}\big) = \tfrac1b\big(1 - \mathbb P (f(x')\ \text{is odd})\big); this is a simple linear equation P = 1 b ( 1 P ) P = \tfrac1b(1 - P) , or b P = 1 P bP = 1 - P , with solution P = P ( f ( x ) is odd ) = 1 1 + b . P = \mathbb P (f(x)\ \text{is odd}) = \frac{1}{1+b}.

superb solution

Tousif Ahmad - 3 years, 4 months ago

Shit!!!! I did the same but for base e

Arijit Dey - 3 years, 4 months ago

Log in to reply

In that case, the answer is 1/(e+1).

Arjen Vreugdenhil - 3 years, 4 months ago

it came as e/e+1

Arijit Dey - 3 years, 4 months ago

I don’t understand after “opposite parity” can you explain? Please

alperen taş - 3 years, 4 months ago

Log in to reply

Opposite parity = one is odd, the other is even.

Arjen Vreugdenhil - 3 years, 4 months ago

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?

n sb - 3 years, 4 months ago
Andrea Ghizzi
Jan 29, 2018

We are looking for the measure of the preimage of the set

[ 1 , 2 ) [ 3 , 4 ) [ 5 , 6 ) . . . . [1,2) \bigcup [3,4) \bigcup [5,6)....

via log 2 1 x \log_{2}\frac{1}{x} . Representing x in binary we must have that

x ( 0.0 1 2 , 0. 1 2 ] ( 0.000 1 2 , 0.00 1 2 ] ( 0.00000 1 2 , 0.0000 1 2 ] . . . . . x \in (0.01_{2},0.1_{2}] \bigcup (0.0001_{2},0.001_{2} ] \bigcup ( 0.000001_{2},0.00001_{2}].....

Adding the lengths of the intervals we get the probability

P = 0.0 1 2 + 0.000 1 2 + 0.00000 1 2 + . . . = 0.010101.. . 2 P = 0.01_{2} + 0.0001_{2} + 0.000001_{2} + ... = 0.010101..._{2}

Now 3 P = P + 2 P = 0.010101.. . 2 + 0.101010.. . 2 = 0.111111.. . 2 = 1 3P = P + 2P = 0.010101..._{2} + 0.101010..._{2} = 0.111111..._{2} = 1

So P = 1 3 P=\frac{1}{3}

Hamana Hamana
Jan 29, 2018

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.

G D
Feb 1, 2018

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
Jeremy Galvagni
Feb 4, 2018

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 1/4 + 1/4^2 + 1/4^3 + 1/4^4 + 1/4^5 \dots which converges to 1 / 3 1/3 .

Meeharbi N
Feb 1, 2018

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.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...