5
$\begingroup$

Inspired by this reddit post: https://old.reddit.com/r/math/comments/tv3cbg/how_do_you_unbell_curve_a_galtonplinko_board/

The Nth Galton Board, G(N), is a triangular lattice of pegs of height N-1. enter image description here

When a ball is dropped, at each level it will drop left or right with p=1/2. The path of the ball is a bernoulli distribution with N steps, and when N is large, this distribution converges to the normal distribution.

My question, which I'm not even sure how to approach answering, is twofold:

  • Which distributions can be constructed through a galton board process? (Assuming you may place pegs anywhere you like).
  • Can all distributions be constructed like this? Does there exist a distribution which cannot be constructed?
$\endgroup$
0

2 Answers 2

2
$\begingroup$

$\newcommand{\N}{\mathbb N}$The question can be apparently formalized as follows.

We have a random walk $(X_1,X_2,\dots)$ on the state space $\N:=\{1,2,\dots\}$ starting at point $1$ at time moment $1$ -- that is, $X_1=1$. If the walker is at point $j\in\N$ at a time moment $t\in\N$, then it moves to the right by $1$ with a probability $b_{t,j}\in[0,1]$ or stays at the point $j$ with probability $1-b_{t,j}$: \begin{equation*} \begin{aligned} &P(X_{t+1}=j+1|X_t=j,X_{t-1},\dots,X_1) \\ &=b_{t,j} =1-P(X_{t+1}=j|X_t=j,X_{t-1},\dots,X_1). \end{aligned} \end{equation*} The question is then this:

Given any $n\in\N$ and any probability distribution $\pi$ on the set $[n]:=\{1,\dots,n\}$, do there necessarily exist numbers $b_{t,j}\in[0,1]$ for all natural $t$ and $j$ such that the distribution of $X_n$ is $\pi$?

The answer to this question is yes, which can be proved by induction on $n$. Indeed, for $n=1$ this claim is trivial. To make the induction step, we only have to prove the following:

Take any natural $n\ge2$. Take any nonnegative real numbers $p_1,\dots,p_n$ (corresponding to the desired distribution of $X_n$) such that $p_1+\dots+p_n=1$. Then there exist (i) nonnegative real numbers $q_1,\dots,q_{n-1}$ (corresponding to an appropriate distribution of $X_{n-1}$) such that $q_1+\dots+q_{n-1}=1$ and (ii) numbers $b_1,\dots,b_{n-1}$ in $[0,1]$ such that \begin{equation*} p_j=q_{j-1}b_{j-1}+q_j(1-b_j)\text{ for all $j\in[n]$,} \tag{1}\label{1} \end{equation*} where $q_0:=0$, $q_n:=0$, $b_0:=0$, and $b_n:=0$.

But such numbers $q_1,\dots,q_{n-1},b_1,\dots,b_{n-1}$ can be explicitly and simply constructed e.g. as follows: \begin{equation*} q_1:=p_1+p_2,\ q_2:=p_3,\ \dots,\ q_{n-1}:=p_n, \end{equation*} \begin{equation*} b_1:=\frac{p_2}{p_1+p_2},\ b_2:=1,\ \dots,\ b_{n-1}:=1 \end{equation*} (if $p_1+p_2=0$, let $b_1:=1$). Indeed, then all the equalities \eqref{1} will hold. $\quad\Box$


So, to get the desired distribution, we are just successively splitting the probability of the state $1$ while carrying the other probabilities to the next time step.

That is, once the walker has left the state $1$, it will march deterministically to the right, one unit step at a time. If at a time moment $t\in\{1,\dots,n-1\}$ the walker still remains in the state $1$, then at the next time moment, $t+1$, it will still be in the state $1$ with the (conditional) probability $\dfrac{p_1+\dots+p_{n-t}}{p_1+\dots+p_{n-t}+p_{n-t+1}}$ (or will move to the state $2$ with the complementary probability $\dfrac{p_{n-t+1}}{p_1+\dots+p_{n-t}+p_{n-t+1}}$).

As an illustration, here is the tree diagram of getting the probabilities $0.2,0.3,0.4,0.1$ for the respective states $1,2,3,4$ at time $t=4$:

enter image description here

The root of this tree, at the top, corresponds to time moment $t=1$, followed by the layers corresponding to time moments $t=2,3,4$. The nodes of the tree corresponding to the time moments $t=1,2,3,4$ are labeled by the probabilities $P(X_t=j)$ for $j=1,\dots,t$.

$\endgroup$
1
$\begingroup$

If you place a peg below the inlet suitably offset to the left or right, you can achieve any probability $P$ to bounce to the right you like. Choose $P$ to be the probability with which you want the ball to end up in the right-most bin and funnel the right-bouncing balls there; funnel the left-bouncing balls such as to create a new inlet above the remaining bins. Iterate, filling the bins from right to left.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .