17
$\begingroup$

A drunken honeybee lands on a completely random hexagon of a large triangular section (depicted below) of its hive, and then every second afterwards, takes a step to a completely random adjacent hexagon. How long on average will it take for the honeybee to escape this region? enter image description here

This is my own transformative result of an existing probability problem. Hint: The solution (for this given case) will be an integer!

$\endgroup$
  • $\begingroup$ I worked out some small triangles by hand, and it seems to indicate the answer for side length 17 is rot13(gjraglbar), but I'm failing to see why such pattern arises... $\endgroup$ – Bubbler Oct 28 at 5:50
  • $\begingroup$ cant think of a solution without a computer :) $\endgroup$ – Oray Oct 28 at 8:34
  • $\begingroup$ I had a submitted edit rejected to change 'depicted below' to 'depicted below for n=17'. It actually makes a difference to whether the assertion "Hint: The solution will be an integer!" is only being claimed for n=17 as depicted, or in general. (cc: @VoldemortsWrath) $\endgroup$ – smci Oct 28 at 21:00
  • $\begingroup$ @smci -- The question has already been (correctly) answered, so it's clearly answerable without the edit. Therefore, it's really not needed. $\endgroup$ – Voldemort's Wrath Oct 29 at 1:30
  • $\begingroup$ @VoldemortsWrath: you're misunderstanding me. I said the claim hidden down the bottom of the question "The solution will be an integer!" for all n is stronger than just claiming that for n=17 case; which seemed counterintuitive at first. $\endgroup$ – smci Oct 29 at 1:41
10
$\begingroup$

Let $n$ be the size of the triangle and $(a,b,c)$ the barycentric coordinates of a given hexagon within that triangle, such that $a+b+c = n+2$. I claim that the average escape time $E$ when starting from that hexagon is $\frac {3abc} {n+2}$ (1). Indeed, we have the system of equations $E(a,b,c) = 1 + \frac{E(a+1,b-1,c) + E(a,b+1,c-1) + E(a-1,b,c+1) + E(a-1,b+1,c) + E(a,b-1,c+1) + E(a+1,b,c-1)} {6}$
and it is straight forward to check that the $E$ given by (1) satisfies these equations and the boundary conditions which are $E(a,b,c) = 0$ if $a=0 \vee b=0 \vee c=0$.

It remains to average over starting points: $\langle E \rangle = \frac {2} {17\times 18} \sum_{a+b+c = 19} \frac {3abc} {19}$ The sum can be recognized as up to prefactors the binomial coefficient $\begin{pmatrix}21 \\ 5 \end{pmatrix}$ yielding $\langle E \rangle = \frac {2} {17\times 18} \times \frac {3} {19} \times\begin{pmatrix}21 \\ 5 \end{pmatrix} = 21$

To get some intuition for the formula $\begin{pmatrix}N+2n \\ 2n+1 \end{pmatrix} = \sum_{i_0,\ldots,i_n \ge 1, i_0+\ldots+i_n = N+n} i_0 \cdots i_n$ recall that the binomial coefficient on the l.h.s. can be interpreted as the volume (number of cannon balls) in an 2n+1-dimensional pyramid shaped pile of cannon balls with N cannon balls along each edge. This can be shown by a routine stars-and-bars argument using barycentric coordinates.
enter image description here Source: wikipedia public domain


Leaving the subtleties of discretization to one side let us project the $2n+1$-simplex (which has $2n+2$ barycentric coordinates) to the $n$-simplex (which has $n+1$ barycentric coordinates) simply by pairing coordinates and summing pairs. We can now ask what are the shape and volume of the subset of the large simplex that gets mapped to a single point in the small simplex? One can work out that it must be a (hyper) cuboid, but maybe it's easier to just look at a picture:
enter image description here Source: wikipedia CC BY-SA 4.0 Tomruen

| improve this answer | |
$\endgroup$
  • $\begingroup$ Well done! rot13(Gur ovg nobhg gur ovabzvny pbrssvpvrag vf arj gb zr; jurer qbrf gung sbezhyn pbzr sebz? (V whfg qvq fbzr nytroen gb svther bhg gur fhz) Nyfb, ner lbh noyr gb zbgvingr jurer gung pryy-jvfr sbezhyn lbh irevsvrq pnzr sebz?) $\endgroup$ – Feryll Oct 28 at 11:00
  • $\begingroup$ @Feryll rot13 V tbg obgu ol rkgencbyngvat gur 1Q pnfr. Gur 1Q pnfr pna or fbyirq ol unaq sbe fznyy rqtr yratguf naq gur sbezhyn pna or thrffrq gura. V qba'g unir nal tbbq vaghvgvba jul vg fubhyq or guvf sbezhyn. Er gur ovabzvny pbrssvpvrag: Gur 1Q pnfr vf fbeg bs vaghvgvir: Guvax bs gur pnaaba onyy grgenurqeba juvpu vf glcvpnyyl hfrq nf ivfhnyvfngvba bs gur fhzzngvba sbezhyn sbe gevnatyr ahzoref. Abj gnxr vg naq qb abg onfr vg ba n snpr ohg ba bar rqtr. Gura vafcrpgvat gur ynlref lbh jvyy svaq erpgnatyrf bs svkrq pvephzsrerapr naq fhesnpr nernf 1ka 2k(a-1) rgp. $\endgroup$ – Paul Panzer Oct 28 at 11:14
  • $\begingroup$ V frr. Nf sbe pbzvat hc jvgu gur sbezhyn va gur svefg cynpr, vs lbh gnxr abgvpr bs ebgngvbany naq ersyrpgvba flzzrgel, gura nal nytroenvp sbezhyn jbhyq unir gb or n pbzovangvba bs ryrzragnel flzzrgevp cbylabzvnyf va gur onelpragevp pbbeqvangrf. Gung vzzrqvngryl cbvagf lbh gb n irel erfgevpgrq cbby bs fhfcrpgf :) $\endgroup$ – Feryll Oct 29 at 0:39
  • $\begingroup$ @Feryll rot13 Jnfa'g vg gur pnfr gung rirel flzzrgevp cbylabzvny pna or rkcerffrq nf n cbylabzvny va ryrzragnel flzzrgevp cbylabzvnyf? Be nz V zvfhaqrefgnaqvat fbzrguvat? Btw. I added a (very informal) sketch of how to obtain the summation formula. $\endgroup$ – Paul Panzer Oct 29 at 0:51
  • $\begingroup$ Lrf, ps shaqnzragny gurberz bs flzzrgevp cbylabzvnyf $\endgroup$ – Feryll Oct 29 at 3:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.