Считаем кур, пока их не заклевали

[propell-ant]

Эх, куры. Исходная задача может быть переформулирована в реальный мир так:
Есть рынок с конечным числом покупателей, есть некоторый товар, который покупатели случайным образом продают друг другу. Купивший сразу же убеждается, что товар ему не нужен (т.е. это ему «впарили» ненужный товар) и повторно ему уже продать этот товар не получится. Какое ожидаемое количество покупателей не купит в итоге товар?

И в такой формулировке легко понять, почему эта задачка так актуальна сегодня (см. качество ликвидности на финансовых рынках).

И вот ссылка на старинную статью Очкова про расчет финансовой пирамиды, один из графиков (тот, что с двумя пиками) удивительно похож на то, что в статье.

[sebres]

Когда летом читал оригинал, набросал симулякр на питоне, вдруг кому нужно поиграться пригодится…

Скрытый текст

REPEAT = 10000

DEBUG = False
CHICKS_CNT = 100
SIMULTANEOUS = True
ONCE = False

# --------------------------

import os

if DEBUG:
  def debug(*args):
    print(args[0] % args[1:])
else:
  def debug(*args):
    pass

try:
    xrange
except NameError:
    xrange = range

def get_rnd_01(length):
  if isinstance(os.urandom(1)[0], int):
    return (c & 1 for c in os.urandom(length))
  return (ord(c) & 1 for c in os.urandom(length))

def it_peck(chicks, simultaneous=SIMULTANEOUS):
  if simultaneous:
    _pritbuf = list(chicks)
  for i, p in enumerate(get_rnd_01(len(chicks))):
    if simultaneous:
      if _pritbuf[i] <= 0: continue
    else:
      if chicks[i] <= 0: continue
    p = i + (1 if p else -1)
    if p < 0: p = len(chicks) - 1
    if p >= len(chicks): p = 0
    debug('  %6r pecks %r', i, p)
    chicks[p] -= 1
  for i in xrange(len(chicks)):
    if chicks[i] < 0: chicks[i] = 0

def stop_it(chicks):
  for i in xrange(len(chicks)-1):
    if chicks[i] and chicks[i+1]: return False
  return False if chicks[len(chicks)-1] and chicks[0] else True


itn = 0
avg = 0
while itn < REPEAT:
  chicks = [1]*CHICKS_CNT
  debug('** %r) ...', itn)
  while True:
    debug('  ** %r) ** iter', itn)
    it_peck(chicks)
    if ONCE or stop_it(chicks): break
  s = sum(chicks)
  debug('** %r) = %r', itn, s)
  avg += s
  itn += 1

avg = float(avg) / REPEAT
print(avg)

[eshirshov]

У меня по другому получилось…
итерация 0) — 1. живых кур
итерация 1) — 1/4 живых кур, включительно: 1/16 живых кур парных
1/16 живых кур парных через N итераций останется половина = 1/32
итерация N) 1 = 3/4(одиночных кур)+1/4(парных кур)
N.1. 1/4*3/4 = 3/16, где 3/4 — одиночных кур
N.2. 1/4*1/4*1/2 =1/32, 1/4 — парных кур, 1/2 выживает в парном состязании
N.3. 3/16+1/32 = 7/32 итоговая выживаемость
сравнение итогов:
7/32 < 8/32(1/4 оригинальный ответ)
P.S.
предполагаю, что Люк Робитейл ни секунды не думал над ответом, а выбрал из один из предложенных.
конечно, я могу ошибаться в расчётах, но точно вижу, что оригинальные расчёты не учитывают возможность живых парных посте первой итерации

[PatientZero]

В вопросе, на который отвечал Робитейл, была одна итерация.

[eshirshov]

нда, про много итераций ответа в статье нет. упомянут твит Джордана Элленберга мимоходом зачем-то и на этом всё. Ввелся в заблуждение.

[PatientZero]

Как это нет? Ожидаемое количество выживших в задаче Робитейла с одной итерацией — N/4, в задаче Элленберга с клеванием до победного конца — N/6.

[eshirshov]

решать мат.задачки пол-первого ночи плохая идея была(((

[3aicheg]

Мой вариант на Python 3:

import random

#chicken are represented as a [0, 1, 1, 0, ...] list
#0 for pecked, 1 for unpecked

#peck a random neighbor (if and where we can)
def peck(chicken, pecked_can_peck = True):
    N = len(chicken)
    ch = chicken[:]
    for i in range(N):
        if not pecked_can_peck and chicken[i] == 0: continue
        left, right = i-1, (i+1)%N
        who_to_peck = random.choice([left, right])
        ch[who_to_peck] = 0
    return ch

#check if there are still an opportunity to peck
def unpecked_adjacent_exist(chicken):
    for i in range(len(chicken)):
        if chicken[i-1] + chicken[i] == 2: return True
    return False

#peck one time, return the number of survivors
def pecked_single(N):
    chicken = [1]*N
    chicken = peck(chicken)
    return sum(chicken)

#peck iteratively while we can, then return the number of survivors
def pecked_iterative(N):
    chicken = [1]*N
    while unpecked_adjacent_exist(chicken):
        chicken = peck(chicken, False)
    return sum(chicken)

N_chicken = 100 #number of chicken
N_iter = 10000  #number of trials
survivors_single, survivors_iterative = 0, 0
for i in range(N_iter):
    survivors_single += pecked_single(N_chicken)
    survivors_iterative += pecked_iterative(N_chicken)

#averaged results
print(survivors_single/N_iter, survivors_iterative/N_iter)

[lega]

Я так посчитал, незнаю правильно ли: минимальный процент выжившых = 0, максимальный = 1/3, оба варианта возможны но это крайтие точки, беру среднее = (0 + 1/3) / 2 = 1/6, т.е. результат = ~17

[RagnarHab]

нет же, допустим 1/3 выпала один раз,0-выпало 1 раз, а 1/4 100 раз, все сложить будет не 1/6.

[scientes]

Function TaskOfHens(iHensCount) 
    numenator=0;
    denominator=1;
    N=iHensCount;
    i=1;
    prev=1;
    while N>2 do
        prev=prev*N/i;
        numenator=numenator+i*prev;
        N=N-3;  i=i+1;
    enddo;  

    N=iHensCount;
    j=(numenator%4);
    answer=numenator-j;
    while N>2 do
        answer=answer/4;
        N=N-3;
    enddo;  
    return answer+j/4;  
EndFunction

iHensCount=99 Ответ -> 24,75

[Fusion23]

Я завидую упорству автора, а также владению им такого большого количества свободного времени)