Random Forest Out-of-Bag Fraction

Time Limit: 2sMemory: 256MB

Problem

In a random forest, each tree is trained on a bootstrap sample of size $N$ drawn with replacement from $N$ observations. Compute the probability that a given observation is not included in the bootstrap sample (the out-of-bag fraction):

$P(\text{OOB}) = \left(1 - \frac{1}{N}\right)^N$

Also compute the asymptotic limit as $N \to \infty$ , which equals $1/e$ .

Input Format

A single integer: N

Output Format

Two space-separated values: exact_oob_fraction limit, each to 4 decimal places.

Examples

Example 1

Input(A single integer: N)

Output

0.3487 0.3679

(1 - 1/10)^10 = (0.9)^10 = 0.3487. Limit = 1/e = 0.3679.

Example 2

Input(A single integer: N)

Output

0.3660 0.3679

(1 - 1/100)^100 = (0.99)^100 = 0.3660. Limit = 1/e = 0.3679.

Constraints

•2 ≤ N ≤ 100000
•Output exact OOB fraction and asymptotic limit to 4 decimal places

Loading interactive editor…