A socialistic coin

Probability Level 3

Consider a hypothetical coin where the probability of getting the previous result, is half the probability of obtaining the previous result before it was tossed. For example, let p n p_{n} be the probability of getting heads in the n th n^\text{th} coin toss, and so ( 1 − p n ) (1-p_{n}) is the probability of getting tails in the n th n^\text{th} coin toss. Then,

  • If the result of the n th n^\text{th} coin toss is heads then p n + 1 = p n 2 p_{n+1}=\dfrac{p_{n}}{2} .
  • If the result of the n th n^\text{th} coin toss is tails then ( 1 − p n + 1 ) = 1 − p n 2 (1-p_{n+1})=\dfrac{1-p_{n}}{2} or p n + 1 = 1 + p n 2 p_{n+1}=\dfrac{1+p_{n}}{2} .

The coin is taken and tossed until two consecutive heads are obtained. If E ( H H ) E(HH) is the expected number of tosses to get two consecutive heads, find ⌊ 1000 E ( H H ) ⌋ \left\lfloor 1000E(HH) \right\rfloor .

Details and Assumptions :

For the first toss, the probability of getting heads and the probability of getting tails are both 0.5.


The answer is 7076.

Tech Swami by Tech Swami , 22, India

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.

1 solution

Piotr Idzik
Feb 18, 2020

I have written some parallel Monte-Carlo simulation. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
 
"""
Monte-Carlo simulation for:
https://brilliant.org/problems/a-socialistic-coin/
"""
import random
from multiprocessing import Process, Queue, cpu_count
import math
import timeit

def get_random_res(head_prob):
    """
    returns 'H' with probability head_prob
    and 'T' with probability 1-head_prob
    """
    cur_rand = random.uniform(0, 1)
    if cur_rand < head_prob:
        cur_res = 'H'
    else:
        cur_res = 'T'
    return cur_res

def toss_socialistic_coin(last_res, last_head_prob):
    """
    returns the result of a single toss of the socialistic coin and the updated probability
    """
    if last_res == 'H':
        cur_head_prob = last_head_prob/2
    elif last_res == 'T':
        cur_head_prob = (1+last_head_prob)/2
    else:
        raise ValueError('Wrong input!')
    cur_res = get_random_res(cur_head_prob)
    return cur_res, cur_head_prob

def single_run(init_head_prob, goal_number_of_heads_in_row):
    """
    tosses the socialistic coin until
    the 'H' will not occur goal_number_of_heads_in_row times in a row
    """
    toss_num = 0
    cur_number_of_heads = 0
    cur_res = get_random_res(init_head_prob)
    toss_num += 1
    cur_head_prob = init_head_prob
    if cur_res == 'H':
        cur_number_of_heads += 1
    while cur_number_of_heads < goal_number_of_heads_in_row:
        cur_res, cur_head_prob = toss_socialistic_coin(cur_res, cur_head_prob)
        toss_num += 1
        if cur_res == 'H':
            cur_number_of_heads += 1
        else:
            cur_number_of_heads = 0
    return toss_num

def mc_simulation_single(init_head_prob, goal_number_of_heads_in_row, local_iter):
    """
    single tread Monte-Carlo simulation for the socialistic coin problem
    """
    cur_sum = 0
    for _ in range(local_iter):
        cur_sum += single_run(init_head_prob, goal_number_of_heads_in_row)
    print(cur_sum/local_iter)
    return cur_sum/local_iter

def call_single(init_head_prob, goal_number_of_heads_in_row, local_iter, res_queue):
    """
    wrapper of mc_simulation_single used in mc_simulation_par
    """
    res_queue.put(mc_simulation_single(init_head_prob, goal_number_of_heads_in_row, local_iter))

def mc_simulation_par(init_head_prob, goal_number_of_heads_in_row, total_iter, max_proc_num):
    """
    parallel Monte-Carlo simulation for the socialistic coin problem
    """
    local_iter = total_iter//max_proc_num
    proc_list = []
    queue = Queue()
    for _ in range(max_proc_num):
        cur_proc = Process(target=call_single,
                           args=(init_head_prob, goal_number_of_heads_in_row, local_iter, queue,))
        cur_proc.start()
        proc_list.append(cur_proc)
    for proc in proc_list:
        proc.join()
    cur_sum = 0
    while not queue.empty():
        cur_sum += queue.get()
    return cur_sum/max_proc_num

if __name__ == '__main__':
    NUMBER_OF_THREADS = cpu_count()
    START_TIME = timeit.default_timer()
    RES = mc_simulation_par(0.5, 2, NUMBER_OF_THREADS*10000000, NUMBER_OF_THREADS)
    END_TIME = timeit.default_timer()
    print(f"{RES} -> {math.floor(1000*RES)}")
    print(f"runTime: {END_TIME-START_TIME} [s]")

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...