8
$\begingroup$

Your gambling friend has come to stay with you and offers to play a game with you as many times as you wish:

  • He chooses an integer $x$ between $1$ and $9$ inclusive, and makes a wager of $\$1$ with you
  • You have a computer:
    • pick a uniformly distributed random integer, $n$, between $0$ and $10,000,000$ inclusive;
    • calculate $2^n$; and
    • return you the first decimal digit, $d$.
  • His odds will be $(x+1):1$

You need to choose if you want to play the game, but you cannot use the computer to do so, you excuse yourself to the bathroom where you do your best thinking and keep a pen and pad for such brainstorming sessions...

What is your expected value of playing this game with him if he plays the best available strategy?


Note:
The odds, $(x+1):1$, mean that:

  • To play he gives you $\$1$;
  • If $d=x$ you then give him $\$(x+2)$;
  • If $d\neq x$ you keep the $\$1$.

Adapted from minimax's original, which was slightly adapted from a problem by V. I. Arnold.

$\endgroup$
  • $\begingroup$ @GentlePurpleRain - what do you reckon is that a valid puzzle? $\endgroup$ – Jonathan Allan Jul 30 '16 at 9:43
  • $\begingroup$ @JonathanAllan It definitely reads less like a math textbook problem now, although all of the answers still read like math textbook answers. This is still fundamentally a pure mathematics problem, and not really a puzzle. $\endgroup$ – GentlePurpleRain Jul 30 '16 at 19:46
  • 1
    $\begingroup$ Should the wording really matter that much? If someone asks you "Mary has two apples. She gets two more apples. How many apples does Mary have?", that is not different at all from "what is 2+2?". In the same vein, answers that look like textbook answers can actually explain something interesting (such as the distribution described in this question, which strangely occurs all over the real world). $\endgroup$ – ffao Aug 1 '16 at 16:26
15
$\begingroup$

Here's a simple proof:

$\{\cdot\}$ denotes the fractional part.

$\log_{10}2$ is irrational, so $\{n\log_{10}2\}$ is evenly distributed across $[0,1)$. The leading digit of $2^n$ is $\lfloor10^{\{n\log_{10}2\}}\rfloor$, so it is $x$ iff $\{n\log_{10}2\}$ is in the interval $[\log_{10}x,\log_{10}(x+1))$. This interval has a size of $\log_{10}\frac{x+1}x$, so this is the probability that the first digit of $2^n$ is $x$.


Edit: (Jonathan Allan) - Since this question is on hold I'll put this more expanded version here for the time being.

The basics first, logarithmic and exponentiation identities...

$$x=b^{\log_{b}(x)}\tag{1}\label{1}$$ since logarithm and power functions are inverses.


$$b^{c+d}=b^cb^d\tag{2}\label{2}$$ since multiplication is distributes over addition, i.e: $$b\times\cdots(c+d\text{ times})\cdots\times b=(b\times\cdots(c\text{ times})\cdots\times b)\times (b\times\cdots(d\text{ times})\cdots\times b)$$


$$\left(b^e\right)^f=b^{ef}\tag{3}\label{3}$$ since multiplication is distributes over multiplication, i.e: $$(b\times\cdots(e \text{ times})\cdots\times b)\times\cdots(f \text{ times})\cdots\times(b\times\cdots(e \text{ times})\cdots\times b)$$ $$=b\times\cdots(e\times f \text{ times})\cdots\times b$$


Applying a couple of these identities...

By substituting using $(1)$ for $x$: $$\log_b(x^p)=\log_b((b^{\log_{b}(x)})^p)$$ then applying $(3)$ $$\log_b(x^p)=\log_b({b^{p\log_{b}(x)}})$$ and hence $$x^p={b^{p\log_{b}(x)}}$$ which means $$2^n={10^{n\log_{10}(2)}}\tag{A}\label{A}$$


Now an excursion

...into what a written number means in terms of relevance to the puzzle...
A number in a base is an expression of sums of powers
in base $10$ we talk of units, tens, hundreds, thousands and so on (going right to left)
as such writing a number like $743$ is really expressing it in this way:
$743=7\times 100+4\times 10+3\times 1$ or
$743=7\times 10^2+4\times 10^1+3\times 10^0$
We could also move everything into the highest power of $10$:
$743=7.43\times 10^2$
Such that the number on the left of the decimal point is the leading digit and is therefore in $[1,9]$
Now we can note that $\log_b{1}=0$ and $\log_b{b}=1$ (or equivalently $b^0=1$ and $b^1=b$) so
$743=10^r10^2$ with $r\in[0,1)$, that is $r$ is between $0$ (inclusive) and $1$ (exclusive)
- for this example of $743$, $r=0.87098881376\dots$
hence
$7.43=10^r$
and
$7=\lfloor10^r\rfloor$ (the integer part of) - which is the leading digit of the number $743$.


Similarly

for the problem at hand where $n$ is a positive integer: $$2^n=10^r10^s$$ with $s\in\Bbb{N}$ (a positive integer or zero) and $r\in[0,1)$
But by $(2)$ in reverse that means $$2^n=10^{r+s}$$ So $r$ is the fractional part of $r+s$

and from $(A)$: $$r+s=n\log_{10}(2)$$ Therefore we have that the leading digit in base $10$ of $2^n$ is $$\lfloor10^{\{n\log_{10}(2)\}}\rfloor\tag{B}\label{B}$$ where $\{\cdot\}$ represents taking the fractional part.


Now

if $\log_{10}(2)$ were rational it would be expressible as $\frac tu$ with $t,u\in \Bbb{N^*}$ ($t$ and $u$ positive integers)
Furthermore since $1<2<10$ we know that (as we knew for $r$)
$$\log_{10}(2)\in[0,1)$$ so $u>t$
But\begin{align}\log_{10}(2)&=\frac tu\\\rightarrow u\log_{10}(2)&=t\\\rightarrow\log_{10}(2^u)&=t\\\rightarrow 2^u&=10^t\\\rightarrow2^u&=2^t5^t\\\rightarrow2^{u-t}&=5^t\end{align}
Which would make an even number equal an odd number, so $\log_{10}(2)$ cannot be rational
Hence $\log_{10}(2)$ is irrational.


Although

...I'm not sure of a simple proof of the equidistribution theorem but for an elementary proof see this post on MathOverflow (however, it does seem intuitive due to the ever changing landscape of decimal digits of an irrational number)

This tells us that $\{n\log_{10}(2)\}$ will be uniformly distributed (by choice of $n$) across the interval it may occupy, $[0,1)$, as $n$ gets large because $\log_{10}(2)$ is irrational.


Finally

... by $(B)$ the chance of a leading digit of $2^n$ being $d$ is the chance of $\lfloor10^{\{n\log_{10}(2)\}}\rfloor$ being $d$

...and if $$d=\lfloor10^{\{n\log_{10}(2)\}}\rfloor$$ then $$d\leq 10^{\{n\log_{10}(2)\}} < d + 1$$ so (since logarithm and power functions are inverses) $$\log_{10}(d)\leq \{n\log_{10}(2)\} < log_{10}(d + 1)$$ Which neatly splits up the range $[0,1)$ (since $\log_{10}(1)=0$ and $\log_{10}(10)=1$)

Leaving the chance of a leading digit of $2^n$ being $d$ being the fraction of the range $[0,1)$ occupied by the range $[\log_{10}(d),\log_{10}(d+1))$

Thus the probability of a leading digit being $d$ is $$P(d)=(\log_{10}(d+1)-\log_{10}(d))/(1-0)$$ which by the inverse of $(2)$ means $$P(d)=\log_{10}(\frac{d+1}d)\space\space\space\space\Box$$


To answer the gambling question

Your friend's best strategy is to pick $d$ such that his expected value$$\$(d+2)P(d)-1$$ is maximised, which is the same as maximising $$(d+2)P(d)=(d+2)\log_{10}(\frac{d+1}d)=\log_{10}({\frac{d+1}d}^{d+2})$$which is the same as maximising$$\frac{d+1}{d}^{d+2}={(1+\frac 1d)^{d+2}}=1+\frac 1d^{d+2}=1+d^{-d-2}$$which decreases as $d$ increases, so he should pick $d=1$, whereupon his expected value is$$\$(1+2)P(1)-1=\$3\log_{10}(2)-1=\$\log_{10}(2^3)-1=\$\log_{10}(8)-1$$Since $$x<b\rightarrow\log_b{x}<1$$ his expectation is negative, and since the game is zero sum our expectation of $$\text{our EV}=\$1-\log_{10}(8)$$is positive

We don't have a calculator in our bathroom, but that is about $9.69\text{c}$ per game played.

(Note that if he goes for the longest odds of $10:1$ by choosing $d=9$ every time our expected value is around $49.67\text{c}$ per game played.)

$\endgroup$
  • $\begingroup$ @JonathanAllan That's what the curly braces mean. $\endgroup$ – f'' Jul 28 '16 at 13:47
  • $\begingroup$ I can't read this.English, please? xD $\endgroup$ – that2guy Jul 29 '16 at 11:52
  • $\begingroup$ @that2guy - I don't know if my expanded version will help or not, it's still not English, but it's definitely more verbose. $\endgroup$ – Jonathan Allan Jul 30 '16 at 11:38
  • $\begingroup$ @f'' No doubt you will find a mistake or two :D $\endgroup$ – Jonathan Allan Jul 30 '16 at 11:38
  • $\begingroup$ @f" it was a very nice and short proof! I was concerned abt the evenly distributed part, but @JonathanAllan cleared that out by mentioning the equidistribution theorem. This result got very close to the simulated results that I got. The only doubt I still have, is abt how fast the interval [0,1) is filled by $\{n\log_{10}2\}$. Also, there is clearly, a correlation between these numbers. So, perhaps, if you sample the sequence, $2^n$, at intervals apart enough, you can guarantee, {.} is generated by a uniform probability distribution. $\endgroup$ – minimax Jul 30 '16 at 18:46
9
$\begingroup$

For an answer to this question you can look up Benford's law which describes a mathematical phenomenon that applies to all forms of naturally growing values.

I don't know enough about it to provide a prove right now (maybe somebody else could do so) but the distribution should be close to this:

1: 30.1%
2: 17.6%
3: 12.5%
4: 9.7%
5: 7.9%
6: 6.7%
7: 5.8%
8: 5.1%
9: 4.6%

$\endgroup$
  • 1
    $\begingroup$ Starts to fit pretty well pretty quickly (first for a leading $9$ would be $n=53$) - at $n=4000$ we have $30.125, 17.625, 12.475, 9.7, 7.925, 6.725, 5.75, 5.175, 4.525\%$ $\endgroup$ – Jonathan Allan Jul 28 '16 at 13:04
  • $\begingroup$ You can actually use this everywhere you have some kind of "measured" numbers. Take a newspaper and look at all numbers that can grow naturally and potentially up to infinity (so you dont look at stuff like telephone numbers, dates or times) and the distribution will be approximately the same. $\endgroup$ – The Dark Truth Jul 28 '16 at 13:09
  • $\begingroup$ The fraction of $n$s occurring as first digit will converge against $log_{10}((n+1)/n)$. $\endgroup$ – Anon Jul 28 '16 at 13:10
4
$\begingroup$

A small simulation ($n$ up to 100,000) to demonstrate f'''s proof:

1: 30103, 2: 17611, 3: 12492, 4: 9692, 5: 7919, 6: 6695, 7: 5797, 8: 5116, 9: 4575.

And in graph form: enter image description here

$\endgroup$
  • $\begingroup$ This is a good example of "Ziph's" law. $\endgroup$ – that2guy Jul 29 '16 at 11:55
  • $\begingroup$ @that2guy As mentioned in TheDarkTruth's answer, this is an example of Benford's law, not Zipf's law. $\endgroup$ – f'' Jul 29 '16 at 13:07
  • $\begingroup$ But I was close, right? XD $\endgroup$ – that2guy Jul 29 '16 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.