Skip to content

Đợi

Tháng Mười 4, 2010

Đợi có thể là đợi mua gạo, mua dầu (thời bao cấp), đợi người yêu, đợi vợ. Đợi cái gì cũng lâu, sốt cả ruột. Nhà toán học được mỗi một cái hơn đời là khi không có gì để làm có thể mang toán ra nghí, mặt ngây ngô trông không được tích sự gì (như một số nhân vật trong truyện Nam Cao) nhưng thời gian trôi nhanh hơn.

Hôm nay nói về toán của đợi. Rách việc, đợi lâu khắc đến lượt, thể nào chẳng mua đươc gạo. Nhưng toán này do các ông Tây chưa bao giờ phải xếp hàng mua gạo nghĩ ra, cũng nên xem thử.

Một mô hình các ông Tây hay dùng dựa trên ý tưởng sau. Về lý thuyết, gạo về lúc 8 giờ sáng để phục vụ đồng bào. Trên thực tế, nó sẽ về sau 8 giờ và vào lúc nào thì chỉ có trời (và các cô bán gạo) biết. (Trong một số trường hợp trời cũng không biết.) Giả thử 8 giờ là thời gian 0. Vào thời điểm x, x >0, ông Tây giả sử là xác suất gạo về trong khoản thời gian [x, x+h] tỷ lệ thuận với h, hay chính xác \approx   \lambda h, trong đó \lambda là một hằng số (tất nhiên ta phải giả sử xác suất này chỉ được tính khi gạo chưa về) và h đủ nhỏ. Nói nôm na, trong một window càng dài, xác suất gạo về càng tăng.

Mô hình này không tệ lắm, và được ứng dụng nhiều. Bên Mỹ này không thấy xếp hàng mua gạo mấy khi, mô hình náy được dùng cho thời gian đợi của telephone, khi đien thoại còn ở thời kỳ sơ khai và AT&T còn là một công ty lớn nhất thế giới. Thời hoàng kim của Bell Labs, các nhà xác suất thống kê đóng một vai trò quan trọng trong phòng thí nghiệm này. Vị trí của nó giờ đây có lẽ đã được thay bởi Microsoft Research.

Điểm mấu chốt của mô hình trên là nó không phụ thuộc vào x (các bác Tây không thích nói chuyện quá khứ !). Nếu bạn nghĩ đến hai trường hợp: 9 giờ gạo chưa về và 11 giờ gạo chưa về thì tại hai thời điểm 9 và 11 giờ, thời gian đơi thêm sẽ có phân bố như nhau. Gọi u(t) là xác suất bạn phải đợi ít nhất là một thời gian là t. Nếu phải đợi \ge t+s, thì trước hết bạn phải đơi t, sau đó đơi thêm s. Bơi tính chất trên, ta có

u(t+s) = u(t) u(s).

Bạn có thể chứng minh (bài tập)

Đinh lý Đợi: Hoạc u(t)=0 với mọi t, hoặc u(t) = e^{-\lambda t } với \lambda là một hằng số.

Vì định lý này, mô hình trên còn được goi là “exponential holding time model”. Dưới đây, bạn có thể thử dùng mô hình này để giải một bài toán cụ. thể. Giả sử bạn ra bưu điện gửi bưu phẩm. Bưu điện có m ô cúa và phải xếp hàng. Khi có một ô cửa trống thì (dĩ nhiên) ngừoi đầu tiên trong hàng được vào ô của đó. Câu hỏi là khi bạn đến bưu điên thì sẽ có mấy người đứng trước bạn ?

Bài toán phát biếu như trên là bài toán từ ứng dụng mà ra. Để giải bài toán này, ta cần một model cụ the. Ta có thể giả sử thời gian giải quyết (đợi) ở mỗi cúa sổ là biến ngấu nhiên như mô hình trên với hằng số \mu. Ngoài ra thời gian để có thêm một người xếp hàng (cũng theo mô hình đợi) phụ thuộc vào hằng số \lambda khác. Gọi P_n(t) lá xác suất có n người tại thời gian t, trong cả hàng và tại các cửa sổ. Tưởng tượng là thời điểm bạn đến đã tương đối muộn, cải ta muốn tính là p_n = \lim _{t  \rightarrow \infty} P_n (t) . Bài toán này được nghiên cứu bởi Kolmogorov đầu những năm 1930.

From → Khác

13 phản hồi
  1. Haha permalink

    Giaỉ bài này cần phải…đợi lâu, anh ạ.🙂

  2. Bngo permalink

    Lần đầu tiên em biết định lý Đợi. Trước đó em biết bài thơ Đợi (cũng được phổ nhạc thành bài hát Đợi) rất hay😀

  3. KHG permalink

    Đợi mãi mới đọc được bài mới của thầy, và rất tự nhiên, là câu chuyên về việc đợi🙂 \lambda trong trường hợp này có thể không là hằng số mà giảm dần theo thời gian🙂🙂

  4. Hi. I’m from the Philippines and hardly speak any Vietnamese. I just stumbled upon your blog, randomly surfing maths blog in WordPress. It is amazing that you have equations in between the Vietnamese words, so I suppose the discussion has something to do with math — and you actually have Vietnamese words for technical mathematical terms. The use of Filipino (Tagalog) in academic writings in my country is virtually inexistent, and even the most native Tagalog, purist speakers will find it hard to translate a math text in Tagalog. I suppose that the situation with Vietnamese is the same as Chinese and Japanese where the academe has not been very dependent on the use of English.

    • Well right now the use of english is very common, but 40 years ago it was russian. We do have vietnamese words for technical terms in most fields, from mathematics to
      medical sciences, and so the education is in vietnamese. It has both pros and cons, though.

  5. Blue permalink

    Mô hình này tương tự như quá trình Poisson phải không anh Văn? Btw, em thấy nơi thì viết Poisson process, nơi thì lại viết Poisson point process, nhờ anh viết về phần này cho bọn em tham khảo với nha.

  6. XuanLong Nguyen permalink

    Để tôi trả lời thay bác Văn nhé. Tôi đoán câu chuyện đợi của anh Văn sẽ đi đến Poisson process, cũng giống như câu chuyện số đề dẫn đến Gaussian distribution/process. Nếu vậy thì rất thú vị. Poisson process có thể định nghĩa trên tập số thực (R), cho thời gian chẵng hạn, khi đó sẽ dẫn đến câu chuyện đợi trên. Nhưng tổng quát và dễ hình dung và mạnh hơn thì Poisson process thường được định nghĩa là phân bố cho các điểm trên mặt phẳng (R^2), hoặc R^n.

    Theo rất nhiều khía cạnh Gaussian và Poisson là hai cái cột trụ chính trong LTXS, stochastic processes, cũng như trong statistical modeling. Mọi hiện tượng ngẫu nhiên hầu như đều thường được truy tận cùng về hai phân bố XS này. Nếu bạn master được hai cái cột này thì bạn sẽ là người may mắn và hạnh phúc đấy.

  7. NGUYEN DUY TIEN permalink

    THEO TOI PHAI THEM GIA THIET CO GIA SO DOC LAP.
    Qua trinh Poisson la qua trinh $u(t)$ co gia so doc lap (independent increaments) va co phan phoi Poisson, t la thoi gian. Qua trinh diem Poisson (Poisson point process), co dinh nghia tuong tu, nhung tham so $t$ khong nhat thiet la thoi gian.
    VHvan la con nha tho VU QUAN PHUONG voi bai tho noi tieng “DOI”. Toi rat thu vi khi doc bai Doi nay cua VH Van.

  8. Blue permalink

    That tinh la minh khong hieu cau tra loi cua ban Xuan Long, tru cai comment dang sau.

  9. XuanLong Nguyen permalink

    Để hiểu rõ hơn thì chắc bạn phải gọi bác Văn thôi. Hoặc tốt nhất là giở một quyển sách về Poisson process ra học. (Đế khởi động, tôi giới thiệu một quyến viết rất elegant, súc tích dễ đọc nhưng nhiều kết quả hay, của Kingman (Tựa đề: Poisson processes), tập trung vào lý thuyết tổng quát trên R^n thay vì R. Đó là một câu chuyện dài và thú vị.

  10. nkd permalink

    Cuối cùng, cuộc chờ đợi của anh cũng có kết quả đấy nhỉ.😀

  11. Hihi, doi mai, hay Long viet mot bai “guest blog” di ?

  12. XuanLong Nguyen permalink

    OK, xin khất nợ anh Văn một dịp nha…

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: