Question

USE R TO WRITE THE CODES!

# 2. More Coin Tosses
Experiment: A coin toss has outcomes {H, T}, with P(H) = .6.
We do independent tosses of the coin until we get a head.

Recall that we computed the sample space for this experiment in class, it has infinite number of outcomes.

Define a random variable "tosses_till_heads" that counts the number of tosses until we get a heads.
```{r}

```

Use the replicate function, to run 100000 simulations of this random variable.
```{r}

```
Use these simulations to estimate the probability of getting a head after 15 tosses. Compare this with the theoretical value computed in the lectures.
```{r}

```
Compute the probability of getting a head after 50 tosses. What do you notice?
```{r}

Answer 1

// Naive approach in C++ to find probability of // at least k heads #include<bits/stdc++.h> using namespace std; #define MAX 21 double fact[MAX]; // Returns probability of getting at least k // heads in n tosses. double probability(int k, int n) {     double ans = 0;     for (int i = k; i <= n; ++i)         // Probability of getting exactly i         // heads out of n heads         ans += fact[n] / (fact[i] * fact[n - i]);     // Note: 1 << n = pow(2, n)     ans = ans / (1LL << n);     return ans; } void precompute() {     // Preprocess all factorial only upto 19,     // as after that it will overflow     fact[0] = fact[1] = 1;     for (int i = 2; i < 20; ++i)         fact[i] = fact[i - 1] * i; } // Driver code int main() {     precompute();     // Probability of getting 2 head out of 3 coins     cout << probability(2, 3) << "\n";     // Probability of getting 3 head out of 6 coins     cout << probability(3, 6) <<"\n";     // Probability of getting 12 head out of 18 coins     cout << probability(12, 18);     return 0; }

Output:

0.5
0.65625
0.118942

Time Complexity: O(n) where n < 20
Auxiliary space: O(n)

Method 2 (Dynamic Programming and Log)
Another way is to use Dynamic programming and logarithm. log() is indeed useful to store the factorial of any number without worrying about overflow. Let’s see how we use it:

At first let see how n! can be written.
n! = n * (n-1) * (n-2) * (n-3) * ... * 3 * 2 * 1

Now take log on base 2 both the sides as:
=> log(n!) = log(n) + log(n-1) + log(n-2) + ... + log(3) 
         + log(2) + log(1)

Now whenever we need to find the factorial of any number, we can use
this precomputed value. For example:
Suppose if we want to find the value of nCi which can be written as:
=> nCi = n! / (i! * (n-i)! )

Taking log2() both sides as:
=> log2 (nCi) = log2 ( n! / (i! * (n-i)! ) )
=> log2 (nCi) = log2 ( n! ) - log2(i!) - log2( (n-i)! )  `

Putting dp[num] = log2 (num!), we get:
=> log2 (nCi) = dp[n] - dp[i] - dp[n-i] 

But as we see in above relation there is an extra factor of 2n which
tells the probability of getting i heads, so
=> log2 (2n) = n.

We will subtract this n from above result to get the final answer:
=> Pi (log2 (nCi)) = dp[n] - dp[i] - dp[n-i] - n

Now: Pi (nCi) = 2 dp[n] - dp[i] - dp[n-i] - nTada! Now the questions boils down the summation of Pi for all i in
[k, n] will yield the answer which can be calculated easily without
overflow.

Below are the codes to illustrate this:

• C++
• Java
• Python3
• C#
• PHP

filter_none

edit

play_arrow

brightness_4

// Dynamic and Logarithm approach find probability of // at least k heads #include<bits/stdc++.h> using namespace std; #define MAX 100001 // dp[i] is going to store Log ( i !) in base 2 double dp[MAX]; double probability(int k, int n) {     double ans = 0; // Initialize result     // Iterate from k heads to n heads     for (int i=k; i <= n; ++i)     {         double res = dp[n] - dp[i] - dp[n-i] - n;         ans += pow(2.0, res);     }     return ans; } void precompute() {     // Preprocess all the logarithm value on base 2     for (int i=2; i < MAX; ++i)         dp[i] = log2(i) + dp[i-1]; } // Driver code int main() {     precompute();     // Probability of getting 2 head out of 3 coins     cout << probability(2, 3) << "\n";     // Probability of getting 3 head out of 6 coins     cout << probability(3, 6) << "\n";     // Probability of getting 500 head out of 10000 coins     cout << probability(500, 1000);     return 0; }

Output:

0.5
0.65625
0.512613

Time Complexity: O(n)
Auxiliary space: O(n)