Expected value and recursion

Probability Level 3

I have three dice and I keep rolling all of them until they all show different numbers.

What is the expected number of rolls?

For example:

I roll one time and get $5,5,3$ .
So, I roll second time and get $1,1,1$ .
So, I roll a third time and get $3,1,4$ .
The number of rolls is $3$ .

The answer is 1.8.

3 solutions

Aryan Sanghi
Aug 17, 2020

Now, Probability of getting all different $\displaystyle P = \frac{6×5×4}{6×6×6}$

Or $\displaystyle \boxed{P = \frac59}$

$\displaystyle E = \sum \text{(Number of times dice is rolled)} × \text{(Probability that it is rolled that many times)}$

$\displaystyle E = 1 × \frac59 + 2 × \bigg(\frac49\bigg)^1 × \frac59 + 3 × \bigg(\frac49\bigg)^2 × \frac59 + 4 × \bigg(\frac49\bigg)^3 × \frac59 + \ldots \infty$

$\displaystyle E = \sum_{r=1}^{\infty} r × \bigg(\frac49\bigg)^{r-1} × \frac59$

Apply A.G.M. summation to get

$\color{#3D99F6}{\boxed{E = 1.8}}$

Good solution. This is also a geometric distribution with $p=\dfrac{5}{9}$ and expectation $\dfrac{1}{p}=\dfrac{9}{5}=\color{#20A900}{\boxed{1.8}}$ .

Let $N$ be the number of rolls, so $N \sim \textnormal{Geom}(p)$ .

$\begin{aligned}\mathbb{E}(N)&=1\cdot p+2\cdot(1-p)p+3\cdot (1-p)^2p+...\\&=p(1+2x+3x^2+...)\ \left\{ x:=1-p\right\}\\S&=1+x+x^2+...=\frac{1}{1-x}\\\implies S'&=1+2x+3x^2+...\\&=\frac{d}{dx}\left (\frac{1}{1-x}\right )=\frac{1}{(1-x)^2}\\\therefore \mathbb{E}(N)&=pS'\\&=\frac{p}{(1-(1-p))^2}\\&=\frac{1}{p}\ \square\\&=\color{#20A900}{\boxed{1.8}}\color{#333333}\textnormal{ where }p=\frac{5}{9}\end{aligned}$

Matthew Christopher - 9 months, 4 weeks ago

Ohk. Thanku sir. :)

Aryan Sanghi - 9 months, 4 weeks ago

@Matthew Christopher , would you please verify my solution.

saket goyal - 9 months, 4 weeks ago

Looks good to me!

Matthew Christopher - 9 months, 4 weeks ago

I typed two, there's nothing like 1.8 rolls

Also I just did $\frac{6}{6} × \frac{5}{6} × \frac{4}{6} = \frac{20}{36}$

Which divides $1$ and gives $1.8$

A Former Brilliant Member - 9 months, 4 weeks ago

Hmm, there's a difference between expected number of rolls and not absolute number of rolls. Expected value can be any real number. :)

Aryan Sanghi - 9 months, 4 weeks ago

@Devbrat Dandotiya , I think your solution is wrong as you just forced the answer to come out of nowhere.

The question asks about the Expected number of moves and not the probability of getting different results on each individual die .

saket goyal - 9 months, 4 weeks ago

If it's about dividing 1 by that fraction, it's not wrong. And no, 'I never force the value to come out of nowhere', there's reasoning behind that. If you're really questioning where did that 1 come from, it's the 100% probability of having all numbers differ

A Former Brilliant Member - 9 months, 4 weeks ago

Sorry If you my initial comment was hurtful.

saket goyal - 9 months, 4 weeks ago

@Saket Goyal – No I'm really insecure

A Former Brilliant Member - 9 months, 4 weeks ago

The solution is actually correct, though needs some additional explanation.

The probability of attaining different values is $\dfrac{20}{36}=\dfrac{5}{9}$ as shown. Importantly, the expected number of rolls before and including the "stop" roll follows a geometric distribution, and the expectation of this is $\dfrac{1}{\left (\frac{5}{9}\right )}$ as I proved above. For the reason why this follows a geometric distribution, see the parent solution and my comment.

Matthew Christopher - 9 months, 4 weeks ago

Oh, thanks I see it now

saket goyal - 9 months, 4 weeks ago

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
int role();
int power(int a);
int main()
{
    int precision=7;
    srand(time(0));
    long int solution=0;
    for(long int a=0;a<power(precision);a++)  solution+=role();
    long long int alpha=solution/power(precision), beta=solution%power(precision);
    cout << alpha << ".";
    for(int delta=1;delta<precision;delta++){
        if(beta<power(delta))   cout << 0;
    }
    cout << beta;
    return 0;
}
int role(){
    int c=1;
    for(;1;c++){
        int rolls[3];
        for(int b=0;b<3;b++)    rolls[b]=rand()%6+1;
        if(rolls[0]!=rolls[1]&&rolls[0]!=rolls[2]&&rolls[1]!=rolls[2])  break;
    }
    return c;
}
int power(int a){
    int b=1;
    for(int c=0;c<a;c++)    b*=10;
    return b;
}

A Former Brilliant Member - 9 months, 3 weeks ago

Saket Goyal
Aug 16, 2020

Let Expected number of moves = $E$ .

E can be one if I get all of the numbers different on first roll. This has a probability 5/9.

Or I can increase E by 1 if I do not get all numbers different. This has a probability 4/9.

So $E=(1)(5/9)+(E+1)(4/9)$

By solving recursion $E=1.8$

Nice use of conditional expectation.

Mark Hennings - 9 months, 4 weeks ago

https://brilliant.org/problems/triangles-and-circles-but-not-geometry-part-3/ Can you please help me with this one.

saket goyal - 9 months, 4 weeks ago

Yuriy Kazakov
Aug 18, 2020

I use Absorbing Markov chain

Wolframalpha

Answer $\boxed{1.8}$

And Python Monte Carlo

import random
def control(x,y,z):
  if x==y or x==z or y==z:
    return False
  return True
d=[0 for k in range(50)]
N=100000
for k in range(N):
  k1=1
  k2=1
  k3=1
  s=0
  while control(k1,k2,k3)==False:
    s=s+1
    k1=random.randint(1,6)
    k2=random.randint(1,6)
    k3=random.randint(1,6)
    #print(k1,k2,k3,control(k1,k2,k3))
  d[s]=d[s]+1
s=-1
pq=0
for kd in d:
  s=s+1
  pq=pq+s*d[s]
  if d[s]>0:
    print(s,d[s],d[s]/N) 
print(pq/N)

Expected value and recursion

The answer is 1.8.

3 solutions

0 pending reports