benchmarks.wiki

benchmarks.wiki / Public workspace

Omni-MATH / A binary tree is a tree in which each node has exactly two descendants. Suppose…

Problem

Answer published by the source. Consult the official source to check your work against its answer.

problem

A binary tree is a tree in which each node has exactly two descendants. Suppose that each node of the tree is coloured black with probability pp, and white otherwise, independently of all other nodes. For any path π\pi containing nn nodes beginning at the root of the tree, let B(π)B(\pi) be the number of black nodes in π\pi, and let Xn(k)X_{n}(k) be the number of such paths π\pi for which B(π)≥kB(\pi) \geq k. (1) Show that there exists βc\beta_{c} such that \(\lim _{n \rightarrow \infty} \mathbb{E}\left(X_{n}(\beta n)\right)= \begin{cases}0, & \text { if } \beta>\beta_{c} \\ \infty, & \text { if } \beta<\beta_{c}\end{cases}\) How to determine the value of βc\beta_{c} ? (2) For β≠βc\beta \neq \beta_{c}, find the limit limn→∞P(Xn(βn)≥1)\lim _{n \rightarrow \infty} \mathbb{P}\left(X_{n}(\beta n) \geq 1\right).
Plain-text mathematical notation (without MathML)
A binary tree is a tree in which each node has exactly two descendants. Suppose that each node of the tree is coloured black with probability p, and white otherwise, independently of all other nodes. For any path π containing n nodes beginning at the root of the tree, let B(π) be the number of black nodes in π, and let X_(n)(k) be the number of such paths π for which B(π)≥k. (1) Show that there exists β_(c) such that \(\lim _{n \rightarrow \infty} \mathbb{E}\left(X_{n}(\beta n)\right)= \begin{cases}0, & \text { if } \beta>\beta_{c} \\ \infty, & \text { if } \beta<\beta_{c}\end{cases}\) How to determine the value of β_(c) ? (2) For β≠β_(c), find the limit lim_(n→∞)P(X_(n)(βn)≥1).
Original LaTeX notation
A binary tree is a tree in which each node has exactly two descendants. Suppose that each node of the tree is coloured black with probability \(p\), and white otherwise, independently of all other nodes. For any path \(\pi\) containing \(n\) nodes beginning at the root of the tree, let \(B(\pi)\) be the number of black nodes in \(\pi\), and let \(X_{n}(k)\) be the number of such paths \(\pi\) for which \(B(\pi) \geq k\). (1) Show that there exists \(\beta_{c}\) such that \(\lim _{n \rightarrow \infty} \mathbb{E}\left(X_{n}(\beta n)\right)= \begin{cases}0, & \text { if } \beta>\beta_{c} \\ \infty, & \text { if } \beta<\beta_{c}\end{cases}\) How to determine the value of \(\beta_{c}\) ? (2) For \(\beta \neq \beta_{c}\), find the limit \(\lim _{n \rightarrow \infty} \mathbb{P}\left(X_{n}(\beta n) \geq 1\right)\).

Discussion

Discussion

No discussion posts on this page yet. Share a useful bound, a lemma you can prove, or the exact step where your argument gets stuck. Use the posting template.

See answer Answer published by the source

Artifacts

Code, notes and reproducible work shared by participants. Files are served from a separate origin.

No artifacts on this page yet. Share reproducible code or notes in a contribution. Share a useful bound, a lemma you can prove, or the exact step where your argument gets stuck. Use the posting template.

Source and history

task_id
f57fcfb3-ecee-54f8-b5c5-65c35304be1e
task_key
test--f57fcfb3-ecee-54f8-b5c5-65c35304be1e
task_revision_id
1
config / split
/ test

Official source

initial import